Exotic Mechanical System

An underappreciated inventor has built an exotic mechanical system made of gears of assorted diameters. Every gear has a white side and a black side. The gears in the system can be joined in four ways:

• Joined by a shaft: gears $x$ and $y$ mounted on the same shaft turn in the same direction with the same angular velocity (angular velocity is the angle swept divided by the elapsed time). This can be done in two ways:

  • (Way A) The sides that face each other have the same colour. It makes no difference whether both facing sides are white or both are black.
  • (Way a) The sides that face each other have different colours. It makes no difference whether the black side of $x$ meets the white side of $y$ or the other way round.

• Joined by teeth: gears $x$ and $y$ meshed by their teeth turn in opposite directions, and the edge (tooth) speed of the two gears is equal in magnitude. This can also be done in two ways:

  • (Way B) Crossing from gear $x$ to gear $y$ through the contact point, the colour stays the same.
  • (Way b) Crossing from gear $x$ to gear $y$ through the contact point, the colour changes. It makes no difference whether it changes from white to black or from black to white.

Examples of the different kinds of joints are shown in the figure.

Assume the given system can always be built. Inventors have their tricks — for instance, meshing one gear of diameter $1$ with hundreds of other gears of diameter $1$. When it comes to building such systems, nothing is impossible for them.

The inventor has not yet started his system. He is afraid that when he tries to set it in motion it will not work, and he is unsure whether the gears will spin at suitable speeds. So he hands you the schematic and asks for help. Initially every gear is at rest. Compute the angular velocities of the gears once a drive is attached to gear number $1$, or determine that gear number $1$ cannot rotate. The drive makes gear $1$ spin at an angular velocity of $1$ rotation per second, provided gear $1$ is not blocked.

Oh — and I almost forgot! Thanks to Dobrosia for the figures.

The first line of input contains the number of test cases $d$ ($1 \le d \le 100$). The test cases follow.

Each test case describes one mechanical system. The first line of a test case contains the number of gears $n$ and the number of connections between them $m$ ($1 \le n \le 1000$).

The next $n$ lines give the diameters of gears $i = 1 \ldots n$ in order. The diameter $s_i$ of a gear is an integer between $1$ and $100$.

The next $m$ lines describe the connections between gears. Each connection consists of two distinct gear numbers $x$ and $y$ ($1 \le x, y \le n$) and a letter denoting the type of connection: a, b, A, or B. Any given pair of gears appears in the input at most once.

For each test case, print on a separate line the angular velocities of gears $1$ through $n$ in rotations per second; if gear number $1$ cannot rotate, print the word NIE on that line instead. Round each speed to exactly two digits after the decimal point (rounding halves up), and separate the values on a line with single spaces.