W Megabajtolandii otworzono nowy salon gier. Do salonu przywieziono różne automaty do gier. Wśród nich były także różne automaty do gier typu “PinBall”. Jak wiadomo w Megabajtolandii nie żyją normalni ludzie, tylko algorytmiczni zboczeńcy. Z tego powodu nie grali oni w te gry, tak jak wszyscy normalni ludzie, odbijając kulki do góry. Dla nich sprawą priorytetową było szybkie ustalenie, gdzie spadnie kulka, jeśli puści się ją z odpowiedniego miejsca, w odpowiednim kierunku, z odpowiednią siłą. Jasiowi najbardziej spodobał się jeden z tych automatów. Gdy popatrzyło się na niego z góry, był kwadratowy i bardzo nowoczesny. Cały był podzielony na MxM pól. Jego nowoczesność polegała na tym, że na niektórych polach są umieszczone półki, które mają taką cechę, że jak spadnie na nią kulka, to zrzucają ją na swoje prawo lub lewo, a dodatkowo w momencie kontaktu kulki z tą półką zmienia ona swoje nachylenie i następna kulka, która spadnie na tę półkę, spadnie z drugiej strony. Wyjątkiem są skrajne półki, które nigdy nie zmieniają zwrotu i zawsze spuszczają kulkę tak, żeby ta nie wypadła z gry. Półki są poustawiane na zmianę, co drugi wiersz ma n i n-1 pól. Można to zobrazować następująco:

      - - -
       - -
      - - -
       - -
      - - -

Przy czym, każda półka jest na początku skierowana, co można zobrazować następująco:

      \ \ /
       / \
      \ \ /

Jaś ma do dyspozycji w grze pewną liczbę kulek. Zrzuca je z wybranych przez siebie miejsc. Bardzo chciałby dojść do tego, gdzie spadnie ostatnia zrzucona przez niego kulka.

Mając dany opis automatu oraz wiedząc gdzie Jaś zrzuca kolejne kulki, oblicz gdzie spadnie ostatnia kulka zrzucona przez Jasia.

W pierwszej linii wejścia znajduje się jedna dodatnia liczba całkowita, oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. Każdy zestaw ma następującą postać. W pierwszej linii znajdują się dwie liczby całkowite N i K (2 ≤ N ≤ 1.000, 1 ≤ K ≤ 250.000), które oznaczają odpowiednio liczbę półek w pierwszym rzędzie (liczbę małych kwadracików w wierszu (lub kolumnie), na który jest podzielony automat) oraz liczbę kulek, które Jaś spuści. W kolejnych K liniach zestawu znajdują się pojedyncze liczby całkowite mówiące, z którego miejsca Jaś zrzuca kolejne kulki. Liczby te są z przedziału od 1 do 2*N-1. W kolejnych N wierszach znajduje się opis tego, jak skierowane są półki. Każdy z tych wierszy zawiera na zmianę N i N-1 liczb, które są równe 1 (jeśli półka jest zwrócona w prawo) lub -1 (jeśli półka jest zwrócona w lewo). Pierwszy wiersz ma zawsze N liczb (tj. półek).

Dla każdego zestawu danych pojawiającego się na wejściu należy wypisać dokładnie jedną liczbę (każdą w osobnej linii), oznaczającą numer pola w ostatnim rzędzie licząc od lewej, na które spadnie ostatnia kulka.