Do you know what lipstick is? Well, Lipstick is a cosmetic that applies color, texture, and protection to the lips.
Our friends Hasib, Kamrozzaman, Parvez and Rahat have gone for a Dubai tour and they will be bringing some lipsticks for me as a gift. There is a huge shopping mall containing N shops numbered 1 to N. But the mall has some weird rules.
People can enter any shop from the entrance as they wish. In each shop i there is a placard hanging with a number Kᵢ. People staying at i numbered shop can go to i + Kᵢ numbered shop only. If there doesn't exist any shop numbered i + Kᵢ then they'll be out of the mall. Sometimes the shopkeepers change the number of the placard as they wish.
In this problem there can be 2 kind of queries:
The placard number of the a numbered shop is changed to b
Our friends enter the a numbered shop and start buying one lipstick from each shop they can visit.
I am so excited to get lipsticks as I love them most! Now I need your help to know how many lipsticks they’ll be bringing in total as a gift.
Input
The first line contains two integers N and M (1 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^5) — the number of shops in a row and the number of queries. The second line contains N positive integers not exceeding N — initial values of the placards.
The following M lines describe queries. Each of these line can be one of the two types:
0 a b
1 a
Type 0 means that the placard number of the a numbered shop is changed to b, and type 1 means that our friends have started their journey from the a numbered shop. Numbers a and b are positive integers not exceeding N.
Output
Print the total number of lipsticks they'll be bringing after performing all the queries.
Sample
| Input | Output |
|---|---|
8 5 1 1 1 1 1 2 8 2 1 1 0 1 3 1 1 0 3 4 1 2 | 15 |
