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 i-th hill is Ai. 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 i-th 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 i-th 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 space-separated integers A1, A2, ..., AN 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 ≤ Ai ≤ 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.

Difficulty: interview

Starter code:

Solutions:
n,q=list(map(int,input().split()))
final=[]
height=list(map(int,input().split()))
for k in range(0,q):
 b=input().split()
 if int(b[0])==1:
  step=int(b[1])-1
  for k in range(0,int(b[2])):
   temp = 0
   j=1
   while j in range(1,101) and temp==0 and step+j<n:
    if height[step+j]>height[step]:
     step=step+j
     temp=1
    j+=1
  final.append(step+1)
 elif int(b[0])==2:
  for k in range(int(b[1])-1,int(b[2])):
   height[k]=height[k]+int(b[3])
for l in range(0,len(final)):
 print(final[l])

def find_pos(arr, n, p, c):
 i = p
 i1 = p
 while i <= n and c > 0:
  if arr[i1] < arr[i]:
   if i - i1 > 100:
    return i1
   c, i1 = c - 1, i
  i += 1
 return i1


n, q = list(map(int, input().split()))
arr = [0] + list(map(int, input().split()))
for a0 in range(1, q + 1):
 temp = list(map(int, input().split()))
 if temp[0] == 1:
  p, c = temp[1], temp[2]
  print(find_pos(arr, n, p, c))
 else:
  l, r, val = temp[1], temp[2], temp[3]
  for i in range(l, r + 1):
   arr[i] += val


n,q = list(map(int,input().split()))
hill = list(map(int,input().split()))
def get_answer_type_1(i,k):
 for ind in range(k):
  curr_elem = hill[i]
  for ind_sub in range(i,i+101):
   try:
    this_elem = hill[ind_sub]
   except:
    break
   if this_elem>curr_elem:
    i=ind_sub
    break
 return i+1

def get_answer_type_2(l,r,x):
 for ind in range(l,r+1):
  hill[ind]+=x

for i in range(q):
 query = input().split()
 if query[0] == '1':
  i,k = list(map(int,query[1:]))
  i-=1
  print(get_answer_type_1(i,k))
 else:
  l,r,x = list(map(int,query[1:]))
  l-=1
  r-=1
  get_answer_type_2(l,r,x)


def find_final_posi(l1, cp, jumps):
 count = 0
 i = cp
 while i in range(cp, cp + 101):
  if ((count == jumps) | (i >= len(l1))):
   return cp
  elif l1[cp] < l1[i]:
   cp = i
   i += 1
   count += 1
  else:
   i += 1
 return cp

[n, q] = [int(x) for x in input().split()]
hillht=[-1]
hillht.extend([int(x) for x in input().split()])
for j in range(q):
 oper = [int(x) for x in input().split()]
 if oper[0] == 2:
  for x in range(oper[1], oper[2] + 1):
   hillht[x] += oper[3]
 else:
  print(find_final_posi(hillht, oper[1],oper[2]))

def find_final_posi(l1, cp, jumps):
 count = 0
 i = cp
 while i in range(cp, cp + 101):
  if ((count == jumps) | (i >= len(l1))):
   return cp
  elif l1[cp] < l1[i]:
   cp = i
   i += 1
   count += 1
  else:
   i += 1
 return cp


[n, q] = [int(x) for x in input().split()]
hillht=[-1]
hillht.extend([int(x) for x in input().split()])
for j in range(q):
 oper = [int(x) for x in input().split()]
 if oper[0] == 2:
  for x in range(oper[1], oper[2] + 1):
   hillht[x] += oper[3]
 else:
  i = oper[1]
  k = oper[2]
  l = i
  signal = 0
  print(find_final_posi(hillht, i, k))

def find_final_posi(l1, cp, jumps):
 count = 0
 i = cp
 while i in range(cp, cp + 101):
  if ((count == jumps) | (i>=len(l1))):
   return cp
  elif l1[cp] < l1[i]:
   cp = i
   i += 1
   count += 1
  else:
   i += 1
 return cp

