Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
sh, sw, gh, gw = sh - 1, sw - 1, gh - 1, gw - 1
G = [list(input()) for _ in range(H)]
INF = 10 ** 9


D = [[INF] * W for _ in range(H)]
D[sh][sw] = 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
que = deque([(sh, sw)])

while que:
    nh, nw = que.pop()
    for dh, dw in directions:
        for k in range(1, K + 1):
            nx_h, nx_w = nh + k * dh, nw + k * dw
            if not (0 <= nx_h < H and 0 <= nx_w < W):
                break

            if G[nx_h][nx_w] == '@':
                break

            if D[nx_h][nx_w] <= D[nh][nw]:
                break

            D[nx_h][nx_w] = D[nh][nw] + 1
            que.appendleft((nx_h, nx_w))

print(D[gh][gw] if D[gh][gw] != INF else -1)


### FIXED CODE ###

from collections import deque
H, W, K = map(int, input().split())
sh, sw, gh, gw = map(int, input().split())
sh, sw, gh, gw = sh - 1, sw - 1, gh - 1, gw - 1
G = [list(input()) for _ in range(H)]
INF = 10 ** 9


D = [[INF] * W for _ in range(H)]
D[sh][sw] = 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
que = deque([(sh, sw)])

while que:
    nh, nw = que.pop()
    for dh, dw in directions:
        for k in range(1, K + 1):
            nx_h, nx_w = nh + k * dh, nw + k * dw
            if not (0 <= nx_h < H and 0 <= nx_w < W):
                break

            if G[nx_h][nx_w] == '@':
                break

            if D[nx_h][nx_w] <= D[nh][nw]:
                break

            if D[nx_h][nx_w] > D[nh][nw] + 1:
                D[nx_h][nx_w] = D[nh][nw] + 1
                que.appendleft((nx_h, nx_w))

print(D[gh][gw] if D[gh][gw] != INF else -1)
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
cost = [[float("inf") for i in range(n)] for i in range(n)] 
to=[[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)
dist=[1000000]*n    

que=deque([0])
while que:
    v=que.pop()
    for i in to[v]:
        if(dist[i] is 1000000):
            dist[i]=v+1
            que.appendleft(i)
        
print("Yes")
for i in dist[1:]:
    print(i)    


### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
to=[[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)
dist=[None]*n    

que=deque([0])
while que:
    v=que.pop()
    for i in to[v]:
        if(dist[i] is None):
            dist[i]=v+1
            que.appendleft(i)
        
print("Yes")
for i in dist[1:]:
    print(i)
### BUGGY CODE ###

#098_D
def search_1(x):
    l = set()
    n = len(bin(int(x))) - 2
    for j in range(n):
        if (int(x) >> j) & 1:
            l.add(j)
    return l

n = int(input())
a = [search_1(x) for x in input().split()]
#print(a)

ans = 0
cur = set()
r = 0
for l in range(0, n):
    while r < n and len(cur & a[r]) == 0:
        cur |= a[r]
        r += 1
    #print(l, r)
    ans += r - l 
    
    cur -= a[l]
print(ans)

### FIXED CODE ###

#098_D
def search_1(x):
    l = set()
    n = len(bin(int(x))) - 2
    for j in range(n):
        if (int(x) >> j) & 1:
            l.add(j)
    return l

n = int(input())
a = [search_1(x) for x in input().split()]
#print(a)

ans = 0
cur = set()
r = 0
for l in range(0, n):
    while r < n and len(cur & a[r]) == 0:
        cur |= a[r]
        r += 1
    #print(l, r)
    ans += r - l 
    
    cur -= a[l]
print(ans)
### BUGGY CODE ###

import heapq
import copy
N = input()
A = [-int(input()) for _ in range(int(N))]
for idx, a in enumerate(A):
    A_heap = copy.deepcopy(A)
    A_heap.pop(idx)
    heapq.heapify(A_heap)
    pop_A = heapq.heappop(A_heap)
    print(-(pop_A))

### FIXED CODE ###

import heapq
import copy
N = input()
A = [-int(input()) for _ in range(int(N))]
A_heap = copy.deepcopy(A)
heapq.heapify(A_heap)
for idx, a in enumerate(A):
    pop_A = heapq.heappop(A_heap)
    pop_A_list = []
    pop_A_list.append(pop_A)
    if pop_A == a:
        pop_A2 = heapq.heappop(A_heap)
        print(-(pop_A2))
        heapq.heappush(A_heap, pop_A)
        heapq.heappush(A_heap, pop_A2)
        continue

    print(-(pop_A))
    heapq.heappush(A_heap, pop_A)
### BUGGY CODE ###

import copy
n=int(input())
A=[int(i) for i in input().split()]
list_a=copy.deepcopy(A)
set_A=set(list_a)
ans=0
for i in set_A:
    a=A.count(i)
    if a<i:
        ans+=a
    elif i<a:
        ans+=a-i

print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
A=Counter([int(i) for i in input().split()])
#print(A)
ans=0
for i in A.items():
#    print(i)
    k=i[0]
    l=i[1]
    if k<l:
        ans+=l-k
    elif l<k:
        ans+=l

print(ans)
### BUGGY CODE ###

import sys
from math import log2,floor
N = int(sys.stdin.readline().rstrip())
A = list(map(int,sys.stdin.readline().split()))
mod = 10**9+7
ans = 0
for i in range(61):
    bits = 0
    for x in A:
        if (x>>i)&1:
            bits += 1
    s = (bits*(N-bits))%mod
    t = (2**i)%mod
    ans += ((bits*(N-bits))* 2**i) %mod
ans %= mod
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
mod = 10**9 + 7
 
def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))
 
