Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_08_20 - Lider w macierzy

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ż 105).

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

Dodane przez:Marcin Kasprowicz
Data dodania:2017-11-27
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.