[n,q]=[int(x) for x in input().split()]
inp=[int(x) for x in input().split()]
hillht=[-1]
hillht.extend(inp)
for j in range(q):
 oper=[int (x) for x in input().split()]
 if oper[0]==2:
  for x in range(oper[1],oper[2]+1):
   hillht[x]+=oper[3]
 else:
  i = oper[1]
  k = oper[2]
  l=i
  signal=0
  print(find_final_posi(hillht,i,k))

n,q=list(map(int,input().split()))
l=list(map(int,input().split()))
for i in range(q):
 s=list(map(int,input().split()))
 if s[0]==1:
  ind=s[1]-1
  jump=s[2]
  j=ind+1
  val=l[ind]
  while True:
   if j>=len(l):
    break
   if l[j]>val and j-ind<=100 and jump>0:
    val=l[j]
    jump-=1
    ind=j
   if j-ind>100:
    break
   if jump<=0:
    break
   j+=1
  print(ind+1)
 else:
  left=s[1]-1
  r=s[2]
  x=s[3]
  for i in range(left,r):
   l[i]+=x


import sys
import numpy as np
from collections import OrderedDict
f = sys.stdin

#f = open('HILLJUMP.txt')
#N and Q, the number of hills and number of operations.
n, q = [int(x) for x in f.readline().split()]
#A1, A2, ..., AN denoting the initial heights of the hills.
a = [int(x) for x in f.readline().split()]
#Each of the next Q lines describes an operation.
L = [0]*(n+1)
R = [0]*(n+1)
for _ in range(0, q):
 op = [int(x) for x in f.readline().split()]
 if op[0] == 1:
  p = op[1] - 1
  nj = 0
  vis = L[p] - R[p]
  vp = a[p] + vis
  for i in range(p + 1, n):
   dist = i - p
   if dist > 100:
    break
   else:
    #jump, if dist <= 100
    vis += L[i] - R[i]
    vi = a[i] + vis
    if vp < vi:
     p = i
     vp = vi
     nj += 1
     if nj >= op[2]:
      break
  print(p + 1)
 else:
  l = op[1] - 1
  r = op[2] - 1
  L[l] += op[3]
  R[r + 1] += op[3]
#f.close()


def query(i, j):
 cnt = 0
 past = arr[i]
 limit = 0
 ind = i
 for idx in range(i+1, n):
  curr = arr[idx] 
  if curr != past and curr > past:
   cnt += 1
   past = curr
   ind = idx
   limit = 0
  if cnt == j:
   return ind+1 
  if curr <= past:
   limit += 1
  if limit > 100:
   break 
 return ind+1

def update(l, r, v):
 for idx in range(l, r+1):
  arr[idx] += v
 


n, q = list(map(int, input().split()))
arr = list(map(int, input().split()))

for _ in range(q):
 a = list(map(int, input().split()))
 if a[0]-1:
  update(a[1]-1, a[2]-1, a[3]) 
 else:
  print(query(a[1]-1, a[2]))




N, Q = list(map(int, input().split(" ")))
ar = list(map(int, input().split(" ")))

def find_next(i,k):
 #print ar, i , k 
 count = 0 
 last = i 
 ind = i+1 
 while ind < N and count < k:
  #print ind , count 
  if ar[ind] > ar[last] and ind-last <= 100:
   count +=1 
   last = ind 
  elif ind - last > 100:
   return last
  
  ind +=1 
 
 if count < k:
  return last 
 
 return ind-1 
 

def change_height(L,R,K):
 for i in range(L,R+1):
  ar[i] += K 

for _ in range(Q):
 inp = list(map(int, input().split(" ")))
 if inp[0] == 1:
  i, k = inp[1] , inp[2]
  print(find_next(i-1, k)+1) 
 elif inp[0] == 2:
  L, R , K = inp[1], inp[2] , inp[3]
  change_height(L-1,R-1,K )
  