def main():
    n = ni()
    a = na()
    ans = 0
    for i in range(61):
        cnt = 0
        for ai in a:
            if (ai >> i) & 1:
                cnt += 1
        ans += ((cnt * (n - cnt)) * 2**i) % mod
    ans %= mod
    print(ans)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from _collections import deque


h, w = map(int, input().split())
ls = []  # [[0, 0, 0, 1, 0], [0, 1, 0, 1, 0], [0, 1, 0, 0, 0]]
for _ in range(h):
    ls1 = []
    s = input()
    for i in range(w):
        if s[i] == '.':
            ls1.append(0)
        else:
            ls1.append(1)
    ls.append(ls1)

def trans(a, b):
    return a * w + b

ls2 = [[] for _ in range(h * w)]


for i in range(h):
    for j in range(w):
        # check ij
        if ls[i][j] == 1:
            continue

        if 0 <= i < h and 0 <= j - 1 < w and ls[i][j - 1] == 0:
            ls2[trans(i, j)].append(trans(i, j - 1))
            #print(ls2)
        if 0 <= i + 1 < h and 0 <= j < w and ls[i + 1][j] == 0:
            ls2[trans(i, j)].append(trans(i + 1, j))
            #print(ls2)
        if 0 <= i - 1 < h and 0 <= j < w and ls[i - 1][j] == 0:
            ls2[trans(i, j)].append(trans(i - 1, j))
            #print(ls2)
        if 0 <= i < h and 0 <= j + 1 < w and ls[i][j + 1] == 0:
            ls2[trans(i, j)].append(trans(i, j + 1))

#print(ls2)


def route(i, j):
    if i == j:
        return 0
    count = 1
    ss = deque(ls2[i])
    next = deque()
    now = i
    explored = [i]
    while True:
        #print(now, i, j)
        if not ss:
            count +=1
            ss = next
            next = deque()
        now =ss.popleft()
        if now in explored:
            continue
        if now == j:
            #print(count)
            return count
        else:
            next.extend(ls2[now])


ls3 = [0] * (h * w)


for i in range(h * w):
    if ls2[i] == []:
        continue
    count = 0
    for j in range(h * w):
        if ls2[j] == []:
            continue
        else:
            count = max( count, route(i, j))
    ls3[i] = count

print(max(ls3))

### FIXED CODE ###

from collections import deque

def main():
    h, w = map(int, input().split())
    ls = [input() for _ in range(h)]

    def trans(a, b):
        return a * w + b

    ls2 = [[] for _ in range(h * w)]

    for i in range(h):
        for j in range(w):
            # check ij
            if ls[i][j] == '#':
                continue
            if i >= 1 and ls[i-1][j] != '#':
                ls2[trans(i, j)].append(trans(i-1, j))
            if i <= h-2 and ls[i+1][j] != '#':
                ls2[trans(i, j)].append(trans(i + 1, j))
            if j <= w-2 and ls[i][j+1] != '#':
                ls2[trans(i, j)].append(trans(i, j + 1))
            if j >= 1 and ls[i][j-1] != '#':
                ls2[trans(i, j)].append(trans(i, j - 1))


    #print(ls2)


    def route(i):
        count = 1
        ss = deque(ls2[i])
        next = deque()
        explored = {i}
        while ss or next:
            if not ss:
                count +=1
                ss = next
                next = deque()
            now =ss.popleft()
            if now in explored:
                continue
            else:
                explored.add(now)
                next.extend(ls2[now])
        return count-1
    ans = 0
    for i in range(h * w - 1):
        if ls2[i] == []:
            continue
        ans = max(ans, route(i))

    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import itertools

