Supernova

Extratereștrii de pe planeta Adarin au studiat toate cele $K$ stele din galaxia lor. Aceștia au ajuns la concluzia că fiecare stea, după moartea sa, va crea o supernovă. Extratereștrii doresc să plece de pe planeta lor înainte ca o supernovă să o distrugă.
Galaxia în care trăiesc extratereștrii este împărțită în sectoare, reprezentate sub forma unei matrice cu $N$ linii și $M$ coloane, fiecărui sector din galaxie ii corespunde o poziție din această matrice. În galaxie planeta Adarin se află în sectorul cu coordonatele $N_a$ și $M_a$. Prin cercetările lor, extratereștrii cunosc pozițiile tuturor stelelor din galaxia lor, precum și durata de viața a fiecăreia. Când o stea moare, aceasta creează o supernovă. O supernovă este definită astfel:

• În anul în care moare o stea, sectorul în care se află ea devine periculos.
• În fiecare an următor, zona periculoasa se extinde catre toate sectoarele care au o latură comună cu un sector periculos si devin și ele periculoase.

Exemplu de evoluție a unei supernove după moartea unei stele:

Cerință

Scrieți un program care să rezolve următoarele două cerințe:

1. Extratereștrii au simulat moartea unei stele. Cunoscând ca steaua trăiește $v$ ani, ei doresc sa determine cate sectoare devin periculoase după $t$ ani.
2. Sunt date coordonatele planetei Adarin și ale celor $K$ stele din galaxie, cat si durata de viață a stelelor. Calculați anul în care planeta Adarin va fi distrusa.

Date de intrare

Fișierul de intrare supernova.in conține pe prima linie o valoare $cer$ ce poate fi $1$ sau $2$ în funcție de cerința ce va fi rezolvată.
Pentru cerința $1$, pe a doua linie a fișierului de intrare se găsesc doua valori $v$, reprezentând durata de viață a stelei si $t$, reprezentând un interval de timp.
Pentru cerința $2$, pe a doua linie, se găsesc valorile $K, N, M$ ce reprezintă numărul de stele din galaxie si numărul de linii respectiv de coloane ale galaxiei. Pe a treia linie a fișierului de intrare se găsesc valorile $Na$ și $Ma$ ce reprezintă coordonatele planetei Adarin. Pe fiecare dintre liniile de la $4$ la $K + 3$ se găsesc câte $3$ valori $n, m$ și $T$ care reprezintă linia, respectiv coloana sectorului în care se afla o stea și durata de viață a stelei respective.

Date de ieșire

Pentru cerința $1$, fișierul supernova.out va conține numărul de sectoare din galaxie care devin periculoase după $t$ ani.
Pentru cerința $2$, fișierul supernova.out va conține anul în care Planeta Adarin va fi distrusa de o supernova.

Restricții și precizări

• $1 \le t \le 10^9$;
• $1 \le v \le t$;
• $1 \le K \le 10^5$;
• $1 \le N, M \le 10^9$;
• $1 \le n, m, N_a, M_a \le N, M$;
• $1 \le T \le 10^9$.

Exemplul 1

supernova.in

1
1 3

supernova.out

13

Explicație

Pentru primul exemplu steaua moare în anul $1$ creând $1$ sector periculos, în anul $2$ vor fi $5$ sectoare periculoase, iar în anul $3$ vor fi $13$ sectoare periculoase în total.

Exemplul 2

supernova.in

1
1337 31414

supernova.out

1809312013

Exemplul 3

supernova.in

2
1 10 10
5 5
5 5 1

supernova.out

1

Explicație

Galaxia are $1$ stea, $10$ linii si $10$ coloane.
Planeta Adarin se afla în sectorul cu coordonatele $(5,5)$.
Steaua se afla în sectorul cu coordonatele $(5,5)$ si va muri în Anul $1$, distrugând planeta în același an.

Exemplul 4

supernova.in

2
4 100000 100000
69450 7266
45925 758 39310
3205 28284 57866
11199 45407 48522
38985 44310 14702

supernova.out

69343