(N,Q)=input().split()
N=int(N)
Q=int(Q)
L=list(input().split())
L=list(map(int,L))
#L=[100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82,     81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63,     62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44,     43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25,     24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4    , 3, 2,101,100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85,     84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66,     65,64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47,     46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28,     27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8    , 7, 6, 5, 4, 3,2,102]
#L=[5,1,2,3,4,6,7,9,8]
#L.append(198)
#L.append(222)
#print L
while(Q>0):
 L2=list(input().split())
 L2=list(map(int,L2))
 le=len(L2)
 i=L2[1]-1
 k=L2[2]
 #print i,k
 if le==3:
  flag=True
  
  #print i
  #print k
  while(flag==True):
   jump= next((z for z,n in enumerate(L[i:]) if n > L[i]), len(L)+1)
   #print jump
   #print L[jump]
   if jump>100 or jump==len(L)+1:
    print(i+1)
    flag=False
   elif k>0:
    i=i+jump
    k=k-1
   else:
    print(i+1)
    flag=False
 else:
  c=L2[3]
  for i in range(i,k):
   L[i]=L[i]+c
  #print L        
 Q=Q-1


debug = True

n, q = list(map(int, input().split()))
a = [0] + list(map(int, input().split()))


def small_inputs():
 p = list(map(int, input().split()))

 if p[0] == 1:
  i, k = p[1:]

  c = i
  for j in range(k):
   d = 1
   m = c + 1
   while m <= n and d <= 100:
    if a[m] > a[c]:
     c = m
     break
    d += 1
    m += 1
   if m == n + 1 or d > 100:
    break
  print(c)

 else:
  l, r, x = p[1:]
  for i in range(l, r + 1):
   a[i] += x


def large_inputs():
 p = list(map(int, input().split()))

 if p[0] == 1:
  i, k = p[1:]
  print(-1)

 else:
  l, r, x = p[1:]

for test in range(q):

 if n <= 1000 and q <= 1000:
  small_inputs()
 else:
  large_inputs()


import sys
import numpy
from collections import OrderedDict
f = sys.stdin

def makeJump(op):
 p = op[1] - 1
 nj = 0
 for i in range(p + 1, n):
  dist = i - p
  if dist > 100:
   break
  else:
   #jump, if dist <= 100
   vp = a[p]
   vi = a[i]
   for k in [x for x in list(jumps.keys()) if p <= x]:
    d = jumps[k]
    for k2 in d:
     if p >= k2:
      vp += d[k2]
   for k in [x for x in list(jumps.keys()) if i <= x]:
    d = jumps[k]
    for k2 in d:
     if i >= k2:
      vi += d[k2]
   if vp < vi:
    p = i
    nj += 1
  if nj >= op[2]:
   break
 print(p + 1)
 return

#f = open('HILLJUMP.txt')
#N and Q, the number of hills and number of operations.
n, q = [int(x) for x in f.readline().split()]
#A1, A2, ..., AN denoting the initial heights of the hills.
a = [int(x) for x in f.readline().split()]
#Each of the next Q lines describes an operation.
queries = []
jumps = {}
for _ in range(0, q):
 op = [int(x) for x in f.readline().split()]
 if op[0] == 1:
  #Type 1, and it will be followed by two integers i and k.
  makeJump(op)
 else:
  #three integers L, R and X.
  l = op[1] - 1
  r = op[2] - 1
  x = op[3]
  if not r in jumps:
   jumps[r] = {}
  if not l in jumps[r]:
   jumps[r][l] = 0
  jumps[r][l] += x
#f.close()


n,q = list(map(int,input().split()))
arr = list(map(int,input().split()))
for _ in range(q):
 ar = list(map(int,input().split()))
 a = ar[0]
 if(a==1):
  b,c = ar[1],ar[2]
  curr = b-1
  f = 1
  for i in range(c):
   for j in range(curr,n):
    if(arr[j] > arr[curr] and (j-curr<=100)):
     curr = j
     break
  

  print(curr+1)
   

 else:
  b,c,d = ar[1],ar[2],ar[3]
  for k in range(b-1,c):
   arr[k]+=d
  
   
   
   
 
 
 


