În ţara Sorelui Răsare există o tablă de bowling ce conţine NxM pătrăţele dispuse pe N linii şi M coloane, numerotate de la 1 la N şi de sus în jos, respectiv de la 1 la M şi de la stânga la dreapta. Un grup de copii trebuie să aşeze mai multe popice pe tablă într-o zonă dreptunghiulară în care fiecare pătrăţel va conţine câte un popic. Fiecare copil are dreptul să îşi exprime opţiunea referitor ori la o singură linie ori la o singură coloană. El va spune dacă doreşte ca aceasta să conţină sau nu popice. Pot exista mai mulţi copii care îşi exprimă opţiunea pentru aceeaşi linie sau pentru aceeaşi coloană.
Cerinţă
Cunoscându-se opţiunile copiilor, să se determine poziţia ideală a zonei pe tablă astfel încât numărul de copii nemulţumiţi să fie minim. Cum pot exista mai multe soluţii, să se identifice o zonă de arie maximă. Dacă şi în această situaţie există mai multe soluţii atunci se determină zona dreptunghiulară care are suma indicilor colţului stânga-sus minimă.
Date de intrare
Fişierul de intrare popic.in conţine pe prima linie numerele naturale N şi M, separate printr-un spaţiu reprezentând numărul de linii, respectiv numărul de coloane de pe tablă. Pe cea de a doua linie este scris un număr natural L ce reprezintă numărul de copii care şi-au exprimat opţiunile referitoare la linii. Pe fiecare dintre următoarele L linii din fişier se găsesc perechi de numere naturale x y, separate printr-un spaţiu, cu semnificaţia: pentru linia x opţiunea este y, unde y este 0 dacă nu vrea să existe popice pe linia x şi 1 în caz contrar. Pe următoarea linie este scris un număr C ce reprezintă numărul de copii care au făcut opţiuni referitoare la coloane. Pe fiecare dintre următoarele C linii din fişier se găsesc perechi de numere naturale x y, separate printr-un spaţiu, cu semnificaţia: pentru coloana x opţiunea este y, unde y este 0 dacă nu vrea să existe popice pe coloana x şi 1 în caz contrar.
Date de ieşire
Fişierul de ieşire popic.out va conţine o singură linie pe care se vor afla patru numere naturale a b c d, separate prin câte un spaţiu, reprezentând numărul liniei respectiv al coloanei colţului stânga-sus (a b) şi numărul liniei respectiv al coloanei colţului dreapta-jos (c d) al zonei dreptunghiulare alese.
Restricţii
• 1 ≤ N, M ≤ 50000
• 1 ≤ L, C ≤ 100000
• Copiii sunt obligaţi să aşeze cel puţin un popic pe tablă.
Exemple
popic.in
popic.out
Explicaţii
4 5
5
4 0
1 0
3 1
4 1
4 1
5
2 1
3 1
4 0
5 0
4 0
2 1 4 3
Figura de mai jos corespunde soluţiei din exemplu:
3 3
3
1 0
2 0
3 0
3
1 0
2 0
3 0
1 1 1 1
Figura de mai jos corespunde soluţiei din exemplu:
