Cei N ţărani din satul Gheorgheni sunt numerotaţi de la 1 la N si au casele dispuse haotic. Casele sunt reprezentate ca N puncte în plan care au ca şi coordonate numere reale. Ca să îşi organizeze mai bine satul, au decis să-şi împartă pământul astfel: fiecare ţăran va primi un teren astfel încât orice punct de pe suprafaţa acestuia va fi mai aproape de casa lui decât de oricare altă casă. Punctele aflate la egală distanţă de 2 sau mai multe case vor alcătui gardul, care nu va fi proprietatea nimănui pentru a nu apărea conflicte. Lăcomia lor totuşi iese în evidenţă prin faptul că au uitat de drumuri ( :)) ).
Astfel vor apărea două categorii de ţărani: dominaţi (au vecini de jur-împrejurul curţii) şi liberi (au vecini doar în unele părţi ale curţii).
De-a lungul timpului satul Gheorgheni a devenit atractiv, astfel mai sosesc pe rând M ţărani, fiecare stabilindu-şi casa într-un punct de coordonate reale. După sosirea fiecăruia, se reîmpart terenurile şi se doreşte aflarea numărului de ţărani liberi.

Cerinţă

Să se determine şi să se afişeze numărul ţăranilor liberi la început şi după fiecare sosire a unui ţăran nou.

Date de intrare

Fişierul de intrare terenuri.in conţine pe prima linie N şi M, reprezentând numărul initial de ţărani ai satului Gheorgheni si numărul de ţărani care se vor muta îin sat. Următoarele N linii vor conţine câte două numere reale, reprezentând coordonatele caselor ţăranilor iniţiali (băştinaşii) (linia i conţine coordonatele casei ţăranului i).
Apoi urmează M linii, fiecare conţinând două numere reale x şi y, reprezentând coordonatele casei unui ţăran nou venit.

Date de ieşire

Fişierul de ieşire terenuri.out va conţine pe prima linie numărul iniţial al ţăranilor liberi.
Următoarele M linii conţin numărul de ţărani liberi după fiecare sosire a unui ţăran nou.

Restricţii

• 3 ≤ N ≤ 100 000
• 0 ≤ M ≤ 100.000
• -1 000 000 000 ≤ x, y ≤ 1 000 000 000
• 40% din teste vor avea M = 0.
• 20% din teste vor avea 0 < M ≤ 100.
• Dacă un ţăran vine în sat el nu va mai pleca niciodată
• Daca aveţi nevoie de calcule de precizie se recomandă folosirea 1^-10

Exemple

terenuri.in	terenuri.out	Explicaţii
5 1 1.0 1.0 3.0 2.0 2.0 3.0 3.0 4.0 1.0 5.0 6.0 3.0	4 3	În configuraţia iniţială, ţăranul 3 va fi dominat, iar ceilalţi patru ţărani vor fi liberi. După venirea ţăranului nou, ţăranii 2 şi 4 vor fi dominaţi, iar ceilalţi 3 vor fi liberi.

autor: Gabriel Biţiş

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com