Fişierul intrare/ieşire:	marbles.in, marbles.out	Sursă	preONI 2008, Runda finala
Autor	Filip Cristian Buruiana	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.125 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Marbles

Gigel are N bilute colorate pe care le aseaza pe axa Ox a unui sistem cartezian de coordonate. Asupra acestora el efectueaza urmatoarele operatii:

• 0 i j va reprezenta o operatie de mutare a bilei aflata la coordonata i la coordonata i+j. Se garanteaza faptul ca intre coordonatele i si i+j nu exista nicio alta bila.
• 1 i j reprezinta operatia de interogare. Astfel, Gigel se intreaba care este numarul maxim de bile de aceeasi culoare care se afla intre coordonatele i si j inclusiv.

Cerinta

Ajutati-l pe Gigel furnizandu-i raspunsurile pentru operatiile de interogare.

Date de intrare

Fisierul de intrare marbles.in contine pe prima linie numerele N si M, numarul de bilute, respectiv numarul de operatii efectuate. Pe urmatoarele N linii se afla cate doua numere intregi a_i b_i reprezentand coordonata la care se afla initial bila i, respectiv culoarea ei. Urmeaza apoi M linii, fiecare descriind o operatie facuta de Gigel.

Date de iesire

Fisierul de iesire marbles.out va contine pentru fiecare operatie de interogare raspunsul corespunzator.

Restrictii

• 1 ≤ N ≤ 100 000
• 1 ≤ M ≤ 100 000
• Culoarea unei bile va fi un numar natural din intervalul [1, 64]
• Coordonatele bilelor la orice moment de timp vor fi numere intregi ce se vor incadra pe 32 de biti.

Exemplu

Explicatie

Initial, intre coordonatele 4 si 13 exista doua bile care sunt colorate cu 1. Dupa mutarea bilei de pe pozitia 4 pe pozitia 4 - 1 = 3, intre coordonatele 4 si 13 mai raman doar doua bile, ambele fiind colorate diferit.

Cum se trimit solutii?