Zadania z V Warmińsko-Mazurskich Zespołowych Zawodów Programistycznych

Stacja telefoniczna ma 2K wejść, tyle samo wyjść i P warstw komutatorów. Każda warstwa składa się z K komutatorów, które łączą parę linii wejściowych z parą linii wyjściowych. Każdy komutator może się znajdować w jednym z dwóch stanów: X lub =.

W stanie X komutator łączy linie wejściowe z liniami wyjściowymi „na krzyż”. W stanie = zaś równolegle.

Linie wejściowe oraz wyjściowe numerowane są od 1 do 2K.

Na wejściu każdy komutator ma dwie kolejne linie: pierwszy komutator ma linie 1 i 2, drugi 3 i 4 i tak dalej. Wyjścia z komutatorów mogą zostać podpięte do dowolnych linii.

Na rysunku przedstawiona jest trójwarstwowa stacja. Po lewe stronie są linie wejściowe, po prawej — wejściowe. Warstwy komutatorów zaznaczone są na szaro. Komutatory pierwszej warstwy mają odpowiednio stany  X, =, X, =. Komutatory drugiej warstwy mają stany =, =, X, X. Stany komutatorów trzeciej warstwy to =, X, X, X. Takie ustawienie komutatorów realizuje połączenia 1-8, 2-1, 3-2, 4-7, 5-6, 6-4, 7-3, 8-5.

Napisz program, który na podstawie pożądanych połączeń określa stany wszystkich komutatorów tak, żeby stacja telefoniczna zrealizowała te połączenia.

Input

W pierwszej linijce wejście jest liczba testów. Dalej, dla każdego testu dane są w blokach: W pierwszej linijce bloku podane są dwie liczby naturalne: P — ilość warstw oraz K — połowa ilości wejść/wyjść. W następnej linijce podane są 2K liczb naturalnych A(1), A(2), ..., A(2K), określających pożądane połączenia: wejście i należy połączyć z wyjściem A(i), i=1,...2K. Kolejne P-1 linii stanowią opisanie poszczególnych warstw. Każda linia zawiera 2K liczb naturalnych: B(1), ... B(2K), co oznacza, że w tej warstwie przy stanie = wszystkich komutatorów wejście i zostanie połączone z wejściem B(i). W ostatniej warstwie wyjściami są linie wejściowe, które są numerowane od 1 do 2K i nie wymagają opisania. Ograniczenia: 0<P≤4, 0<K≤10.

Output

Na wyjściu dla każdego testu trzeba podać stany poszczególnych komutatorów. Każda warstwa w oddzielnej linijce. Jeżeli testowe zadanie nie ma rozwiązań, trzeba wyświetlić "noway" (bez cudzysłowu). Jeżeli zadanie ma wiele rozwiązań, należy wyświetlić tylko jedno.

Example

Pierwszy test ilustruje stację z rysunku.

Input:
2
3 4
8 1 2 7 6 4 3 5
1 5 3 7 2 6 4 8
1 3 2 4 5 7 6 8
3 4
8 1 2 7 6 4 3 5
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

Output:
X=X=
==XX
=XXX
noway