import sys
import numpy
from collections import OrderedDict
f = sys.stdin

def makeJump(op):
 p = op[1] - 1
 nj = 0
 for i in range(p + 1, n):
  dist = i - p
  if dist > 100:
   break
  else:
   #jump, if dist <= 100
   vp = a[p]
   vi = a[i]
   for k in [x for x in list(jumps.keys()) if x <= p]:
    d = jumps[k]
    for k2 in d:
     if p <= k2:
      vp += d[k2]
   for k in [x for x in list(jumps.keys()) if x <= i]:
    d = jumps[k]
    for k2 in d:
     if i <= k2:
      vi += d[k2]
   if vp < vi:
    p = i
    nj += 1
  if nj >= op[2]:
   break
 print(p + 1)
 return

#f = open('HILLJUMP.txt')
#N and Q, the number of hills and number of operations.
n, q = [int(x) for x in f.readline().split()]
#A1, A2, ..., AN denoting the initial heights of the hills.
a = [int(x) for x in f.readline().split()]
#Each of the next Q lines describes an operation.
queries = []
jumps = {}
for _ in range(0, q):
 op = [int(x) for x in f.readline().split()]
 if op[0] == 1:
  #Type 1, and it will be followed by two integers i and k.
  makeJump(op)
 else:
  #three integers L, R and X.
  l = op[1] - 1
  r = op[2] - 1
  x = op[3]
  if not l in jumps:
   jumps[l] = {}
  if not r in jumps[l]:
   jumps[l][r] = 0
  jumps[l][r] += x
#f.close()


import sys
import numpy
f = sys.stdin

#f = open('HILLJUMP.txt')
#N and Q, the number of hills and number of operations.
n, q = [int(x) for x in f.readline().split()]
#A1, A2, ..., AN denoting the initial heights of the hills.
a = [int(x) for x in f.readline().split()]
#Each of the next Q lines describes an operation.
t2 = []
for _ in range(0, q):
 op = [int(x) for x in f.readline().split()]
 if op[0] == 1:
  #Type 1, and it will be followed by two integers i and k.
  p = op[1] - 1
  jumps = 0
  for i in range(p + 1, n):
   dist = i - p
   if dist > 100:
    break
   else:
    #jump, if dist <= 100
    vp = a[p]
    vi = a[i]
    for arr2 in t2:
     l = arr2[1] - 1
     r = arr2[2] - 1
     if p >= l and p <= r:
      vp += arr2[3]
     if i >= l and i <= r:
      vi += arr2[3]
    if vp < vi:
     p = i
     jumps += 1
   if jumps >= op[2]:
    break
  print(p + 1)
 else:
  #three integers L, R and X.
  #a = a[:op[1]-1] + map(lambda x: x+op[3], a[op[1]-1:op[2]]) + a[op[2]:]
  #a[op[1]-1:op[2]] = map(lambda x: x+op[3], a[op[1]-1:op[2]])
  t2.append(op)
#f.close()



from sys import stdin, stdout
n,q=list(map(int,stdin.readline().split()))
hillheight = list(map(int,stdin.readline().split()))

for i in range(q):
 t =list(map(int,stdin.readline().split()))
 if t[0] == 1:
  position = t[1]-1
  numberofjumps = t[2]
  for k in range(position,n):
   if k-position>100 or numberofjumps==0:
    break
   if hillheight[k] > hillheight[position]:
    position = k
    numberofjumps = numberofjumps - 1
  stdout.write("{}\n".format(position+1))
 elif t[0] == 2:
  L = t[1]
  R = t[2]
  X = t[3]
  for w in range(L-1,R):
   
   hillheight[w] = hillheight[w] + X
   




import sys
 
