CodeEff/ECCO huggingface dataset:
# Original solution
n, m = list(map(int, input().split()))
s = list(map(int, input().split()))
t = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0]*(m+1) for i in range(n+1)]
for si in range(n+1):
    dp[si][0] = 1
for ti in range(m+1):
    dp[0][ti] = 1

for si in range(n):
    for ti in range(m):
        if s[si] == t[ti]:
            dp[si+1][ti+1] = dp[si][ti+1] + dp[si+1][ti]
            dp[si+1][ti+1] %= MOD 
        else:
            dp[si+1][ti+1] = dp[si][ti+1] + dp[si+1][ti] - dp[si][ti] 
            dp[si+1][ti+1] %= MOD

print((dp[-1][-1] % MOD))

# Optimized solution
def count_cs(str1, str2, MOD):
    """文字列str1, str2の共通部分列(Common Subsequence, CS)を数え上げる。
    添字が異なる場合は異なる部分列として考える。
    計算量 O(|str1||str2|)
    """
    dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] + 1
            else:
                dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j]
            dp[i + 1][j + 1] %= MOD
    return (dp[len(str1)][len(str2)] + 1) % MOD


n, m = list(map(int, input().split()))
s = list(map(int, input().split()))
t = list(map(int, input().split()))
MOD = 10 ** 9 + 7


print((count_cs(s, t, MOD)))
# Original solution
from collections import defaultdict as dd

N, M = list(map(int, input().split()))
MOD = 10**9 + 7
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [[0 for i in range(M+1)] for j in range(N+1)]
for j in range(M):
    dp[1][j + 1] = dp[1][j] + 1 if s[0] == t[j] else dp[1][j]

for i in range(N):
    dp[i + 1][1] = dp[i][1] + 1 if t[0] == s[i] else dp[i][1]

if N > 1 and M > 1:
    for i in range(1, N):
        for j in range(1, M):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] + 1
            else:
                dp[i + 1][j + 1] = dp[i][j+1] + dp[i+1][j] - dp[i][j]
    
print(((dp[N][M] + 1)%MOD))


# Optimized solution
N, M = list(map(int, input().split()))
MOD = 10**9 + 7
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [[0 for i in range(M+1)] for j in range(N+1)]
for j in range(M):
    dp[1][j + 1] = dp[1][j] + 1 if s[0] == t[j] else dp[1][j]

for i in range(N):
    dp[i + 1][1] = dp[i][1] + 1 if t[0] == s[i] else dp[i][1]

for i in range(1, N):
    for j in range(1, M):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] + 1)%MOD
        else:
            dp[i + 1][j + 1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j])%MOD
    
print(((dp[N][M] + 1)%MOD))
# Original solution
N,M=list(map(int,input().split()))
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
sm=[[ 0 for i in range(M)] for j in range(N)]
s1=0
s2=0
if N>M:
  for i in range(N):
    if t[0]==s[i]:
      a=1
    else:
      a=0
    s1=s1+a
    sm[i][0]=s1
    if i<M:
      if s[0]==t[i]:
        a=1
      else:
        a=0
      s2=s2+a
      sm[0][i]=s2
else:
  for i in range(M):
    if s[0]==t[i]:
      a=1
    else:
      a=0
    s2=s2+a
    sm[0][i]=s2
    if i<N:
      if t[0]==s[i]:
        a=1
      else:
        a=0
      s1=s1+a
      sm[i][0]=s1
for i in range(1,N):
  for j in range(1,M):
    if s[i] != t[j]:
      sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]
    else:
      sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+sm[i-1][j-1]+1
ans=(sm[N-1][M-1]+1)%mod
print(ans)

# Optimized solution
N,M=list(map(int,input().split()))
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
sm=[[ 0 for i in range(M)] for j in range(N)]
s1=0
s2=0
if N>M:
  for i in range(N):
    if t[0]==s[i]:
      a=1
    else:
      a=0
    s1=s1+a
    sm[i][0]=s1
    if i<M:
      if s[0]==t[i]:
        a=1
      else:
        a=0
      s2=s2+a
      sm[0][i]=s2
else:
  for i in range(M):
    if s[0]==t[i]:
      a=1
    else:
      a=0
    s2=s2+a
    sm[0][i]=s2
    if i<N:
      if t[0]==s[i]:
        a=1
      else:
        a=0
      s1=s1+a
      sm[i][0]=s1
