waterSimu

Tuti este un student pasionat de fizică, iar recent a descoperit o mare fascinație pentru simulările de apă. În loc să-și facă temele de informatică, el a petrecut ore întregi dezvoltând un simulator de apă. Profesorul Nea Cais nu e deloc încântat de această preocupare, insistând că Tuti ar trebui să se concentreze pe temele de informatică.

Nea Cais i-a propus lui Tuti să rezolve problema cât mai eficient dacă tot nu lucrează. Acesta fiind încântat că scapă de cicălirea lui Nea Cais, acceptă.

Simulatorul de apă este format din mai multe părți. Una dintre ele este cea în care programul trebuie să spună pentru o moleculă de apă ce molecule sunt în jurul ei.

Cerință

În simulator se primesc $N$ molecule, indexate de la $1$ la $N$ în ordinea primirii lor la intrare de coordonate întregi $(x, y)$ într-un grid de $5 \ 000$ pe $5 \ 000$. Acestea sunt cercuri cu raza $0.5$ și nu se intersectează.

În practica Tuti trebuie să răspundă la $Q$ întrebări de $2$ feluri:

• Operația 1: să se mute o moleculă de index $X$ de la poziția ei inițială $(x, y)$ la o alta $(z, t)$;
• Operația 2: să se spună câte molecule sunt la o distanță maxim 5 de molecula cu index $X$ și care sunt indexii lor (distanța se consideră de la centrele moleculelor).

Date de intrare:

Pe prima linie a fișierului watersimu.in vor fi $N$ urmat de $Q$. Urmează $N$ linii cu perechi $(x_i, y_i)$ reprezentând poziția pe grid a moleculei de index $i$.
După o sa mai fie $Q$ linii cu valoarea 1 sau 2 reprezentând operația:

• Daca e valoarea 1 înseamnă că o sa mai apară și un $X$ (indexul moleculei) și un $(z, t)$ fiind locația unde se mută;
• Daca e valoarea 2 înseamnă că o sa mai apară și un $X$ (indexul moleculei).

Date de ieșire:

Pentru fiecare operație de tipul 2 se va afișa pe o linie a fișierului watersimu.out numărul de molecule la o distanță maxim $5$ față de molecula $X$ și indexul lor. Indexii trebuie afișați în ordine crescătoare.

Restrictii si precizari

• $1 \leq N, Q \leq 200 \ 000$;
• Testele sunt generate aleatoriu;
• Moleculele nu se intersectează;
• Distanța dintre 2 molecule este distanța dintre centrele lor.
• Coordonatele centrelor sunt numere naturale între $1$ și $5 \ 000$;
• Pentru $50$ de puncte, $n \leq 500$.

Exemplu

watersimu.in

6 4
0 0
0 6
3 0
0 30
30 0
5 0
2 4
2 3
1 1 3 3
2 1

watersimu.out

0
2 1 6
3 2 3 6