V rade máme postavených $n$ prázdnych pohárikov očíslovaných od 1 po $n$. Občas niekto príde a do každého pohárika v zadanom intervale $a$ až $b$ (vrátane týchto dvoch pohárikov) vloží jeden kamienok. A raz za čas potrebujeme vedieť koľko kamienkov je v poháriku číslo $x$. Naprogramujte algoritmus, ktorý bude spracovávať obe tieto operácie.
Na prvom riadku sú dve čísla $n$ a $q$ ($1 \leq n,q \leq 400\,000$) — počet pohárikov a počet operácií, ktoré treba spracovať.
Nasleduje $q$ riadkov. Každý z nich má jeden z nasledovných dvoch tvarov. \verb!1 x! — otázka na počet kamienkov v pohári s číslom $x$ ($1 \leq x \leq n$). \verb!2 a b! — do všetkých pohárikov medzi $a$ a $b$ (vrátane) vložíme jeden kamienok ($1 \leq a \leq b \leq n$).
Pri každej operácii typu \verb!1 x! vypíšte jedno číslo — počet kamienkov v poháriku s číslom $x$.
5 7
2 3 5
1 2
2 1 4
2 4 4
1 4
1 2
2 1 1
0
3
1
Pri prvej otázke v poháriku číslo dva ešte nie je žiaden kamienok, lebo sú iba v pohároch 3 až 5. Keď sa pýtame na pohár číslo 4, tak sú v ňom už 2 kamienky. A v pohári dva je už jeden kamienok, ktorý bol pridaný v intervale 1 až 4.
Táto úloha sa síce dá vyriešiť intervalovým stromom s lazy-loading operáciami (a kľudne si ho vyskúšajte naprogramovať), no ak sa trochu zamyslíte, viete prísť aj na riešenie, ktorému stačia klasické operácie intervalového stromu.