Miruna s-a decis recent să intre în afacerile cu petrol. Ea doreşte să construiască o platformă petrolieră pe Marea Albă. Această mare este foarte interesantă deoarece are forma unui dreptunghi de dimensiuni N şi M, putând fi astfel reprezentată sub forma unei matrice. Pentru fiecare zonă reprezentată de către un element al matricei, se cunoaşte adâncimea apei mării în zona respectivă. Platforma pe care Miruna doreşte să o construiască trebuie sa aibă dimensiunile A şi B. Deoarece pilonii necesari construcţiei costă foarte mult, se doreşte minimizarea adâncimii maxime a unei zone unde va urma să se construiască platforma.
Cerinţă
Dându-se o matrice cu N linii şi M coloane reprezentând Marea Albă, determinaţi o submatrice de dimensiuni A şi B - poziţia de construcţie a platformei - astfel încât elementul maxim din submatrice să fie cât mai mic.
Date de intrare
Fişierul de intrare platforma.in conţine pe prima linie patru numere naturale N, M, A şi B. Pe urmatoarea linie se vor afla M numere întregi reprezentând prima linie a matricei care codifică fundul mării. Pentru a afla celelalte elemente ale matricei veţi folosi formula: Element[i][j]=(Element[i-1][j]*i)% 666013, i>1 (atenţie la generarea numerelor, aveţi nevoie de întregi pe 64 de biţi).
Date de ieşire
Fişierul de ieşire platforma.out va conţine un singur număr natural, reprezentând adâncimea maximă a zonei deasupra căreia va trebui să fie construită platforma.
Restricţii
1 <= N, M <= 1000
1 <= A <= N
1 <= B <= M
Adâncimea maximă a mării nu depăşeşte 666013
Exemplu
platforma.in
platforma.out
Explicaţii
2 4 2 2
1 2 3 4
4
Fundul mării arată astfel: 1 2 3 4
2 4 6 8
Andrei Grigorean
Facultatea de Matematică şi Informatică, Universitatea din Bucureşti