== include(page="template/taskheader" task_id="memcpy") ==

Fie o matrice de dimensiuni $1000x1000$ cu elemente distincte. Dorim ca în această matrice să copiem submatricea de dimensiuni $N x M$ care are colţul stânga sus în $(X, Y)$ peste submatricea de dimensiuni $N x M$ care are colţul stânga sus în $(NEW_X, NEW_Y)$. Este necesar ca acest lucru să se realizeze folosind $N x M$ atribuiri de tipul $A[x][y] = A[z][t]$. Sa se determine ordinea minima lexicografica in care pot fi făcute aceste atribuiri pentru a copia corect submatricea?

Fie o matrice de dimensiuni $1000x1000$ cu elemente distincte. Dorim ca în această matrice să copiem submatricea de dimensiuni $N x M$ care are colţul stânga sus în $(X, Y)$ peste submatricea de dimensiuni $N x M$ care are colţul stânga sus în $(NEW_X, NEW_Y)$. Este necesar ca acest lucru să se realizeze folosind $N x M$ atribuiri de tipul $A[x][y] = A[z][t]$. Să se determine ordinea minima lexicografica in care pot fi făcute aceste atribuiri pentru a copia corect submatricea.

h2. Date de intrare

h2. Date de ieşire

Hash-ul e ceva de genu:

Fişierul de ieşire $memcpy.out$ va conţine o singură valoare naturală, $hash$, care va fi determinată în felul următor:

hash = 0, mod = 1e9 + 7;

==code(cpp) |

for(int i = 0; i < all; ++i) {
    hash += 1LL * i * ans[i].first * ans[i].second % mod;

int hash = 0, mod = 1e9 + 7;
for(int i = 1; i <= n * m; ++i) {
    hash += 1LL * i * raspuns[i].x * raspuns[i].y % mod;

    hash %= mod;
}

==

În fişierul de ieşire $memcpy.out$ ar trebui in mod normal sa contina $NxM$ linii, fiecare conţinând câte o pereche de numere. Dacă linia $i$ conţine perechea $(a{~i~}, b{~i~})$ atunci celula cu coordonatele $(a{~i~}, b{~i~})$ va fi copiată la momentul $i$. Se observă că destinaţia de copiere pentru această celulă este unică. În consecinţă, nu va fi specificată. Datorita numarului mare de afisari vom inlocui aceste numere cu un singur numar ca se va afla astfel: vom porni de la $MOD = 1.000.000.007$. Se va face suma din $i * a{~i~} * b{~i~}$ si se va afisa aceasta valoare $modulo MOD$.

Unde $răspuns[i]$ conţine coordonatele celulei care va fi copiată în operaţia cu numărul $i$.

h2. Restricţii

* $1 ≤ N, M ≤ 500$

* $1 ≤ N, M ≤ 1000$

* $Toate coordonatele citite sau afişate se vor afla în intervalul [1, 1000].$
* $Submatricele descrise în input vor fi incluse complet în matrice.$

table(example). |_. memcpy.in |_. memcpy.out |
|  4 4 1 1 2 2

| 758 |

| 858
|

h3. Explicaţie

...
 

Celulele vor fi copiate în această ordine: (1, 4); (2, 4); (1, 3); (3, 4); (2, 3); (1, 2); (4, 1); (4, 2); (3, 1); (4, 3); (3, 2); (2, 1); (4, 4); (3, 3); (2, 2); (1, 1).

== include(page="template/taskfooter" task_id="memcpy") ==

9615