== include(page="template/taskheader" task_id="marbles") ==
Gigel are {$N$} bilute colorate pe care le aseaza pe axa {$Ox$} a unui sistem cartezian de coordonate. Gigel efectueaza urmatoarele operatii:
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$}. O restrictie asupra acestei operatii este faptul ca in urma ei ordinea initiala a bilelor nu se va modifica.
* {$1 i j$} Gigel se intreaba care este numarul maxim de bile de aceeasi culoare care se afla in intervalul [{$i,j$}].
* {$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.
h2. Cerinta
Ajutati-l pe Gigel furnizandu-i raspunsurile pentru operatie de tip {$1$}.
Ajutati-l pe Gigel furnizandu-i raspunsurile pentru operatiile de interogare.
h2. Date de intrare
Fisierul de intrare $marbles.in$ contine pe prima linie numerele {$N$} si {$M$}, numarul de bilute, respectiv de operatii. 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.
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.
h2. Date de iesire
In fisierul de iesire $marbles.out$ va contine pentru fiecare operatie de tipul {$1$} din input, raspunsul corespunzator.
Fisierul de iesire $marbles.out$ va contine pentru fiecare operatie de interogare raspunsul corespunzator.
h2. Restrictii
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 100.000$
* Culoarea unei bile va fi un numar natural din intervalul [{$1,64$}]
*
* $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, precum si toate numerele din fisierul de intrare, vor fi intregi cu semn ce se vor incadra pe {$32$} de biti.
* Nu vor exista $2$ bile la aceeasi coordonata
h2. Exemplu
h3. Explicatie
In intervalul [{$4,13$}] initial se afla doua bile de tip {$1$}.
Dupa mutarea bilei de pe pozitia {$4$} pe pozitia {$4-1=3$} in intervalul [{$4,13$}] mai ramane doar o bila de tip {$1$} si una de tip {$2$}.
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.
== include(page="template/taskfooter" task_id="marbles") ==
