Cyberattack

"Disclaimer: Numele FortGo este pur original, orice asemănare cu proprietăți culturale existente este o coincidență." - Argumentul folosit de avocați în Marele Proces al Jocurilor Video (MPJV) împotriva companiilor din spatele Fortnite și CS:GO.

”FortGo 7” este un MMORPG foarte popular în anul 4096. În acest joc, harta este împărțită în zone de influență aparținând fiecărui jucător. Această configurație poate fi reprezentată printr-un dreptunghi cu $N$ linii și $M$ coloane, unde fiecare zonă de $1 \times 1$ îi aparține unui jucător diferit. În ziua de 32 februarie, un hacker, supărat pentru că a pierdut tot progresul din cauza unei erori locale, s-a decis să corupă teritoriile bazate într-o anumită parte a hărții. Astfel, la momentul de timp $1$, colțul din stânga-sus al dreptunghiului devine corupt. La fiecare moment ulterior, atacul continuă și toate teritoriile vecine celor deja corupte devin și ele, la rândul lor, corupte. Atacul se sfârșește când orice alt colț pe lângă cel din stânga-sus devine corupt. După finalizarea atacului, configurația hărții rămâne neschimbată.

De exemplu, pentru $N = 3$ și $M = 4$, harta va avea următoarea configurație, unde celulele gri reprezintă teritorii corupte și cele albe reprezintă teritorii neafectate. Atacul se oprește la momentul $3$, când teritoriul din colțul stânga-jos devine corupt.

Cerință

Tu faci parte din echipa care trebuie să colecteze date despre atacul cibernetic care a avut loc. Știind dimensiunile hărții, $N$ și $M$, trebuie să determini două tipuri de informații despre starea hărții:

1. Câte celule sunt corupte în momentul $T$?
2. Câte teritorii nu au fost afectate de atac în momentul $T$?

Date de intrare

Prima linie din fișierul de intrare cyberattack.in va conține patru numere naturale $C$, $N$, $M$ și $T$, unde $C$ reprezintă tipul de informație care trebuie determinat, $N$ și $M$ reprezintă numărul de linii, respectiv numărul de coloane al hărții, iar $T$ reprezintă momentul în care se află harta.

Date de ieșire

• Dacă $C = 1$, atunci pe prima linie din fișierul de ieșire cyberattack.out se va găsi un număr natural, reprezentând numărul de celule corupte în momentul $T$.
• Dacă $C = 2$, atunci pe prima linie din fișierul de ieșire cyberattack.out se va găsi un număr natural, reprezentând numărul de celule neafectate de atac în momentul $T$.

Restricții și precizări

• $1 \leq N, M, T \leq 1 \ 000 \ 000 \ 000$;
• Hacker-ul a lăsat în urma lui un indiciu, care te poate ajuta cu rezolvarea problemei: ”The territory INTerval is too short for my liking. I LONG for another LONGer map to corrupt.”;

Exemplul 1

cyberattack.in

1 3 4 2

cyberattack.out

3

Explicație

Din desen observăm că, în momentul $T = 2$, există $3$ teritorii corupte.

Exemplul 2

cyberattack.in

2 3 4 2

cyberattack.out

9

Explicație

La fel, din desen observăm că, în momentul $T = 2$, există $9$ teritorii neafectate de atac.