Harta

Urod este un om politic de influență majoră. Într-o zi acesta a fost invitat de bunul său prieten Rodut pentru a mânca niște pizza pe insula sa privată. Urod, fiind un mare fan al insulelor private și al preparatelor cu temă italiană, a acceptat invitația și a luat un avion ca să poată ajunge pe insulă.

Apropiindu-se cu avionul de insulă, acesta a reușit să vadă că insula se aseamănă cu o matrice cu $N$ linii și $M$ coloane, cu $S$ atracții turistice (muzee de artă, restaurante de 5 stele, castele gonflabile etc.). Urod notează fiecare secțiune din insulă cu o pereche de numere întregi pozitive $(x, y)$, reprezentând celula de pe linia $x$ și coloana $y$.

Urod vrea să viziteze mai multe atracții înainte de masă, alegând un mod special de a le parcurge. Dacă se află în punctul $(a, b)$, va proceda astfel:

• Adună toate celulele $(x_i, y_i)$ cu atracții turistice într-o listă.
• Sortează lista — mai întâi după distanța Manhattan față de $(a,b)$, iar la distanțe egale după ordinea lexicografică a celulelor.
• Se mută la a $L$-a celulă din lista sortată (indexată de la $1$).

Ordinea în listă. O atracție $(x_i, y_i)$ apare înaintea atracției $(x_j, y_j)$ dacă:

Definiții folosite:

• $\mathrm{DistManhattan}\!\left((a,b),(c,d)\right) = |a-c| + |b-d|$, unde $|\cdot|$ este valoarea absolută.
• $(a,b)$ este lexicografic mai mică decât $(c,d)$ dacă $a < c$, sau $a = c$ și $b < d$.

Urod vrea să afle, pentru $Q$ celule de start $(qx_i, qy_i)$: în ce celulă s-ar muta după prima sa mutare?

Date de intrare

Fișierul harta.in conține:

• Linia 1: numerele întregi $N$, $M$, $S$, $L$.
• Următoarele $S$ linii: perechile $(x_i,\,y_i)$ — locațiile atracțiilor turistice.
• Linia $S{+}2$: numărul $Q$.
• Următoarele $Q$ linii: perechile $(qx_i,\,qy_i)$ — celulele de start.

Date de ieșire

Fișierul harta.out conține $Q$ linii. Pe linia $i$ se află perechea de numere (separate printr-un spațiu) reprezentând a $L$-a cea mai apropiată atracție turistică față de celula $(qx_i,\,qy_i)$.

Restricții și precizări

• $1 \le N, M \le 1 \ 000$
• $1 \le S \le N \cdot M$
• $1 \le L \le \min(12,S)$
• $1 \le x_i \le N$ și $1 \le y_i \le M$ pentru orice $1 \le i \le S$
• Nu există două atracții turistice în aceeași celulă.
• $1 \le Q \le N \cdot M$
• $1 \le qx_i \le N$ și $1 \le qy_i \le M$ pentru orice $1 \le i \le Q$

Exemplul 1

harta.in

3 3 3 2
1 1
2 2
3 3
3
2 1
2 3
3 3

harta.out

2 2
3 3
2 2

Exemplul 2

harta.in

4 5 4 1
2 4
4 5
4 2
1 2
4
3 1
3 3
2 3
1 3

harta.out

4 2
2 4
2 4
1 2

Explicații

Primul exemplu — matrice $3\times3$, atracții în $(1,1)$, $(2,2)$, $(3,3)$,
$L=2$:

Query $(2,1)$: Distanțele sunt $d(1,1)=1$, $d(2,2)=1$, $d(3,3)=3$. Deoarece $(1,1)$ și $(2,2)$ sunt la distanță egală, se aplică ordinea lexicografică: $(1,1)<_{\text{lex}}(2,2)$. Lista finală: $[(1,1),(2,2),(3,3)]$. $L=2 \Rightarrow$ răspuns: $(2,2)$.

Query $(2,3)$: Distanțele: $d(2,2)=1$, $d(3,3)=1$, $d(1,1)=3$. Egalitate între $(2,2)$ și $(3,3)$; $(2,2)<_{\text{lex}}(3,3)$. Lista finală: $[(2,2),(3,3),(1,1)]$. $L=2 \Rightarrow$ răspuns: $(3,3)$.

Query $(3,3)$: Startul este chiar o atracție, deci $d(3,3)=0$. Lista finală: $[(3,3),(2,2),(1,1)]$. $L=2 \Rightarrow$ răspuns: $(2,2)$.

Al doilea exemplu — matrice $4\times5$, $L=1$ (cea mai apropiată atracție):

• Start $(3,1)$: cea mai apropiată atracție este $(4,2)$ $\to$ răspuns: $(4,2)$.
• Start $(3,3)$: răspuns: $(2,4)$.
• Start $(2,3)$: răspuns: $(2,4)$.
• Start $(1,3)$: răspuns: $(1,2)$.

Ilustrație vizuală — Exemplul 1 ($3\times3$, $L=2$)