În satul vecin există un teren agricol de formă dreptunghiulară împărțit în N*M pătrate elementare identice, dispuse alăturat câte M pe fiecare rând şi câte N pe fiecare coloană. Rândurile sunt numerotate de la 1 la N, iar coloanele de la 1 la M. Un pătrat elementar situat în teren pe rândul R și coloana C este identificat prin coordonatele (R,C).

Suprafețe dreptunghiulare din teren (formate fiecare din unul sau mai multe pătrate elementare alăturate) sunt revendicate de T fermieri din sat, în calitate de moștenitori, pe baza actelor primite de la strămoșii lor. Pentru că au apărut și acte false, s-a constat că pot exista mai mulți fermieri care revendică aceleași pătrate elementare.

În cele T acte ale fermierilor, suprafețele dreptunghiulare sunt precizate fiecare prin câte două perechi de numere (X,Y) și (Z,U), reprezentând coordonatele primului pătrat elementar din colțul stânga-sus al suprafeței (rândul X și coloana Y), respectiv coordonatele ultimului pătrat elementar situat în colțul dreapta-jos al suprafeței (rândul Z și coloana U).

Cerinţe

Scrieţi un program care să citească numerele naturale N, M, T, R, C apoi cele T perechi de coordonate (X,Y) și (Z,U) precizate în acte (corespunzătoare suprafețelor dreptunghiulare revendicate) și care să determine:

1. numărul fermierilor care revendică pătratul elementar identificat prin coordonatele (R,C);
2. numărul maxim de fermieri care revendică același pătrat elementar;
3. numărul maxim de pătrate elementare ce formează o suprafață pătratică nerevendicată de niciun fermier.

Date de intrare

Fişierul teren.in conţine pe prima linie un număr natural P care poate avea doar valoarea 1, valoarea 2 sau valoarea 3. Pe a doua linie a fișierului sunt scrise cinci numere naturale N, M, T, R, C, separate prin câte un spaţiu, cu semnificaţia din enunţ. Pe fiecare din următoarele T linii ale fișierului sunt câte patru numere naturale nenule XK, YK, ZK, UK, separate prin câte un spaţiu, reprezentând perechile de coordonate (XK,YK) și (ZK,UK) corespunzătoare terenurilor revendicate de cei T fermieri (1 ≤ K ≤ T).

Date de ieșire

Fişierul de ieşire teren.out va conţine pe prima linie un număr natural reprezentând numărul fermierilor care revendică pătratul elementar identificat prin coordonatele (R,C) dacă cerința a fost 1, un număr natural reprezentând numărul maxim de fermieri ce revendică același pătrat elementar dacă cerința a fost 2, respectiv un număr natural reprezentând numărul maxim de pătrate elementare ce formează o suprafață pătratică nerevendicată de niciun fermier dacă cerința a fost 3.

Restricții și precizări

• 3 ≤ N, M ≤ 180; 3 ≤ T ≤ 100; 1 ≤ R ≤ N; 1 ≤ C ≤ M;
• 1 ≤ XK ≤ ZK ≤ N şi 1 ≤ YK ≤ UK ≤ M pentru K=1,2,3,...,T;
• Pentru rezolvare corectă a cerinţei 1 se acordă 20% din punctaj, pentru rezolvarea corectă a cerinţei 2 se acordă 20% din punctaj, iar pentru rezolvarea corectă a cerinței 3 se acordă 60% din punctaj.

Exemplul 1

teren.in

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

teren.out

2

Explicație

Pătratul elementar cu coordonatele R=2 și C=2 este revendicat de 2 fermieri.

Exemplul 2

teren.in

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

teren.out

3

Explicație

Pătratul elementar cu coordonatele (2,3) este revendicat de 3 fermieri (numărul maxim de revendicări).

Exemplul 3

teren.in

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

teren.out

4

Explicație

Sunt două suprafețe pătratice nerevendicate de niciun fermier, formate fiecare din numărul maxim de patru pătrate elementare. Acestea au coordonatele: (1,4) și (2,5) respectiv (2,4) și (3,5).

#include <bits/stdc++.h>
using namespace std;

ifstream cin("teren.in");
ofstream cout("teren.out");

int a[200][200] , n , m , t , r , c , x1 , x2 , y1 , y2 , cer , lmax , b[200][200];

void umplere(int x1 , int y1 , int x2 , int y2)
{
    for(int i = x1 ; i <= x2 ; i++)
        for(int j = y1 ; j <= y2 ; j++)
            a[i][j]++;
}

int main()
{
    cin >> cer;
    cin >> n >> m >> t >> r >> c;
    for(int i = 1 ; i <= t ; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        umplere(x1 , y1 , x2 , y2);
    }
    /*for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
            cout << a[i][j] << " ";
            cout << '\n';
    }*/
    if(cer == 1) cout << a[r][c];
    else if(cer == 2)
    {
        int maxi = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            for(int j = 1 ; j <= m ; j++)
                if(a[i][j] > maxi) maxi = a[i][j];
        }
        cout << maxi;
    }
    else
    {
        for(int i = 1 ; i <= n ; i++)
        {
            for(int j = 1 ; j <= m ; j++)
                if(a[i][j] == 0)
                {
                    b[i][j] = min(min(b[i][j-1] , b[i-1][j]) , b[i-1][j-1]) + 1;
                    lmax = max(lmax, b[i][j]);
                }
        }
        cout << lmax*lmax;
    }

}