Hill Jumping

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Chef is going to organize a hill jumping competition and he is going to be one of the judges in it. In this competition there are N hills in a row, and the initial height of ith hill is A_{i}. Participants are required to demonstrate their jumping skills by doing what the judges tell them.
Judges will give each participant a card which has two numbers, i and k, which means that the participant should start at the ith hill and jump k times, where one jump should be from the current hill to the nearest hill to the right which is strictly higher (in height) than the current one. If there is no such hill or its distance (i.e. difference between their indices) is more than 100 then the participant should remain in his current hill.
Please help Chef by creating a program to use it during the competitions. It should read the initial heights of the hill and should support two kinds of operations:
Type 1: Given a two numbers: i and k, your program should output the index of the hill the participant is expected to finish if he starts from the ith hill (as explained above).
Type 2: Given three numbers: L, R, X, the heights of all the hills between L and R, both end points inclusive, should be increased by X (if X is negative then their height is decreased).
Input
 First line contains two integers N and Q, denoting the number of hills and number of operations respectively.
 Second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the initial heights of the hills.
 Each of the next Q lines describes an operation. If the first integer is equal to 1, it means that the operation is of Type 1, and it will be followed by two integers i and k. Otherwise the first number will be equal to 2, and it means that the operation is of Type 2, and so it will be followed by three integers L, R and X.
Output
For each operation of Type 1, output the index of the hill in which the participant will finish.
Constraints
 1 ≤ N, Q ≤ 100,000
 1 ≤ A_{i} ≤ 1,000,000
 1 ≤ L ≤ R ≤ N
 1,000,000 ≤ X ≤ 1,000,000
 1 ≤ i, k ≤ N
Subtasks
 Subtask 1 (20 points) : 1 ≤ N, Q ≤ 1,000
 Subtask 2 (80 points) : Original constraints
Example
Input: 5 3 1 2 3 4 5 1 1 2 2 3 4 1 1 1 2 Output: 3 4
Explanation
The initial heights are (1, 2, 3, 4, 5). The first operation is of Type 1 and starts from Hill 1 and wants to jump twice. The first jump will be to Hill 2, and the second jump will be to Hill 3. Hence the output for this is 3.
The second operation changes the heights to (1, 2, 2, 3, 5).
The last operation starts from Hill 1. The first jump is to Hill 2. But the next jump will skip Hill 3 (because it's height is not strictly greater than the current hill's height), and will go to Hill 4. Hence the output is 4.
Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/HILLJUMP 
Tags  aug17, bruteforce, kingofnumbers, medium, sqrt 
Date Added:  20102016 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions