Paski to gra dwuosobowa. Rekwizytami potrzebnymi do gry są plansza i prostokątne paski w trzech kolorach: czerwonym, zielonym i niebieskim. Wszystkie paski czerwone mają wymiary c x 1, zielone z x 1, a niebieskie n x 1, gdzie c, z i n są liczbami naturalnymi. Gracze dysponują nieograniczoną pulą pasków każdego koloru.

Plansza do gry jest prostokątem o wymiarach p x 1 i składa się z p pól o wymiarach 1 x 1.

Gracze wykonują ruchy na przemian. Ruch polega na ułożeniu na planszy paska dowolnego koloru. Obowiązują przy tym następujące zasady:

• pasek nie może wystawać poza planszę,
• nie wolno przykrywać (nawet częściowo) pasków ułożonych wcześniej,
• końce paska muszą pokrywać się z brzegami pól planszy. Przegrywa gracz, który jako pierwszy nie może wykonać ruchu zgodnie z zasadami gry.

Pierwszy gracz to ten, który wykonuje pierwszy ruch w grze. Mówimy, że pierwszy gracz ma strategię wygrywającą, jeżeli niezależnie od posunięć drugiego gracza może zawsze wygrać.

Zadanie

Napisz program, który

• wczyta z pliku tekstowego PAS.IN wymiary pasków i co najmniej jednej planszy,
• dla każdej planszy stwierdzi, czy pierwszy gracz posiada strategię wygrywającą,
• zapisze wyniki w pliku tekstowym PAS.OUT.

Wejście

Pierwszy wiersz pliku wejściowego PAS.IN zawiera trzy liczby naturalne c, z i n, 1 <= c, z, n <= 1000, równe długościom pasków, odpowiednio, czerwonych, zielonych i niebieskich. Liczby w wierszu są pooddzielane pojedynczymi znakami odstępu.

Drugi wiersz pliku PAS.IN zawiera jedną liczbę m, 1 <= m <= 1000, równą liczbie różnych plansz do rozpatrzenia. Wiersze od 3 do m+2 zawierają po jednej liczbie p, 1 <= p < 1000. Liczba w wierszu i + 2 jest długością i-tej planszy.

Wyjście

Plik wyjściowy PAS.OUT powinien zawierać m wierszy. W i-tym wierszu pliku powinna być zapisana tylko jedna liczba:

• 1 - jeżeli pierwszy gracz ma strategię wygrywającą dla i-tej planszy,
• 2 - w przeciwnym przypadku.

Przykład

Dla pliku wejściowego PAS.IN:

1 5 1
3 
1 
5 
6

poprawną odpowiedzią jest plik wyjściowy PAS.OUT

1
1 
2