Masala E

Kichkina Shakhriyor juda ko'p o'ynashni yaxshi ko'radi. Eng muhimi, u "Teshiklar" o'yinini o'ynashni yaxshi ko'radi. Bu quyidagi qoidalarga ega bir kishi uchun o'yin:

Bitta qatorda joylashgan va $1$ dan $N$ gacha bo'lgan raqamlar bilan chapdan o'ngga raqamlangan $N$ ta teshik bor. Har bir teshik o'z kuchiga ega (teshik raqami $i , a_i$ quvvatiga ega). Agar siz to'pni $i$ teshigiga tashlasangiz, u darhol $i + a_i$ teshigiga sakraydi, keyin undan sakrab chiqadi va hokazo. Agar bunday raqam bilan teshik bo'lmasa, to'p shunchaki qatordan sakrab chiqadi. Har bir $M$ harakatda o'yinchi ikkita harakatdan birini bajarishi mumkin:

• Teshikning kuchini $a$ qiymatiga o'rnating $b$.
• To'pni $a$ teshigiga tashlang va to'p qatordan sakrashdan oldin qancha sakrab chiqqanini hisoblang, shuningdek, qatordan chiqishdan oldin qaysi teshikdan sakrab chiqqanini ham yozing.

Shakhriyor matematikada yaxshi emas, shuning uchun siz allaqachon taxmin qilganingizdek, barcha hisob-kitoblarni bajarishingiz kerak.

Birinchi qatorda ikkita butun $N$ va $M (1 ≤ N ≤ 10^5, 1 ≤ M≤ 10^5)$ mavjud — qatordagi teshiklar soni va harakatlar soni. Ikkinchi qatorda $N$ dan oshmaydigan $N$ musbat sonlar mavjud - teshik quvvatining boshlang'ich qiymatlari. Quyidagi $M$ qatorlar Shakhriyor tomonidan qilingan harakatlarni tasvirlaydi. Ushbu qatorlarning har biri ikkita turdan biri bo'lishi mumkin:

• $0  a  b$
• $1  b$

$0$ turi $a$ teshikning quvvatini $b$ ga o'rnatish kerakligini bildiradi va $1$ turi $a$-teshikka to'p tashlashni talab qiladi. $a$ va $b$ raqamlari $N$ dan oshmaydigan musbat butun sonlardir.

$1$-turdagi har bir harakat uchun alohida qatorga bo'sh joy bilan ajratilgan ikkita raqamni chiqaring - qatordan chiqishdan oldin to'p tashrif buyurgan so'nggi teshik soni va u qilgan sakrashlar soni.