Jumping Frog (II)

kazi_nayeem Ada Lovelace National Gir...
Limits 2s, 512 MB

A frog wants to cross a river. There are some posts in the river. The frog can go from one post to another by jumping. All the posts are located in a single line and numbered from 1 to NN and distance between ii-th post and i+1i+1-th post is 1. Distance between the first post and the starting position is 1 and distance between the NN-th post and the other side of the river 1. The frog can jump at most XiX_i distance from ii-th post. Now you have to answer if there is any path that the frog can take to cross the river.

Input

Input starts with an integer TT (T5T ≤ 5), denoting the number of test cases.

Each case starts with two integers NN (1N1000001 ≤ N ≤ 100000) and QQ (1Q1000001 ≤ Q ≤ 100000) where NN is the number of posts and QQ is number of queries.

The next line contains NN integers separated by spaces and the ii-th integer of this line represents the strength XX (0Xi10000000000 ≤ X_i ≤ 1000000000) of the ii-th post. Next QQ lines will contain two or three integers each. First number tt (1t21 ≤ t ≤ 2) represents the type of query.

  • If t=1t = 1, there will be 2 more integers pp (1pN1 ≤ p ≤ N), ss (0s10000000000 ≤ s ≤ 1000000000) meaning that pp-th post's strength changes to ss.

  • If t=2t = 2, there will be one more integer ss meaning that frogs can jump at most ss distance from starting point.

Output

For each case, print the case number in one line and for each query type of 2 output "yes” if the frog can go to other side with current configuration or "no" otherwise in one line.

Sample

InputOutput
1
5 11
0 0 1 5 3
2 1
2 2
2 3
2 4
2 5
1 4 0
2 1
2 5
2 3
1 1 4
2 1
Case 1:
no
no
yes
yes
yes
no
yes
no
yes

Submit

Login to submit.

Statistics

75% Solution Ratio
aaman007Earliest, May '19
RobbinFastest, 0.1s
Shuvo_MalakarLightest, 1.6 MB
serotoninShortest, 1268B
Toph uses cookies. By continuing you agree to our Cookie Policy.