Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Jumping Frog (II)

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 N and distance between i-th post and (i+1)-th post is 1. Distance between the 1st post and the starting position is 1 and distance between the Nth post and the other side of the river 1. The frog can jump at most Xi distance from ith 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 T (≤ 5), denoting the number of test cases.

Each case starts with two integers N and Q where N is the number of posts and Q is number of queries. Next line contains N integers separated by spaces and the i’th integer of this line represents the strength Xi of the i’th post. Next Q lines will contain two or three integers each. First number t represents the type of query.

  • If t = 1, there will be 2 more integers p, s meaning that pth post’s strength changes to s.
  • If t = 2, there will be one more integer s meaning that frogs can jump at most s distance from starting point.

Constraints:

  • (1 ≤ N ≤ 100,000)
  • (1 ≤ Q ≤ 100,000)
  • (0 ≤ Xi ≤ 1000,000,000)
  • (1 ≤ t ≤ 2)
  • (1 ≤ p ≤ N)
  • (0 ≤ s ≤ 1000,000,000)

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.

Samples

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

Author
Discussion
Submit

Login to submit