Kontekst zadania
Słynny matematyk John H. Conway (1937–2020) zmarł niestety podczas pandemii COVID-19. Jego zainteresowania badawcze obejmowały wiele dziedzin, takich jak gry kombinatoryczne czy teoria grup; wniósł istotny wkład w klasyfikację grup skończonych, automaty komórkowe oraz gry kombinatoryczne. Poświęcił się popularyzacji matematyki i zaprojektował „Grę w życie” (Conway's Game of Life), która zyskała światową sławę.
Dziś przypomnijmy sobie jeden z jego najsłynniejszych wynalazków.
Zasady Gry w życie są następujące:
- Istnieje kwadratowa siatka, w której każda komórka znajduje się w jednym z dwóch stanów: martwym lub żywym. Stan każdej komórki w następnej chwili jest jednoznacznie określony przez jej obecny stan oraz stan 8 sąsiadujących z nią komórek.
- Jeśli obecna komórka jest żywa i ma mniej niż 2 żywych sąsiadów (nie wliczając 2), staje się martwa.
- Jeśli obecna komórka jest żywa i ma 2 lub 3 żywych sąsiadów, pozostaje w tym samym stanie.
- Jeśli obecna komórka jest żywa i ma więcej niż 3 żywych sąsiadów, staje się martwa.
- Jeśli obecna komórka jest martwa i ma dokładnie 3 żywych sąsiadów, staje się żywa; w przeciwnym razie pozostaje martwa.
Treść zadania
Ze względu na ograniczenia pamięci komputera nie możemy symulować Gry w życie na nieskończonej siatce, dlatego rozważamy tylko siatkę $4\times 4$, przyjmując, że poza siatką komórki nie mogą być żywe.
Otrzymasz $Q$ zapytań, z których każde określa stan każdej komórki na siatce $4\times 4$. Twoim zadaniem jest określenie stanu każdej komórki na siatce po $T$ jednostkach czasu.
Wejście
Dane wczytywane są ze standardowego wejścia.
Pierwsza linia zawiera liczbę całkowitą $Q$, oznaczającą liczbę zapytań.
Następnie następuje $5Q$ linii, gdzie każde 5 linii opisuje jedno zapytanie.
W każdym zapytaniu pierwsze 4 linie zawierają ciąg znaków 01 o długości 4, reprezentujący stan komórek w siatce, gdzie 0 oznacza komórkę martwą, a 1 żywą. Kolejna linia zawiera liczbę całkowitą $T$, oznaczającą liczbę jednostek czasu, które mają upłynąć.
Wyjście
Dane wyprowadzane są na standardowe wyjście.
Należy wyprowadzić $4Q$ linii, gdzie każde 4 linie odpowiadają wynikowi jednego zapytania.
Wynik każdego zapytania to 4 linie, z których każda zawiera ciąg znaków 01 o długości 4, reprezentujący stan komórek w siatce, gdzie 0 oznacza komórkę martwą, a 1 żywą.
Przykład
Wejście 1
1 0000 1100 0110 0000 3
Wyjście 1
0100 1010 1010 0100
Uwagi 1
Po jednej jednostce czasu stan siatki zmienia się na:
0000 1110 1110 0000
Po kolejnej jednostce czasu stan siatki zmienia się na:
0100 1010 1010 0100
Następny stan będzie identyczny z tym stanem, co oznacza, że w kolejnych chwilach stan ten będzie się utrzymywał. Zatem po 3 jednostkach czasu od początku stan jest właśnie taki.
Przykład 2
Zobacz pliki ex_2.in oraz ex_2.ans w katalogu do pobrania.
Podzadania
Dla $100\%$ danych gwarantuje się, że $Q \le 10^{4}, T \le 10^{9}$.
| Test | $Q$ | $T$ |
|---|---|---|
| 1,2,3,4 | $= 10^{2}$ | $\le 10^{2}$ |
| 5,6,7 | $= 10^{3}$ | $\le 10^{3}$ |
| 8,9 | $= 10$ | $\le 10^{9}$ |
| 10 | $= 10^{4}$ |