n = int(input())
l = [int(v) for v in input().split()]

l = sorted(l)

res = {}
comb = list(itertools.combinations(l, 3))
count = 0
for i in range(len(comb)):
    a = comb[i][0]
    b = comb[i][1]
    c = comb[i][2]
    if '{}{}{}'.format(a, b, c) in res:
        count += 1
        continue
    if a + b <= c:
        continue
    elif a + c <= b:
        continue
    elif b + c <= a:
        continue
    else:
        count += 1
        res['{}{}{}'.format(a, b, c)] = 'Good'

print(count)


### FIXED CODE ###

import bisect


def triangles():
    n = int(input())
    l = [int(v) for v in input().split()]
    l.sort()

    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            c = l[i] + l[j]
            index = bisect.bisect_left(l, c)
            count += max(index - j - 1, 0)

    print(count)


if __name__ == '__main__':
    triangles()
### BUGGY CODE ###


H, W, D = map(int, input().split())

coord_dict = {}
for i in range(H):
    gyo = [int(i) for i in input().split()]
    for j in range(W):
        coord_dict.update({gyo[j] : (i,j)})
        
Q = int(input())

exam = [[] for i in range(Q)]
for i in range(Q):
    exam[i] = [int(i) for i in input().split()]

for i in range(Q):
    reduce_MP = 0
    num = exam[i][0]
    coord1 = coord_dict[num]
    while num < exam[i][1]:
        coord2 = coord_dict[num + D]
        reduce_MP += abs(coord1[0] - coord2[0]) + abs(coord1[1] - coord2[1])
        num += D
        coord1 = coord2
    print(reduce_MP)



### FIXED CODE ###

H, W, D = list(map(int, input().split()))

Amap = []
for i in range(H):
    Amap.append(list(map(int, input().split())))

xx = [0 for i in range(90002)]
yy = [0 for i in range(90002)]
for y in range(H):
    for x in range(W):
        xx[Amap[y][x]] = x
        yy[Amap[y][x]] = y
Q = int(input())

coord = []
for i in range(Q):
    coord.append(list(map(int, input().split())))

# magic point calculation
mp = [0 for i in range(90002)]

for i in range(D+1, 90002):
    mp[i] = mp[i-D] + abs(xx[i] -xx[i-D]) + abs(yy[i] - yy[i-D])

for i in coord:
    print(mp[i[1]] - mp[i[0]])
### BUGGY CODE ###

def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)

    dp = [[""]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = dp[i][j] + S[i]
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], key=len)
    print(dp[N][M])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    X = input()
    Y = input()
    N = len(X)
    M = len(Y)
    dp = [[0]*(M+1) for _ in range(N+1)]
    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            if x == y:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    res = ""
    while N > 0 and M > 0:
        if dp[N][M] == dp[N-1][M]:
            N -= 1
        elif dp[N][M] == dp[N][M-1]:
            M -= 1
        else:
            res = X[N-1] + res
            N -= 1
            M -= 1
    print(res)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

x = int(input())
done=False
for a in range(-9000,9001):
  for b in range(-9000,9001):
    if(not done and a**5-b**5==x):
      print(a,b)
      done=True

### FIXED CODE ###


x = int(input())
for a in range(-300,301):
  if(a<0):
    for b in range(-300,a):
      if(a**5-b**5==x):
        print(a,b)
        break
    else: continue
    break
  else:
    for b in range(-300,a):
      if(a**5-b**5==x):
        print(a,b)
        break
    else: continue
    break
### BUGGY CODE ###

import sys
from collections import Counter
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    aa = list(Counter(aa).values())
    aa.sort()
    # print(aa)
    r0 = sum(aa) + 1
    for k in range(1, n + 1):
        l = 0
        r = r0
        while l + 1 < r:
            m = (l + r) // 2
            i = bisect_left(aa, m)
            s = sum(aa[:i]) + m * (len(aa) - i)
            if s >= m * k:
                l = m
            else:
                r = m
        print(l)

