FRAKTAL - konkurs programistyczny

Def. Lider w zbiorze, to taka wartość, która występuje więcej razy niż połowa wszystkich jego elementów. Np. dla liczb 1, 1, 2, 1 liderem jest liczba 1, natomiast zbiór 1, 2, 2, 1, 3, 1 nie posiada lidera.

Wyobraźmy sobie macierz prostokątną n x m wypełnioną liczbami całkowitymi. Twoim zadaniem jest odpowiedzenie na pytanie, czy w podmacierzy kwadratowej o wymarach p x p znajduje się lider (0 < p ≤ min(n, m)). 

Wejście

W pierwszym wierszu trzy liczby całkowite n, m i p, określające wymiary macierzy. Liczby n i m mieszczą się w przedziale [2..1000].

W kolejnych n wierszach po m liczb całkowitych. Każda mieści się w przedziale [1..1 000 000].

Następnie jedna liczba q określająca liczbę zapytań (nie więcej niż 10⁵).

Każde zapytanie składa się z dwóch liczb x i y, wyznaczające współrzędne lewego górnego rogu podmacierzy (0 < x ≤ n - x, 0 < y ≤ m - y)

Wyjście

Dla każdego zapytania liczba, która jest liderem, jeśli lider istnieje w podmacierzy lub 0, gdy lidera nie ma.

Przykład

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

Wyjście:
1
0
2