기묘한 기계 장치

한 저평가된 발명가가 지름이 제각각인 톱니바퀴들로 이루어진 기묘한 기계 장치를 만들었다. 각 톱니바퀴에는 흰색 면과 검은색 면이 있다. 이 장치의 톱니바퀴들은 다음 네 가지 방식으로 연결될 수 있다.

• 축으로 연결: 톱니바퀴 $x$와 $y$를 같은 축에 끼우면 둘은 같은 방향으로, 같은 각속도로 돈다(각속도는 회전한 각을 걸린 시간으로 나눈 값이다). 이 연결에는 두 가지 방식이 있다.

  • (방식 A) 서로 맞닿는 면의 색이 같다. 두 면이 모두 흰색이든 모두 검은색이든 상관없다.
  • (방식 a) 서로 맞닿는 면의 색이 다르다. $x$의 검은 면이 $y$의 흰 면에 닿든 그 반대든 상관없다.

• 톱니로 연결: 톱니바퀴 $x$와 $y$를 톱니끼리 맞물리면 둘은 서로 반대 방향으로 돌며, 두 바퀴의 톱니(가장자리) 속력의 크기가 같아진다. 이 연결에도 두 가지 방식이 있다.

  • (방식 B) 맞물리는 접점을 지나 $x$에서 $y$로 넘어갈 때 색이 그대로 유지된다.
  • (방식 b) 맞물리는 접점을 지나 $x$에서 $y$로 넘어갈 때 색이 바뀐다. 흰색에서 검은색으로 바뀌든 검은색에서 흰색으로 바뀌든 상관없다.

여러 연결 방식의 예시를 그림에 나타내었다.

주어지는 기계 장치는 언제나 실제로 조립할 수 있다고 가정한다. 발명가들에게는 나름의 방법이 있어서, 예컨대 지름이 $1$인 톱니바퀴 하나를 지름이 $1$인 다른 수백 개의 톱니바퀴와 톱니로 맞물리게 하는 것도 가능하다. 이런 장치를 만드는 데 있어 그들에게 불가능이란 없다.

발명가는 아직 장치를 돌려보지 않았다. 막상 돌리면 작동하지 않을까 봐, 또 톱니바퀴들이 도는 속도가 적절할지 걱정된다. 그래서 장치의 도면을 너에게 건네주며 도움을 청했다. 처음에는 모든 톱니바퀴가 멈춰 있다. $1$번 톱니바퀴에 구동 장치를 연결했을 때 각 톱니바퀴의 각속도를 구하거나, $1$번 톱니바퀴가 돌 수 없음을 판정하여라. 구동 장치는 $1$번 톱니바퀴가 막혀 있지 않은 한 초당 $1$회전의 각속도로 돌게 한다.

아, 그리고 깜빡할 뻔했다! 그림을 그려 준 Dobrosia에게 감사를 전한다.

입력의 첫 줄에는 테스트 개수 $d$가 주어진다($1 \le d \le 100$). 그 뒤로 테스트들이 이어진다.

각 테스트는 하나의 기계 장치에 대응한다. 각 테스트의 첫 줄에는 톱니바퀴의 수 $n$과 그들 사이의 연결 수 $m$이 주어진다($1 \le n \le 1000$).

이어지는 $n$개의 줄에는 $i = 1 \ldots n$번 톱니바퀴의 지름이 차례로 주어진다. 톱니바퀴의 지름 $s_i$는 $1$ 이상 $100$ 이하의 정수이다.

그다음 $m$개의 줄에는 톱니바퀴 사이의 연결이 하나씩 주어진다. 각 연결은 서로 다른 두 톱니바퀴 번호 $x$, $y$($1 \le x, y \le n$)와 연결 방식을 나타내는 문자 a, b, A, B 중 하나로 이루어진다. 같은 톱니바퀴 쌍은 입력에 많아야 한 번 등장한다.

각 테스트마다 한 줄에, $1$번부터 $n$번까지 톱니바퀴의 각속도를 초당 회전수 단위로 출력한다. 단, $1$번 톱니바퀴가 돌 수 없으면 대신 그 줄에 NIE를 출력한다. 각 속도는 소수점 아래 정확히 둘째 자리까지 반올림하여(반올림은 반내림 없이 $0.5$는 올림) 출력하고, 한 줄의 값들은 공백 하나로 구분한다.