main()


### FIXED CODE ###

import sys
from collections import Counter
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

class BitSum:
    def __init__(self, n):
        self.n = n
        self.table = [0] * (n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    aa = list(Counter(aa).values())
    aa.sort()
    bit = BitSum(len(aa))
    for i, a in enumerate(aa):
        bit.update(i, a)
    # print(aa)
    for k in range(1, n + 1):
        l = 0
        r = n // k + 2
        while l + 1 < r:
            m = (l + r) // 2
            i = bisect_left(aa, m)
            s = bit.sum(i - 1) + m * (len(aa) - i)
            if s >= m * k:
                l = m
            else:
                r = m
        print(l)

main()
### BUGGY CODE ###

n, m = list(map(int, input().split()))
results = []
if m:
    results = [input().split() for _ in range(m)]
ac = []
wa = {}
cnt_ac = 0
cnt_wa = 0
for res in results:
    if res[1] == "AC":
        if not res[0] in ac:
            cnt_ac += 1
            ac.append(res[0])
            if res[0] in wa.keys():
                cnt_wa += wa[res[0]]
    else:
        if res[0] in wa.keys():
            wa[res[0]] += 1
        else:
            wa[res[0]] = 1
print(cnt_ac, cnt_wa)

### FIXED CODE ###

N,M=map(int,input().split())
AC=[0]*N
WA=[0]*N
wa=0
for i in range(M):
  p,s=input().split()
  p=int(p)-1
  if AC[p]==0 and s=="AC":
  	AC[p]=1
  	wa+=WA[p]
  WA[p]+=1
print(sum(AC),wa)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

def main():
    def digit_dp(n, m):
        # dp[i][j][k] -> i: 現在見ている桁数
        #                j: n以下が保証されているかどうか
        #                k: m で割った余りの総和
        n = list(map(int, list(str(n))))
        n_len = len(n)
        dp_table = [[[0 for k in range(m)] for j in range(2)] for i in range(n_len + 1)]
        dp_table[0][0][0] = 1

        for i in range(n_len):
            for j in range(2):
                for k in range(m):
                    for d in range(0, 10 if j else n[i] + 1):
                        dp_table[i + 1][j or (d < n[i])][(k + d % m) % m] += dp_table[i][j][k]

        return dp_table[-1][0][0] + dp_table[-1][1][0] - 1
        #0 の分、1を減算


    a = int(readline())
    b = int(readline())
    mod = 10**9 + 7
    print(digit_dp(a, b) % mod)

if __name__ == "__main__":
    main()


### FIXED CODE ###

k = str(input())
d = int(input())

DP = [[[0 for _ in range(d)] for _ in range(2)] for _ in range(len(k)+1)]
DP[0][0][0] = 1

for i in range(len(k)):
    now = int(k[i])
    for j in range(2):
        for mod in range(d):
            for n in range(10):
                # 対象の数字未満が確定する場合
                if j==1 or (j==0 and n < now):
                    next_j = 1
                # 対象の数字とこの桁まで同じ場合
                elif n == now:
                    next_j = 0
                # 対象の数字よりも大きな値の場合
                else: 
                    continue

                n_mod = n % d
                next_mod = (mod + n_mod) % d
                DP[i+1][next_j][next_mod] = (DP[i+1][next_j][next_mod] + DP[i][j][mod]) % (10**9+7)

ans = (DP[len(k)][0][0] + DP[len(k)][1][0] -1) % (10**9+7)
print(ans)
# print(DP)
### BUGGY CODE ###

from collections import deque
n,m = map(int,input().split())

uv = [[] for i in range(n)]

for i in range(m):
    u,v = map(int,input().split())
    #uv[v-1].append(u-1)
    uv[u-1].append(v-1)
    
s,t = map(int,input().split())

check = [[0 for i in range(3)] for j in range(n)]

d = deque()
d.appendleft([0,0,s-1])
#check[s-1][0] = 1

while len(d) > 0:
    for i in range(len(d)):
        num,cnt,ver = d.popleft()
        check[ver][num] = 1
        num = (num+1)%3
        cnt += 1
        for j in range(len(uv[ver])):
            #print(cnt,num,ver,j,t-1,uv[ver][j])
            if uv[ver][j] == t-1 and num == 0:
                print(cnt//3)
                exit()
            if check[uv[ver][j]][num] == 0:
                #check[uv[ver][j]][num] = 1
                d.append([num,cnt,uv[ver][j]])
                
print(-1)

### FIXED CODE ###

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# vertexごとに3つの状態数を持つ
N, M = lr()
graph = [[] for _ in range((N+1)*3)]  # 1-indexed
for _ in range(M):
    a, b = lr()
    a *= 3; b *= 3
    for i in range(3):
        j = i+1 if i < 2 else 0
        graph[a+i].append(b+j)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1) * 3
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for i in graph[prev]:
            #print(graph[prev],dist[next],next)
            d1 = d + 1
            if dist[i] > d1:
                dist[i] = d1
                heappush(que, (d1, i))
    return dist

S, T = lr()
dist = dijkstra(S*3)
answer = dist[T*3]
if answer == INF:
    answer = -1
else:
    answer //= 3
print(answer)
### BUGGY CODE ###

N=int(input())
S=list(input())

minimum=N
for i in range (N+1):
  white=S[:i].count("#")
  black=S[i:].count(".")
  minimum=min(minimum, white+black)
print(minimum)


### FIXED CODE ###

N=int(input())
S=input()

white=S.count(".")
countb=0
ans=white

for i in range (len(S)):
  if S[i]==".":
    white -=1
  else:
    countb +=1 
  ans=min(ans, countb+white)

print(ans)
### BUGGY CODE ###

N = int(input())
A = tuple(map(int, input().split()))
for i in range(N):
    print(str(A.index(i+1)+1), end=' ')

### FIXED CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
a = np.argsort(np.array(a)) + 1
for i in range(len(a)):
    print(a[i], end='')
    if i != len(a) - 1:
        print(' ', end='')
### BUGGY CODE ###

K, S = map(int,input().split())

count = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z == S:
                count += 1
            
print(count)    

### FIXED CODE ###

K, S = map(int,input().split())

count = 0

for x in range(K+1):
    for y in range(K+1):
        if 0 <= S-x-y <= K:
            count += 1
            
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [a[i] - (i+1) for i in range(len(a))]

ans = float("inf")
for i in range(min(a),max(a)+1):
  b = [abs(a[ai]-i) for ai in range(len(a))]
  ans = min(ans, sum(b))
  
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [a[i] - (i+1) for i in range(len(a))]

import statistics
b = int(statistics.median(a))
ans = sum([abs(i-b) for i in a])
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

def solve(n, a):
    a.sort(reverse=True)
    cnt = 0
    for _ in [0]*n:
        cnt += a[1]
        del a[0:2]
        del a[-1]
    return cnt
    
print(solve(N, A))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)
i = 1
n = 1
cnt = 0
while 2*i <= 2*N:
    cnt += A[n]
    i += 1
    n += 2
    
