spiralmatrix

Parcurgând elementele unei matrice pătratice de dimensiune $n$ în spirală, pornind din colțul din stânga-sus, în sens orar, de la margini către interior, se obține șirul strict crescător format din toate valorile de la $1$ la $n^2$, ca în figura de mai jos. Din șirul dat se obțin două subșiruri disjuncte, de lungime egală, cu număr maxim de termeni. Primul subșir este format din numere consecutive din prima jumătate a șirului, și trebuie să conțină în mod obligatoriu valoarea $1$, iar al doilea este format din numere consecutive din a doua jumătate a șirului și trebuie să conțină în mod obligatoriu valoarea $n^2$.

Cerință

Să se afle poziția în matrice a celui mai mare termen din primul subșir și a celui mai mic termen din al doilea subșir.

Date de intrare

Fișierul de intrare spiralmatrix.in conține numărul natural $n$.

Date de ieșire

În fișierul de ieșire spiralmatrix.out se vor scrie:

• pe prima linie două numere, separate printr-un spațiu, reprezentând mai întâi linia și apoi coloana pe care se află în matrice cel mai mare termen al primului subșir;
• pe a doua linie alte două numere, separate printr-un spațiu, reprezentând mai întâi linia și apoi coloana pe care se află în matrice cel mai mic termen al celui de-al doilea subșir.

Restricții și precizări

• $1 < n < 1\ 000\ 000\ 000$
• Pentru teste în valoare de 45 de puncte, $n$ este impar.
• Pentru teste în valoare de 45 de puncte, $n < 1\ 000$.
• Pentru teste în valoare de 75 de puncte, $n < 1\ 000\ 000$.
• Liniile sunt numerotate de sus în jos începând cu $1$, iar coloanele sunt numerotate de la stânga la dreapta începând cu $1$.
• Punctajul pe un test se obține doar dacă sunt corecte toate cele 4 valori.

Exemplul 1

spiralmatrix.in

5

spiralmatrix.out

5 2
4 1

Explicație

Primul subșir este format din valorile de la $1$ la $12$. Valoarea $12$ se găsește pe linia $5$ și coloana $2$.
Al doilea subșir este format din valorile de la $14$ la $25$. Valoarea $14$ se găsește pe linia $4$ și coloana $1$.

Exemplul 2

spiralmatrix.in

4

spiralmatrix.out

4 3
4 2

Explicație

Primul subșir este format din valorile de la $1$ la $8$. Valoarea $8$ se găsește pe linia $4$ și coloana $3$.
Al doilea subșir este format din valorile de la $9$ la $16$. Valoarea $9$ se găsește pe linia $4$ și coloana $2$.