Fişierul intrare/ieşire:	piata.in, piata.out	Sursă	OJI 2008, clasa a 10-a
Autor	Doru Popescu Anastasiu	Adăugată de	Florian Marcu •Florian
Timp execuţie pe test	0.025 sec	Limită de memorie	4736 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Piata

Ionut pleaca la sfarsit de saptamana sa se relaxeze intr-un parc de distractii. La intrarea in parc se afla o piata mare, pavata cu placi de marmura de aceeasi dimensiune. Fiecare placa are scris pe ea un singur numar dintre f(1), f(2), f(3), . . . , f(n), unde f(k) este suma cifrelor lui k, pentru k din multimea { 1 , 2 , . . ., n }. Piata are forma unui tablou bidimensional cu n linii si n coloane. Placile care alcatuiesc piata sunt asezate astfel:

• pe prima linie sunt placi cu numerele f(1) , f(2) , ..., f(n-2), f(n-1) , f(n) (in aceasta ordine de la stanga la dreapta);
• pe linia a doua sunt placi cu numerele f(n) , f(1) , f(2) , f(3) , ..., f(n-1) , (in aceasta ordine de la stanga la dreapta);
• pe linia a treia sunt placi cu numerele f(n-1) , f(n) , f(1) , f(2) , f(3) , ..., f(n-2) (in aceasta ordine de la stanga la dreapta);
  ...
• pe ultima linie sunt placi cu numerele f(2) , ..., f(n-2) , f(n-1) , f(n) , f(1) (in aceasta ordine de la stanga la dreapta).

Parintii lui Ionut vor ca si in aceasta zi, fiul lor sa rezolve macar o problema cu sume. Astfel acestia ii propun lui Ionut sa determine suma cifrelor numerelor aflate pe portiunea dreptunghiulara din piata avand colturile in pozitiile in care se gasesc asezati ei. Tatal se afla pe linia iT si coloana jT (coltul stanga-sus), iar mama pe linia iM si coloana jM (coltul dreapta-jos). Portiunea din piata pentru care se doreste suma este in forma dreptunghiulara, cu laturile paralele cu marginile pietei. Daca Ionut va calcula suma ceruta, atunci el va fi recompensat in parcul de distractii, de catre parintii lui.

Date de intrare

Fisierul de intrare piata.in contine pe prima linie numarul natural n reprezentand dimensiunea pietei. Pe linia a doua se afla despartite printr-un spatiu numerele naturale iT si jT. Pe linia a treia se afla despartite printr-un spatiu numerele naturale iM si jM .

Date de iesire

In fisierul de iesire piata.out va contine pe prima linie suma ceruta.

Restrictii

• 2 ≤ n ≤ 40000.
• 1 ≤ iT , jT , iM , jM ≤ n .
• iT ≤ iM .
• jT ≤ jM .
• Suma ceruta de parintii lui Ionut nu depaseste niciodata valoarea 2100000000 .
• 20% din teste au n ≤ 250 .
• 30% din teste au 250 ≤ n ≤ 10000 .
• 30% din teste au 10001 ≤ n ≤ 28000 .
• 20% din teste au 28001 ≤ n ≤ 40000 .

Exemplu

Cum se trimit solutii?