for i in range(1,N):
  for j in range(1,M):
    if s[i] != t[j]:
      sm[i][j]=(sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1])%mod
    else:
      sm[i][j]=(sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+sm[i-1][j-1]+1)%mod
ans=(sm[N-1][M-1]+1)%mod
print(ans)
# Original solution
def main():
    mod = 10**9 + 7
    N, M = list(map(int, input().split()))
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))
    u = [1] * (N + 1)
    v = [1] * (N + 1)
    for t in T:
        for i, s in enumerate(S, 1):
            if s == t:
                v[i] = v[i - 1] + u[i]
            else:
                v[i] = v[i - 1] + u[i] - u[i - 1]
        u, v = v, u
    return u[-1] % mod

print((main()))


# Optimized solution
def main():
    mod = 10**9 + 7
    N, M = list(map(int, input().split()))
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))
    V = [1] * N
    for t in T:
        p, q = 1, 1
        for i, (s, v) in enumerate(zip(S, V)):
            V[i] = q = v + q if s == t else v + q - p
            p = v
    return V[-1] % mod

print((main()))
# Original solution
#!/usr/bin/env python3

MOD = 10**9 + 7

n, m = list(map(int, input().split()))
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(m):
        dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j]
        if s[i] == t[j]:
            dp[i + 1][j + 1] += dp[i][j] + 1
        dp[i + 1][j + 1] %= MOD

print((dp[n][m] + 1))


# Optimized solution
#!/usr/bin/env python3

MOD = 10**9 + 7

n, m = list(map(int, input().split()))
s = list(map(int, input().split()))
t = list(map(int, input().split()))

dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 1
for j in range(m + 1):
    dp[0][j] = 1

for i in range(n):
    for j in range(m):
        dp[i + 1][j + 1] += dp[i + 1][j]
        dp[i + 1][j + 1] += dp[i][j + 1]
        dp[i + 1][j + 1] += -dp[i][j]
        if s[i] == t[j]:
            dp[i + 1][j + 1] += dp[i][j]
        dp[i + 1][j + 1] %= MOD

print((dp[n][m]))
# Original solution
import copy
N, M = list(map(int, input().split()))
S_array = list(map(int, input().split()))
T_array = list(map(int, input().split()))

mod = 10**9 + 7

add_num_array = [0] * N
ans_array = [0] * (N + 1)
ans_old = [1] * (N + 1)

for t in T_array:
    ans_array[0] = 1
    for i, s in enumerate(S_array):
        if s == t:
            add_num_array[i] = (add_num_array[i] + ans_old[i]) % mod
        ans_array[i + 1] = (ans_array[i] + add_num_array[i]) % mod
    ans_old = copy.deepcopy(ans_array)
    # print(ans_array)
print((ans_array[-1]))

# Optimized solution
N, M = list(map(int, input().split()))
S_array = list(map(int, input().split()))
T_array = list(map(int, input().split()))

mod = 10**9 + 7

add_num_array = [0] * N
ans_array = [0] * (N + 1)
ans_old = [1] * (N + 1)

for t in T_array:
    ans_array = [1] * (N+1)
    for i, s in enumerate(S_array):
        if s == t:
            add_num_array[i] = (add_num_array[i] + ans_old[i]) % mod
        ans_array[i + 1] = (ans_array[i] + add_num_array[i]) % mod
    ans_old = ans_array

print((ans_array[-1]))
# Original solution
def main():
  from collections import defaultdict
  import bisect
  n,m = list(map(int,input().split()))
  s = list(map(int,input().split()))
  t = list(map(int,input().split()))
  mod = 10**9+7
  p = max(n,m)
  if n>m:
    t.extend((0,)*(n-m))
  else:
    s.extend((0,)*(m-n))
  dcs = defaultdict(list)
  dct = defaultdict(list)
  dp = [[1 for i in range(p+1)] for j in range(p+1)]
  for i in range(p):
    if s[i] != 0:
      dcs[s[i]].append(i)
    if t[i] != 0:
      dct[t[i]].append(i)
  def update(i,j):
    val = dp[i-1][j-1]
    x = s[i-1]
    y = t[j-1]
    if dct[x]:
      k = bisect.bisect_left(dct[x],j-1)
      if k != 0:
        val += dp[i][dct[x][k-1]+1]-dp[i-1][dct[x][k-1]+1]
    if dcs[y]:
      l = bisect.bisect_left(dcs[y],i-1)
      if l != 0:
        val += dp[dcs[y][l-1]+1][j]-dp[dcs[y][l-1]+1][j-1]
    if x == y:
      val += dp[i-1][j-1]
    dp[i][j] = val%mod

  for i in range(1,p+1):
    for j in range(1,p+1):
      update(i,j)
  print((dp[-1][-1]))
