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. Gigel 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].

Cerinta

Ajutati-l pe Gigel furnizandu-i raspunsurile pentru operatie de tip 1.

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.

Date de iesire

In fisierul de iesire marbles.out va contine pentru fiecare operatie de tipul 1 din input, raspunsul corespunzator.

Restrictii

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 100.000
• Culoarea unei bile va fi un numar natural din intervalul [1,64]
  *

Exemplu

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.

Cum se trimit solutii?