Lipsticks From Dubai

rithyy Intra AUST Programming Co...
Limits 1s, 512 MB

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 KPeople 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

InputOutput
8 5
1 1 1 1 1 2 8 2
1 1
0 1 3
1 1
0 3 4
1 2
15

Submit

Login to submit.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.