print(cnt)
### BUGGY CODE ###

from functools import cmp_to_key

n = int(input())
pref = []
suff = []

for i in range(n):
	s = input()
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])

# def comp1(x, y):
# 	return x[1] - y[1]
#
#
# def comp2(x, y):
# 	return -x[0] + y[0]


# pref.sort( key=cmp_to_key(comp1))
# suff.sort( key=cmp_to_key(comp2))

pref.sort(key=lambda x: x[1])
suff.sort(key=lambda x: -x[0])


totPos = 0

for pos, neg in pref:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

for pos, neg in suff:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

if totPos != 0:
	print("No")
else:
	print("Yes")


### FIXED CODE ###

n = int(input())
ara = [input() for _ in range(n)]
pref = []
suff = []

for s in ara:
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])


pref.sort(key=lambda x: x[1])
suff.sort(key=lambda x: x[0], reverse=True)

totPos = 0

ara = pref + suff

for pos, neg in ara:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos


if totPos != 0:
	print("No")
else:
	print("Yes")
### BUGGY CODE ###

#####segfunc######                                                              
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n,q=map(int,input().split())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
a=list(map(int,input().split()))
init(a)
ans=0
for i in range(q):
    x,l,r=map(int,input().split())
    if x==0:
        update(l,query(l,l+1)+r)
    else:
        print(query(l,r))


### FIXED CODE ###

#####segfunc######                                                              
def segfunc(x,y):
    return x+y

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
n,q=map(int,input().split())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
a=list(map(int,input().split()))
init(a)
ans=0
for i in range(q):
    x,l,r=map(int,input().split())
    if x==0:
        update(l,query(l,l+1)+r)
    else:
        print(query(l,r))