Programowanie i algorytmy

Klucznik

Muszę otworzyć dziś drzwi, za którymi znajduje się coś specjalnego. W ręku mam zestaw kluczy - co najmniej jednym z nich mogę je otworzyć. Niestety jest ciemno i jestem prawie pewien, że klucz, który będzie pasował, wybiorę jako ostatni. Sprawdź to!

Wejście

W pierwszym wierszu znajdują się liczby n i m określające wymiary macierzy przedstawiającej zamek (n < 101, m < 101). Macierz składa się wyłącznie z zer i jedynek. Zbiór jedynek oznacza, że w tym miejscu jest dziurka. W zamku jest tylko jedna dziurka do klucza oraz co najmniej jedna jedynka.

Następnie n wierszy po m kolumn reprezentujących zamek.

W kolejnym wierszu jedna niewielka liczba określająca liczbę kluczy do sprawdzenia.

Specyfikacja każdego klucza (klucz zdefiniowany jest w pewnym układzie współrzędnych, który może być obrócony o krotność dziewięćdziesięciu stopni):

W pierwszym wierszu jedna liczba w określająca ilość współrzędnych klucza (w < 10001).

W kolejnych w wierszach po dwie współrzędne x i y, takie że |x| < 1000, |y| < 1000. Współrzędne są unikatowe i nie są posortowane.

Wyjście

Dla każdego klucza napis pasuje lub napis nie pasuje w zależności od sytuacji. 

Uwaga! Klucz musi idealnie pasować do dziurki - każda 'jedynka' z zamka musi mieć odpowiadającą sobie współrzędną klucza (być może obróconego).

Przykład

Wejście:
6 7
0000000
0011100
0110110
0011100
0001100
0000000
2
10
0 2
-1 1
0 1
1 1
-2 0
-1 0
1 0
-2 -1
-1 -1
0 -1
12
0 2
-1 1
0 1
1 1
-2 0
-1 0
1 0
-2 -1
-1 -1
0 -1
1 -1
0 -2

Wyjście:
nie pasuje
pasuje

Szkic rozwiązania

Przykładowe rozwiązanie. „Wycinamy” prostokąt w którym znajduje się klucz. Wykonujemy jego cztery wersje, obracając każdą o kolejne 90 stopni. Dla danego układu współrzędnych reprezentujących klucz wykonujemy translację do pierwszej ćwiartki tak, aby najbardziej wysunięty punkt na lewo leżał na osi OX a najbardziej wysunięty punkt w dół leżał na osi OY. W ostatnim kroku dopasowujemy wycięty prostokąt we wszystkich czterech wersjach do układu współrzędnych.