ar = list(map(int, input().strip().split(' ')))
n=ar[0]
q=ar[1]
gre=[]
for i1 in range(n+2):
 gre.append(0)
n1= list(map(int, input().strip().split(' ')))
n1.insert(0,0)
for i1 in range(q):
 a = list(map(int, input().strip().split(' ')))
 if a[0]==2:
  l=a[1]
  r=a[2]
  x=a[3]
  gre[l]+=x
  gre[r+1]-=x
 elif a[0]==1:
  i=a[1]
  k=a[2]
  g=gre[i]
  w1=i
  m1=n1[i]+g
  for qw in range(i+1,n+1):
   g+=gre[qw]
   if qw-w1>100:
    break
   if k==0:
    break
   if n1[qw]+g > m1:
    m1=n1[qw]+g
    w1=qw
    k=k-1
  print(w1) 

n, queries = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))

for i in range(queries):
 inp = list(map(int, input().strip().split()))
 if inp[0] == 1:
  curr, maxJumps, out = inp[1] - 1, inp[2], inp[1] - 1
  while maxJumps > 0:
   #print 'starting : ', maxJumps, ' at : ', curr
   i, nextTo = curr + 1, curr
   while i < n and i < curr + 101:
    if arr[i] > arr[curr]:
     nextTo = i
     break
    i+=1
   if nextTo == curr:
    out = nextTo
    break
   out = nextTo
   curr = nextTo
   maxJumps -= 1
   #print 'Left : ', maxJumps, ' at : ', out + 1
  print(out + 1)
 else:
  for i in range(inp[1] - 1, inp[2]):
   arr[i] += inp[3]


inpt=list(map(int,input().split()))
n=inpt[0]
q=inpt[1]

h=list(map(int,input().split()))
for i in range(0,q):
 #print(h)
 flag=1
 oper=list(map(int,input().split()))
 typ=oper[0]
 #print(oper)
 if(typ==2):
  for j in range(oper[1]-1,oper[2]):
   h[j]=h[j]+ oper[3]
 elif(typ==1):
  start=oper[1]-1
  pos=start
  jump=oper[2]
  count=0
  jp=0 
  for l in range(pos+1,n):
   #print(l)
   count=count+1
   if(jp==jump):
    break
   if(count>100):
    break
   if(h[l]>h[pos]):
    start=l
    pos=start
    jp=jp+1
    count=0
    
  
  print(start+1)
 
  
  
  
  
  
   


inpt=list(map(int,input().split()))
n=inpt[0]
q=inpt[1]

h=list(map(int,input().split()))
for i in range(0,q):
 #print(h)
 flag=1
 oper=list(map(int,input().split()))
 typ=oper[0]
 #print(oper)
 if(typ==2):
  for j in range(oper[1]-1,oper[2]):
   h[j]=h[j]+ oper[3]
 elif(typ==1):
  start=oper[1]-1
  pos=start
  jump=oper[2]
  count=0
  jp=0 
  for l in range(pos+1,n):
   #print(l)
   count=count+1
   if(jp==jump):
    break
   if(count>100):
    break
   if(h[l]>h[pos]):
    start=l
    pos=start
    jp=jp+1
    count=0
    
  
  print(start+1)
 
  
  
  
  
  
   


inpt=list(map(int,input().split()))
n=inpt[0]
q=inpt[1]
flag=1
h=list(map(int,input().split()))
for i in range(0,q):
 #print(h)
 flag=1
 oper=list(map(int,input().split()))
 typ=oper[0]
 #print(oper)
 if(typ==2):
  for j in range(oper[1]-1,oper[2]):
   h[j]=h[j]+ oper[3]
 elif(typ==1):
  start=oper[1]-1
  pos=start
  jump=oper[2]
  count=0
  for k in range(0,jump):
   count=0
   pos=start
   for l in range(pos+1,n):
    #print(l)
    count=count+1
    if(count>100):
     flag=0
     break
    if(h[l]>h[pos]):
     start=l
     break
   if(flag==0):
    break
  print(start+1)