main()

# Optimized solution
from collections import defaultdict
import bisect
n,m = list(map(int,input().split()))
s = list(map(int,input().split()))
t = list(map(int,input().split()))
mod = 10**9+7
p = max(n,m)
if n>m:
  t.extend((0,)*(n-m))
else:
  s.extend((0,)*(m-n))
dp = [[1 for i in range(p+1)] for j in range(p+1)]
for i in range(1,p+1):
  for j in range(1,p+1):
    x = s[i-1]
    y = t[j-1]
    if x == y:
      dp[i][j] = (dp[i-1][j]+dp[i][j-1])%mod
    else:
      dp[i][j] = (dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1])%mod
print((dp[-1][-1]))
# Original solution
MOD = 10 ** 9 + 7

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = 1 + dp[i - 1][j] + dp[i][j - 1]
            if dp[i][j] >= MOD:
                dp[i][j] -= MOD
        else:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
            if dp[i][j] >= MOD:
                dp[i][j] -= MOD

ret = dp[n][m] + 1
if ret >= MOD:
    ret -= MOD
print(ret)

# Optimized solution
MOD = 10 ** 9 + 7

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = (1 + dp[i - 1][j] + dp[i][j - 1]) % MOD
        else:
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % MOD

print(((dp[n][m] + 1) % MOD))
# Original solution
import sys
sys.setrecursionlimit(10**6+32)
mod=10**9+7
input=sys.stdin.buffer.readline
n,m=list(map(int,input().split()))
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[ [0 for _ in range(m)] for _ in range(n)]
for i in range(0,n):
    for j in range(0,m):
        ret=0
        if i-1>=0:
            ret+=dp[i-1][j]
        if j-1>=0:
            ret+=dp[i][j-1]
        if i-1>=0 and j-1>=0:
            ret-=dp[i-1][j-1]
        if s[i]==t[j]:
            ret+=1
            if i-1>=0 and j-1>=0:
                ret+=dp[i-1][j-1]
        ret%=mod
        if ret<0:
            ret+=mod
        dp[i][j]=ret
print(((dp[n-1][m-1]+1)%mod))



# Optimized solution
import sys
mod=10**9+7
input=sys.stdin.buffer.readline
n,m=list(map(int,input().split()))
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[ [0 for _ in range(m)] for _ in range(n)]
for i in range(0,n):
    for j in range(0,m):
        ret=0
        if i-1>=0:
            ret+=dp[i-1][j]
        if j-1>=0:
            ret+=dp[i][j-1]
        if i-1>=0 and j-1>=0:
            ret-=dp[i-1][j-1]
        if s[i]==t[j]:
            ret+=1
            if i-1>=0 and j-1>=0:
                ret+=dp[i-1][j-1]
        if ret>=mod:
            ret%=mod
        if ret<0:
            ret+=mod
        dp[i][j]=ret
print((dp[n-1][m-1]+1))
# Original solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = list(map(int, readline().split()))
    S = list(map(int, readline().split()))
    T = list(map(int, readline().split()))

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1

    for i in range(N):
        for j in range(M):
            dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] - dp[i][j]) % MOD
            if S[i] == T[j]:
                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % MOD

    print((dp[N][M]))
    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = list(map(int, readline().split()))
    S = list(map(int, readline().split()))
    T = list(map(int, readline().split()))

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1

    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j]) % MOD
            else:
                dp[i + 1][j + 1] = (dp[i][j + 1] + dp[i + 1][j] - dp[i][j]) % MOD

    print((dp[N][M]))
    return


if __name__ == '__main__':
    main()
