E - Uporządkowany NIM 3

Uporządkowany NIM to gra dwuosobowa. Grę stanowi rząd [asciimath]n[/asciimath] stosów kamieni. W [asciimath]i[/asciimath]-tym stosie znajduje się  [asciimath]a_i[/asciimath] kamieni. Stosy są uporządkowane od lewej do prawej strony, gdzie [asciimath]a_1[/asciimath] to rozmiar pierwszego stosu od lewej strony. Gracze wykonują swoje ruchy na przemian. Pojedynczy ruch polega na wybraniu pierwszego niepustego stosu po lewej stronie i usunięciu z niego dowolnej niezerowej liczby kamieni. Wygrywa ten, kto usunie ostatni kamień w grze.

Ola z Mariuszem postanowili zagrać w Uporządkowany Nim w więcej osób. Wprowadzili następujące zmiany w zasadach gry:

  • W Uporządkowany Nim gra [asciimath]g[/asciimath] graczy wykonując swoje ruchu po kolei (po graczu o numerze [asciimath]g[/asciimath] ruch ma znowu gracz o numerze [asciimath]1[/asciimath]). Zwycięzcą gry jest gracz, który usunie ostatni kamień w grze.
  • Gracz o numerze [asciimath]i[/asciimath] może w jednym ruchu usunąć co najwyżej [asciimath]m_i[/asciimath] kamieni.

Ola z Mariuszem chcą zaprosić do gry swoich znajomych. Zanim jednak to zrobią, chcieliby wiedzieć, kto ma strategię wygrywającą w zależności od tego, który gracz będzie zaczynał grę. Dla każdego gracza znana jest lista preferowanych zwycięzców. Dla ustalonego gracza lista [asciimath]p_1, ... , p_g[/asciimath] oznacza, że ten gracz:

  • jeżeli jest to możliwe, gracz wykona taki ruch, żeby wygrał gracz o numerze [asciimath]p_1[/asciimath]
  • jeżeli powyższe nie jest możliwe, to gracz wykona taki ruch, żeby wygrał gracz o numerze [asciimath]p_2[/asciimath]
  • ...
  • jeżeli powyższe nie jest możliwe, to gracz wykona taki ruch, żeby wygrał gracz o numerze [asciimath]p_(g-1)[/asciimath]
  • jeżeli powyższe nie jest możliwe, to gracz wykona taki ruch, żeby wygrał gracz o numerze [asciimath]p_g[/asciimath]

Lista preferencji wszystkich graczy znana jest wszystkim graczom.

Wejście

W pierwszej linii znajduje się liczba graczy [asciimath]g (2<=g<=4)[/asciimath].

W drugiej linii znajduje się ciąg liczb [asciimath]m_1, ... , m_g[/asciimath] [asciimath](1 <= m_i <= 1000)[/asciimath]. [asciimath]m_i[/asciimath] to maksymalna liczba kamieni, jaką w pojedynczym ruchu może zabrać gracz o numerze [asciimath]i[/asciimath].

W kolejnych [asciimath]g[/asciimath] liniach znajdują się listy preferowanych zwycięzców. [asciimath]i[/asciimath]-ta linia w kolejności to permutacja liczb od [asciimath]1[/asciimath] do [asciimath]g[/asciimath]. Jest to lista preferowanych zwycięzców gry dla gracza o numerze [asciimath]i[/asciimath].

W kolejnej linii znajduje się liczba zestawów testowych (gier) [asciimath]t (1<=t<=100) [/asciimath]. Na każdy zestaw składają się dwie linie wejścia.

W pierwszej linii zestawu testowego znajduje się liczba [asciimath]n (1<=n<=10000)[/asciimath]. Jest to liczba stosów.

W drugiej linii zestawu testowego znajduje się [asciimath]n[/asciimath] liczb [asciimath]a_1,...,a_n (1<=a_i<=1000)[/asciimath]. Są to rozmiary stosów.

Wyjście

Dla każdego zestawu testowego należy wypisać ciąg [asciimath]g[/asciimath] liczb. [asciimath]i[/asciimath]-ta liczba w ciągu oznacza numer gracza, który wygra grę, pod warunkiem, że grę zacznie gracz o numerze [asciimath]i[/asciimath].

Przykład

Wejście:
3
2 2 2
1 3 2
2 3 1
1 3 2
2
2
3 5
5
1 2 3 2 1

Wyjście:
3 1 1
1 1 1

Objaśnienie przykładu:

Każdy gracz może wziąć w jednym ruchu co najwyżej 2 kamienie. Gracz 1 i 3 mają takie same listy i grają tak, żeby wygrał gracz o numerze 1. Gracz numer 2 będzie grał tak, żeby wygrał on sam, a jeżeli jest to niemożliwe, to gracz o numerze 3.

Pierwsza gra przy założeniu, że zaczyna gracz 1, będzie wyglądać tak:

  • Gracz 1 bierze 2 kamienie z pierwszego stosu. Zostaje "1 5".
  • Gracz 2 musi wziąć 1 kamień z pierwszego stosu. Zostaje "0 5".
  • Gracz 3 bierze 1 kamień z drugiego stosu (gdyby wziął dwa to wygrałby gracz 2). Zostaje "0 4".
  • Gracz 1 bierze 1 kamień z drugiego stosu. Zostaje "0 3".
  • Gracz 2 nie jest w stanie wziąć pozostałych 3 kamieni. Może wziąć 1 lub 2 kamienie. Jeżeli weźmie 1, to znając listę preferencji trzeciego gracza, wie że trzeci gracz weźmie wtedy 1 kamień i wygra gracz 1. Lepiej jest wziąć 2 kamienie, żeby grę wygrał gracz 3. Zostaje "0 1".
  • Gracz 3 bierze ostatni kamień i wygrywa grę.

Please log in to submit your solution.