Pewien niedoceniany wynalazca zbudował egzotyczny układ mechaniczny, składający się z kół zębatych o zróżnicowanych średnicach. Każde koło zębate ma stronę białą i stronę czarną. Koła zębate wchodzące w skład egzotycznego układu mechanicznego mogą być łączone na cztery sposoby:</p>

• Koła x i y mogą być połączone osiami — wtedy obracają się one w tym samym kierunku, a ich prędkość kątowa jest taka sama (prędkość kątowa to stosunek wartości przebytego kąta do czasu). Połączenia tego można dokonać na dwa sposoby:
  • (Sposób A) Naprzeciw siebie są strony kół zębatych o tych samych kolorach. Nie ma znaczenia, czy naprzeciw siebie są kolory białe, czy czarne.
  • (Sposób a) Naprzeciw siebie są strony kół zębatych o różnych kolorach. Nie ma znaczenia, czy strona czarna koła x została połączona ze stroną białą koła y, czy też odwrotnie.
  </li>
• Koła zębate x i y mogą być połączone zębatkami — wtedy obracają się one w przeciwnych kierunkach, a prędkości wszystkich zębów obu kół są identyczne co do wartości. Połączenia tego można dokonać na dwa sposoby:
  • (Sposób B) Przy przejściu z zębatki x na zębatkę y przez punkt styku zębatek, kolor pozostaje ten sam.
  • (Sposób b) Przy przejściu z zębatki x na zębatkę y przez punkt styku zębatek, kolor ulega zmianie. Nie ma znaczenia, czy kolor zmienia się z białego na czarny, czy z czarnego na biały.
  </ul> </li> </ul>

  Przykładowe połączenia różnych typów zobrazowano na rysunku.

  

  Zakładamy, że dany egzotyczny układ mechaniczny zawsze da się zbudować. Niedoceniani wynalazcy mają swoje sposoby, aby np. połączyć zębatkami koło zębate o średnicy 1 z setkami innych kół zębatych o średnicy 1. W kwestii budowania egzotycznych układów mechanicznych nie ma dla nich rzeczy niemożliwych.

  Niedoceniany wynalazca nie uruchomił jeszcze swojego egzotycznego układu mechanicznego. Boi się, że, gdy spróbuje wprawić go w ruch, układ nie zadziała. Nie wie też, czy prędkości, z jakimi będą się kręciły koła zębate, są odpowiednie. Dlatego niedoceniany wynalazca przekazał Tobie schemat swojego układu i poprosił o pomoc. Początkowo żadne koło zębate nie porusza się. Oblicz, jakie będą prędkości kątowe kół zębatych, gdy do koła zębatego nr 1 podłączony zostanie napęd, lub stwierdź, że koło zębate nr 1 nie może się obracać. Napęd powoduje, że, jeśli koło zębate nr 1 nie jest zablokowane, to kręci się z prędkością kątową o wartości 1 obrót na sekundę.

  A... i zapomniałbym! Za rysunki dziękujemy Dobrosi.

  입력 형식

  W pierwszej linii wejścia podana jest liczba testów d (1 ≤ d ≤ 100). Dalej podane są testy.</p>

  Każdy test odpowiada jednemu egzotycznemu układowi mechanicznemu. Pierwsza linia każdego testu zawiera liczbę kół zębatych n oraz liczbę połączeń pomiędzy nimi m (1 ≤ n ≤ 1000).

  W kolejnych n liniach podane są rozmiary kolejnych (i = 1..n) kół zębatych. Średnica koła zębatego si jest liczbą całkowitą z przedziału od 1 do 100.

  W kolejnych m liniach znajdują się opisy połączeń między kołami zębatymi. Opis połączenia składa się z dwóch różnych liczb x oraz y oznaczających numery kół zębatych (1 ≤ x, y ≤ n) oraz litery określającej sposób połączenia: ’a’, ’b’, ’A’ lub ’B’. Dana para numerów kół zębatych wystąpi na wejściu co najwyżej raz.

  출력 형식

  Dla każdego testu, wypisz w osobnej linii prędkości kątowe kolejnych kół zębatych lub słowo NIE. Prędkości podaj w liczbie obrotów na sekundę. Wynik zaokrąglij do dwóch cyfr po przecinku. Dla każdego koła zębatego możesz się pomylić o co najwyżej 0,01. Jeśli dla danego układu koło zębate nr 1 nie może się obracać, zamiast prędkości wypisz w osobnej linii słowo NIE.

  예제 입력

  3
  3 1
  1
  2
  3
  1 3 B
  3 2
  1
  2
  3
  1 3 A
  2 3 A
  3 3
  1
  2
  3
  1 2 B
  2 3 B
  1 3 B

  예제 출력

  1.00 0.00 0.33
  1.00 1.00 1.00
  NIE