# Original solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = list(map(int, readline().split()))
    S = list(map(int, readline().split()))
    T = list(map(int, readline().split()))

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    sdp = [[0] * (M + 2) for _ in range(N + 2)]

    dp[0][0] = 1
    for i in range(N + 1):
        sdp[i][0] = 1
    for j in range(M + 1):
        sdp[0][j] = 1

    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = sdp[i][j]
            sdp[i + 1][j + 1] = (sdp[i][j + 1] + sdp[i + 1][j] - sdp[i][j] + dp[i + 1][j + 1]) % MOD

    print((sdp[N][M]))
    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = list(map(int, readline().split()))
    S = list(map(int, readline().split()))
    T = list(map(int, readline().split()))

    dp = [1] * (M + 1)

    for i in range(N):
        dp_prev = dp[:]
        for j in range(M):
            if S[i] == T[j]:
                dp[j + 1] = (dp_prev[j + 1] + dp[j]) % MOD
            else:
                dp[j + 1] = (dp_prev[j + 1] + dp[j] - dp_prev[j]) % MOD

    print((dp[M]))
    return


if __name__ == '__main__':
    main()
# Original solution
n,m = list(map(int, input().split()))
s = list(map(int, input().split()))
t = list(map(int, input().split()))
PR = 1000000007

dp = [[0 for j in range(m+1)] for i in range(n+1)]

for i in range(n+1):
	dp[i][0] = 1

for j in range(m+1):
	dp[0][j] = 1 

for i in range(n):
	for j in range(m):
		#aa
		sumI = 0
		
		for jj in range(0,j):
			if s[i] == t[jj]:
				sumI=(sumI + dp[i][jj]) % PR
		
		sumJ = 0
		for ii in range(0,i):
			if t[j] == s[ii]:
				sumJ=(sumJ + dp[ii][j]) % PR
		
		if s[i] == t[j]:
			dp[i+1][j+1] = (sumI + sumJ + dp[i][j] + dp[i][j]) % PR
		else:
			dp[i+1][j+1] = (sumI + sumJ + dp[i][j]) % PR
#		print("i: %d j: %d  sumI: %d sumJ:%d dp[i][j]:%d" % (i+1,j+1,sumI,sumJ,dp[i+1][j+1]))

#print(dp)
print((dp[n][m]))

# Optimized solution
n,m = list(map(int, input().split()))
s = list(map(int, input().split()))
t = list(map(int, input().split()))
PR = 1000000007

dp = [[0 for j in range(m+1)] for i in range(n+1)]

for i in range(n+1):
	dp[i][0] = 1

for j in range(m+1):
	dp[0][j] = 1 

for i in range(n):
	for j in range(m):
		#aa
		sumI = 0
		sumI = dp[i+1][j]
#		for jj in range(0,j):
#			if s[i] == t[jj]:
#				sumI=(sumI + dp[i][jj]) % PR
		
		sumJ = 0
		sumJ = dp[i][j+1]
#		for ii in range(0,i):
#			if t[j] == s[ii]:
#				sumJ=(sumJ + dp[ii][j]) % PR
		
		if s[i] == t[j]:
			dp[i+1][j+1] = (sumI + sumJ) % PR
		else:
			dp[i+1][j+1] = (sumI + sumJ - dp[i][j]) % PR
#		print("i: %d j: %d  sumI: %d sumJ:%d dp[i][j]:%d" % (i+1,j+1,sumI,sumJ,dp[i+1][j+1]))

#print(dp)
print((dp[n][m]))
# Original solution
class BIT():

    __slots__ = ["func", "e", "n", "data"]

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [self.e] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [self.e] + length_or_list
            for i in range(1, self.n):
                if i + (i & -i) < self.n:
                    self.data[i + (i & -i)] = self.func(self.data[i + (i & -i)], self.data[i])        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] = self.func(self.data[index], delta)
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res = self.func(res, self.data[end])
            end -= end & -end
        return res

def main():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N, Q = list(map(int, input().split()))
    seg = BIT(list(map(int, input().split())), lambda a, b: a + b, 0)
    for _ in range(Q):
        a, b, c = list(map(int, input().split()))
        if a:
            print((seg.prefix_folded(c) - seg.prefix_folded(b)))
        else:
            seg.point_append(b, c)

if __name__ == "__main__":
    main()

