Problem 617: Sniper

Într-o matrice $N$ x $N$ avem toate numerele de la $1$ la $N^2$ . Se consideră următorul procedeu prin care se scot pe rând elementele din matrice și se așează într-o permutare: un sniper lovește unul dintre cele $4$ colțuri ale matricei. Se parcurge diagonala/semidiagonala matricei care pleacă din acel colț. Elementele se adaugă la finalul permutării în ordinea parcurgerii. Elementele parcurse se elimină din matrice, iar cele rămase se deplasează vertical sau orizontal, reformând o nouă matrice care ”a pierdut” o linie sau o coloană. O deplasare se poate face la alegere orizontal sau vertical. După lovitura de sniper și deplasarea pe orizontală sau verticală, elementele rămase trebuie să formeze în continuare o matrice!

Cerință

Să se determine a $P$ -a permutare de dimensiune $N^2$ în ordine lexicografică care se poate obține folosind procesul descris mai sus.

Atenție!

Datorită dimensiunilor mari ale matricei, datele vor fi generate conform programului pe care concurenții îl vor primii in workspace, în funcția main aflându-se un exemplu de input/output.

Date de intrare

Pe prima linie se află numerele $N$ , $P$ și $Seed$ . Dacă $Seed = 0$ , fiecare din următoarele $N$ linii conține $N$ numere naturale, altfel numerele vor fi generate conform algoritmului din anexă, și se pot accesa folosind funcția ReadPerm(N).

Date de ieșire

Dacă $seed = 0$ , atunci se vor afișa pe o singură linie $N^2$ numere reprezentând a $P$ -a permutare în ordine lexicografică ce se poate obține, altfel se va afișa o singură valoare ce se calculează conform codului de mai jos. Vă recomandăm să folosiți funcția WritePerm(value) pentru toate cele $N^2$ numere în ordine.

Se vor afișa $N^2$ numere, reprezentând a $P$ -a permutare în ordine lexicografică care se poate obține. Din nou, pentru simplitate de testare vă recomandăm sa folosiți functia WritePerm(value) pentru toate cele $N^2$ numere în ordine, iar dacă $Seed = 0$ atunci toate numerele vor fi afișate la output, altfel valoare $Seed$ nou rezultata va fi afișată.

Restricții și precizări

$1 \leq N \leq 2 \ 500$
$1 \leq P \leq 10^{18}$
$1 \leq A_{i,j} \leq N^2$
Valorile din matricea $A$ sunt distincte.
Se garantează că există cel puțin $P$ permutări care se pot obține folosind procedeul descris în cerință.
Semidiagonala unei matrice se consideră ca fiind diagonala ce începe din colțul stânga-jos și parcurge elementele înspre dreapta-sus sau viceversa, iar diagonala unei matrice se consideră ca fiind diagonala ce începe din colțul stânga-sus și parcurge elementele înspre dreapta-jos.
Corectare: numerele nu formează neapărat o permutare, dar sunt distincte și nu depășesc un milion.

Subtask 1 (9 puncte)

$N \leq 3$

Subtask 2 (21 puncte)

$P = 1$

Subtask 3 (43 puncte)

$1 \leq N \leq 500$

Subtask 4 (27 puncte)

Fără restricții suplimentare

Exemplu

stdin

stdout

2 5 3 1 4 8 9 6 7

stdin

6 9 1729

stdout

5976389439715066411

Explicații

Pentru primul exemplu se alege colțul din stânga jos, deci se trage in numerele 2 5 3, care se adauga la permutare. Matricea devine astfel:

$\begin{matrix} 6 & 4 & \\ 1 & & 9\\ & 8 & 7 \end{matrix}$

Se alege apoi deplasarea pe verticala și matricea devine:

$\begin{matrix} 6 & 4 & 9\\ 1 & 8 & 7 \end{matrix}$

Alegem colțul stânga jos (deci se adaugă 1 4 la permutare), iar matricea devine:

$\begin{matrix} 6 & & 9\\ & 8 & 7 \end{matrix}$

iar după deplasarea pe orizontală, matricea devine:

$\begin{matrix} 6 & 9\\ 8 & 7 \end{matrix}$

Alegem din nou colțul stânga jos (deci se adaugă 8 9 la permutare), iar matricea devine

$\begin{matrix} 6 & 7 \end{matrix}$

Alegem pe 6, iar mai apoi pe 7 și obținem în final permutarea 2 5 3 1 4 8 9 6 7.

Sniper