Pe o alee se află N plopi de diferite înălţimi. Plopii se află de-a lungul unui segment de dreaptă, astfel pot fi numerotaţi 1, 2, ..., N de la cel mai stânga către cel mai din dreapta. Distanţa de la plopul cu indicele i la cel cu indicele j este |i-j| (modulul diferenţei dintre indici). Cum nu ne confruntăm cu o situaţie reală, din când în când plopii îşi pot schimba înălţimea. Alexandra a făcut o listă în care sunt notate toate schimbările petrecute în rândul plopilor, dar din când în când se întreabă care este cel mai apropiat plop de plopul cu indicele i situat în dreapta lui, care să aibă o înălţime mai mare sau egală cu H.
Cerinţă
Aflaţi răspunsul pentru fiecare întrebare a Alexandrei.
Date de intrare
Pe prima linie a fişierului de intrare plopi.in se află două numere naturale separate prin spaţiu N M, reprezentând numărul de plopi de pe alee, respectiv numărul de operaţii (modificări de înălţime sau interogări efectuate de Alexandra). Pe următoarele N linii se află înălţimile iniţiale ale plopilor. Pe linia i+1 se află înălţimea plopului i. Pe următoarele M linii se află câte trei numere naturale separate prin spaţii t p h. Dacă t este egal cu 1, atunci noua înălţime a plopului cu indicele p este h. Dacă t este egal cu 2 atunci Alexandra se întreabă care este cel mai apropiat plop situat în dreapta plopului p care are o înălţime mai mare sau egală decât h.
Date de ieşire
Fişierul de ieşire plopi.out conţine mai multe linii, câte una pentru fiecare întrebare pusă de Alexandra. Pe linia i se află răspunsul la cea de a i-a întrebare, respectiv valoarea -1, dacă întrebarea nu are răspuns.
Restricţii
1 ≤ N, M ≤ 100 000
N este număr natural impar
Toate numerele din fişierul de intrare sunt numere naturale strict pozitive < 2 000 000 000