# Optimized solution
class BIT():

    __slots__ = ["n", "data"]

    def __init__(self, length_or_list):
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [0] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [0] + length_or_list
            for i in range(1, self.n):
                if i + (i & -i) < self.n:
                    self.data[i + (i & -i)] = self.data[i + (i & -i)] + self.data[i]        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] = self.data[index] + delta
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res += self.data[end]
            end -= end & -end
        return res

    def folded(self, begin, end):
        ret = 0
        while begin < end:
            ret += self.data[end]
            end -= end & -end
        while end < begin:
            ret -= self.data[begin]
            begin -= begin & -begin
        return ret

def main():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N, Q = list(map(int, input().split()))
    seg = BIT(list(map(int, input().split())))
    for _ in range(Q):
        a, b, c = list(map(int, input().split()))
        if a:
            print((seg.folded(b, c)))
        else:
            seg.point_append(b, c)

if __name__ == "__main__":
    main()
# Original solution
class BIT():

    __slots__ = ["n", "data"]

    def __init__(self, length_or_list):
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [0] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [0] + length_or_list
            for i in range(1, self.n):
                if i + (i & -i) < self.n:
                    self.data[i + (i & -i)] += self.data[i]        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] += delta
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res += self.data[end]
            end -= end & -end
        return res

    def folded(self, begin, end):
        ret = 0
        while begin < end:
            ret += self.data[end]
            end -= end & -end
        while end < begin:
            ret -= self.data[begin]
            begin -= begin & -begin
        return ret

def main():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N, Q = list(map(int, input().split()))
    seg = BIT(list(map(int, input().split())))
    for _ in range(Q):
        a, b, c = list(map(int, input().split()))
        if a:
            print((seg.folded(b, c)))
        else:
            seg.point_append(b, c)

if __name__ == "__main__":
    main()

# Optimized solution
class BIT():

    __slots__ = ["n", "data"]

    def __init__(self, length_or_list):
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [0] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [0] + length_or_list
            for i in range(1, self.n):
                if i + (i & -i) < self.n:
                    self.data[i + (i & -i)] += self.data[i]        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] += delta
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res += self.data[end]
            end -= end & -end
        return res

    def folded(self, begin, end):
        ret = 0
        while begin < end:
            ret += self.data[end]
            end -= end & -end
        while end < begin:
            ret -= self.data[begin]
            begin -= begin & -begin
        return ret

def main():
    import sys
    input = sys.stdin.buffer.readline

    N, Q = list(map(int, input().split()))
    bit = BIT(list(map(int, input().split())))
    ans = []
    for _ in range(Q):
        a, b, c = list(map(int, input().split()))
        if a:
            ans.append(bit.folded(b, c))
        else:
            bit.point_append(b, c)

    print(('\n'.join(map(str, ans))))

if __name__ == "__main__":
    main()
# Original solution
class FenwickTree():
    def __init__(self, n):
        self.n = n
        self.data = [0] * n

    def add(self, p, x):
        #assert 0 <= p < self.n
        p += 1
        while p <= self.n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, r):
        s = 0
        while r:
            s += self.data[r - 1]
            r -= r & -r
        return s

    def range_sum(self, l, r):
        #assert 0 <= l <= r <= self.n
        return self.sum(r) - self.sum(l)

import sys
input = sys.stdin.buffer.readline

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

ft = FenwickTree(N)
res = []

for i in range(N):
    ft.add(i, A[i])

for _ in range(Q):
    q, x, y = list(map(int, input().split()))
    if q:
        res.append(str(ft.range_sum(x, y)))

    else:
        ft.add(x, y)

print(('\n'.join(res)))

# Optimized solution
class FenwickTree():
    def __init__(self, n):
        self.n = n
        self.data = [0] * n

    def add(self, p, x):
        #assert 0 <= p < self.n
        p += 1
        while p <= self.n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, r):
        s = 0
        while r:
            s += self.data[r - 1]
            r -= r & -r
        return s

    def range_sum(self, l, r):
        #assert 0 <= l <= r <= self.n
        return self.sum(r) - self.sum(l)

import sys
input = sys.stdin.buffer.readline

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

ft = FenwickTree(N)
res = []

for i, a in enumerate(A):
    ft.add(i, a)

for _ in range(Q):
    q, x, y = list(map(int, input().split()))
    if q:
        res.append(str(ft.range_sum(x, y)))

    else:
        ft.add(x, y)

print(('\n'.join(res)))