Harryxun/stf_run huggingface dataset:
import sys

sys.setrecursionlimit(10000)

def cmb(n, r, prime):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n % prime

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] = numerator[k - offset] // pivot
                denominator[k] = denominator[k] // pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result = (result % prime) * (numerator[k] % prime)
    result = result % prime
    return result




def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod


def comb(n,k,p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p

x,y = map(int, input().split())

ans = 0
if (x + y) % 3 != 0:
    ans = 0
else:
    a = (x + y) // 3
    b = (2*x - y) // 3
    #ans = cmb(a,b, pow(10,9) + 7)
    ans = mod_combination(a,b,pow(10,9) + 7)

print(ans)


### FIXED CODE ###

def cmb(n, r, prime):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n % prime

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] = numerator[k - offset] // pivot
                denominator[k] = denominator[k] // pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= numerator[k]
    
    result = result % prime
    return result


x,y = map(int, input().split())

ans = 0

if (x + y) % 3 == 0 and 2*x - y >= 0 and 2*y - x >= 0:
    a = (x + y) // 3
    b = (2*x - y) // 3
    ans = cmb(a,b, pow(10,9) + 7)
    #ans = mod_combination(a,b,pow(10,9) + 7)

print(ans)
import math

N,D = map(int,input().split())
cnt = 0
for n in range(N):
    a,b = map(int,input().split())
    if sqrt(a**2 + b**2)-D>=0:
        cnt+=1
print(cnt)

### FIXED CODE ###

import math

N,D = map(int,input().split())
cnt = 0
for n in range(N):
    a,b = map(int,input().split())
    if math.sqrt(a**2 + b**2)-D<=0:
        cnt+=1
print(cnt)
import numpy as np

N = int(input())
ans = 10^12
for a in range(int(np.sqrt(N))):
  if N % a != 0:
    continue
  step = a + N/a -2
  if step < ans:
    ans = step
    
print(str(ans))

### FIXED CODE ###

import numpy as np
 
N = int(input())
ans = 10**12
for i in range(int(np.sqrt(N)+0.5)):
  a = i+1
  if N % a != 0:
    continue
  step = a + int(N/a) -2
  if step < ans:
    ans = step
print(ans)
import re

S = input()

s = re.sub(r"(dreamer)|(eraser)", "", s)
s = re.sub(r"(dream)|(erase)", "", S)

if len(s) == 0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

S = input()

s = S.replace("eraser", "").replace("erase", "").replace("dreamer", "").replace("dream", "")
if len(s) == 0:
    print("YES")
else:
    print("NO")
#need to use a raw input for one line input because they both defer in data types i.e interger and float
a,b = input().split()
#and then convert them back into respective data types
a=int(a)
b=float(b)
#multiply a and b and then round the answer up before printing
mul=a*b
ans=round(mul)
print(ans)


### FIXED CODE ###

# Take both input K & S, then compare the length of S with K and assign it to length
# If the length is <= K print all
# And if length is >K print some of the character

K = int(input())
S = input()

x = 0

length = len(S)

if length <= K:
    print(S)
else:
    while x < K:
        print(S[x], end=(""))
        x += 1
    print("...")
import sys
import collections
import copy
import math

S = input().split()
A = float(S[0])
B = float(S[1])
C = float(S[2])
D = float(S[3])

E = (C * D) / math.gcd(C, D)
X = math.floor(B/C) - math.floor(A/C)
Y = math.floor(B/D) - math.floor(A/D)
Z = math.floor(B/E) - math.floor(A/E)

print(int(B-A-X-Y+Z))


### FIXED CODE ###


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

 #最小公倍数


def lcm(a, b):
    return a*b//gcd(a, b)


S = input().split()
A = int(S[0])
B = int(S[1])
C = int(S[2])
D = int(S[3])

E = lcm(C, D)

X = int(B//C)-int((A-1)//C)
Y = int(B//D)-int((A-1)//D)
Z = int(B//E)-int((A-1)//E)

print(B-A+1-X-Y+Z)
n = int(input())
left = [None for i in range(n)]
right = [None for i in range(n)]
root = set(range(n))

for i in range(n):
    i, l, r = map(int, input().split())
    left[i] = l
    right[i] = r
    root -= {l, r}

    root_n = root.pop()

def Preorder(i):
    if i == -1:
        return
    (l, r) = tree[i]
    print(" {}".format(i), end = "")
    Preorder(left[i])
    Preorder(right[i])

def Inorder(i):
    if i == -1:
        return
    (l, r) = tree[i]
    Inorder(left[i])
    print(" {}".format(i), end = "")
    Inorder(right[i])

def Postorder(i):
    if i == -1:
        return
    (l, r) = tree[i]
    Postorder(left[i])
    Postorder(right[i])
    print(" {}".format(i), end = "")

print("Preorder")
Preorder(root_n)
print()

print("Inorder")
Inorder(root_n)
print()

print("Postorder")
Postorder(root_n)
print

### FIXED CODE ###

n = int(input())
left = [None for i in range(n)]
right = [None for i in range(n)]
root = sum(range(n)) - n - 1

for i in range(n):
    i, l, r = map(int, input().split())
    left[i] = l
    right[i] = r
    root -= (l + r)

def Preorder(i):
    if i == -1:
        return
    print(" {}".format(i), end = "")
    Preorder(left[i])
    Preorder(right[i])

def Inorder(i):
    if i == -1:
        return
    Inorder(left[i])
    print(" {}".format(i), end = "")
    Inorder(right[i])

def Postorder(i):
    if i == -1:
        return
    Postorder(left[i])
    Postorder(right[i])
    print(" {}".format(i), end = "")

print("Preorder")
Preorder(root)
print()

print("Inorder")
Inorder(root)
print()

print("Postorder")
Postorder(root)
print()
A, B = map(int, input().split())
print(100, 100)
grid = [['#'] * 100 for _ in range(50)] + [['.'] * 100 for _ in range(50)]
A -= 1; B -= 1
i, j = 0, 0
while A:
    grid[i][j] = '.'; A -= 1
    if i % 2 == 0:
        if j == 98: i += 1; j = 1
        else: j += 2
    else:
        if j == 99: i += 1; j = 0
        else: j += 2
i, j = 51, 0
while B:
    grid[i][j] = '#'; B -= 1
    if i % 2 == 0:
        if j == 98: i += 1; j = 1
        else: j += 2
    else:
        if j == 99: i += 1; j = 0
        else: j += 2
for r in grid:
    print(''.join(r))

### FIXED CODE ###

A, B = map(int, input().split())
print(100, 100)
grid = [['#'] * 100 for _ in range(50)] + [['.'] * 100 for _ in range(50)]
A -= 1; B -= 1
i, j = 0, 0
while A:
    grid[i][j] = '.'; A -= 1
    if j == 98: i += 2; j = 0
    else: j += 2
i, j = 51, 0
while B:
    grid[i][j] = '#'; B -= 1
    if j == 98: i += 2; j = 0
    else: j += 2
for r in grid:
    print(''.join(r))
a,b= map(int, input().split())

if(c=a-b*2 >=0):
    print(c)
else:
    print(0)


### FIXED CODE ###

a,b= map(int, input().split())
c=a-b*2
if(c>=0):
    print(c)
else:
    print(0)
x,y,z,k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
if x*y*z < 1e6:
    ans = []
    for a in A:
        for b in B:
            for c in C:
                ans.append(a+b+c)
    ans.sort(reverse = True)
    for i in range(k):
        print(ans[i])
else:
    A.append(-1e20)
    B.append(-1e20)
    C.append(-1e20)
    cnt=0
    a = 0
    b = 0
    c = 0
    print(A[0]+B[0]+C[0])
    while(cnt<k-1):
        Adiv = A[0]-A[a+1]
        Bdiv = B[0]-B[b+1]
        Cdiv = C[0]-C[c+1]
        if(Adiv <= Bdiv and Adiv <= Cdiv):
            a+=1
            print(A[a]+B[0]+C[0])
        elif(Bdiv <= Adiv and Bdiv <= Cdiv):
            b+=1
            print(A[0]+B[b]+C[0])
        else:
            c+=1
            print(A[0]+B[0]+C[c])
        cnt+=1


### FIXED CODE ###

x,y,z,k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
num = []
for a in A:
    for b in B:
        num.append(a+b)
num.sort(reverse = True)
num2 = []
for i in range(min(len(num),k)):
    for j in C:
        num2.append(num[i]+j)
num2.sort(reverse = True)
for i in range(k):
    print(num2[i])
n=int(input())

k=n//15

print(int(800n-200k))

### FIXED CODE ###

n=int(input())

k=n//15

print(int(800*n-200*k))
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
if max(e-a) > k:
    print(":(")
else:
    print("Yay!")

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
if e-a > k:
    print(":(")
else:
    print("Yay!")
N,K = map(int,input().split())
a = []
M = 0
for i in range(N):
  a.append(list(map(int,input().split())))
a.sort()
print(a)
for i in range(N):
    K = K-a[i][1]
    if K <= 0:
        print(a[i][0])
        break

### FIXED CODE ###

a,b,c=map(int,input().split())
if a<=c<=b:
  print("Yes")
else:
  print("No")
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def solve():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for i in range(M):
        a,b = map(int, input().split())
        uf.union(a,b)
    print(uf.group_count() - 1)

if __name__ == '__main__':
    solve()






### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def solve():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for i in range(M):
        a,b = map(lambda x: int(x)-1, input().split())
        uf.union(a,b)
    print(uf.group_count() - 1)

if __name__ == '__main__':
    solve()
def factorial(n):
    res = 1
    for i in range(1, n+1):
        res *= i
    return res

n = int(input())
s = []
for i in range(n):
    s.append(list(str(input())))

for i in s:
    i.sort()

s.sort()

tmp = 'a'
total = 0
cnt = 1
for i in s:
    if i == tmp:
        cnt += 1
    elif cnt >= 2:
        total += factorial(cnt)*factorial(cnt-2)/2
        cnt = 1
    tmp = i
    
if cnt >= 2:
    total += factorial(cnt)*factorial(cnt-2)/2

print(int(total))

### FIXED CODE ###

n = int(input())
ss = ["".join(sorted(list(input()))) for _ in range(n)]
ss.sort()

ans = 0
cnt = 0
tmp = ss.pop(0)
for s in ss:
    if tmp == s:
        cnt+=1
    elif cnt > 0:
        tmp = s
        ans+=((cnt+1) * cnt // 2)
        cnt = 0
    else:
        tmp = s
        cnt = 0
print(ans + ((cnt+1) * cnt // 2))
n, m = input().split()
n, m = int(n), int(m)
a = input().split()
a = [int(i) for i in a]
a.sort()
a.reverse()
for i in range(n):
  if a[i] < 1/4m:
    print("No")
    break
  if i == m:
    print("Yes")
    break

### FIXED CODE ###

n, m = input().split()
n, m = int(n), int(m)
a = input().split()
a = [int(i) for i in a]
a.sort()
a.reverse()
s = 1/(4*m)*sum(i for i in a)
for i in range(n):
    if a[i] < s:
        print("No")
        break
    if i == m-1:
        print("Yes")
        break
n = int(input())
s = list(input())

a = s[0]
for i in range(1,len(s)):
    if a != s[i]:
        a = s[i]
    else:
        del s[i]

print(len(s))


### FIXED CODE ###

n = int(input())
s = list(input())

a = s[0]
ans = list(s[0])
for i in range(1,len(s)):
    if a != s[i]:
        a = s[i]
        ans.append(s[i])

print(len(ans))
import math

def main():
    n = int(input())

    area = (n * n) * math.pi
    measure = (n * 2) *math.pi

    print("{0:.6f} {1:.6f}".format(area,measure))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import math

def main():
    n = float(input())

    area = (n * n) * math.pi
    measure = (n * 2) *math.pi

    print("{0:.6f} {1:.6f}".format(area,measure))

if __name__ == "__main__":
    main()
N=int(input())
info=[list(map(int,input().split())) for i in range(N)]
info.sort(key=lambda x:x[2],reverse=True)
for i in range(101):
  for j in range(101):
    height=info[0][2]+abs(info[0][0]-i)+abs(info[0][1]-j)
    for h in range(1,N):
      if info[h][2]+abs(info[h][0]-i)+abs(info[h][1]-j)!=height;break
    print(i,j,height);exit()

### FIXED CODE ###

n=int(input())
data=[list(map(int,input().split())) for i in range(n)]
data.sort(key=lambda x:x[2],reverse=True)
def cal(y,x,datum,height):
  return max(height-(abs(y-datum[1])+abs(x-datum[0])),0)==datum[2]
for i in range(101):
  for j in range(101):
    height=abs(i-data[0][1])+abs(j-data[0][0])+data[0][2]
    flag=0
    for k in data[1:]:
      if not cal(i,j,k,height):
        flag=1
        break
    if flag:pass
    else:print(j,i,height);exit()
import re

a = []
for i in range(5):
    a.append(input().split())
n = int(a[0][0])
q = int(a[0][1])
str = a[1][0]
b = a[2:]
for i in b:
  l = int(i[0])
  r = int(i[1])
  sub_str = str[(l-1):r]
  print(len(re.findall('AC', sub_str)))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
N = input()
if N.index('9') != -1:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

N = input()
try:
  N.index('9')
  print('Yes')
except:
  print('No')
a, b = list(map(int, input().split()))
print([a+b,b-a][b%a])

### FIXED CODE ###

a, b = list(map(int, input().split()))
print([a+b,b-a][b%a!=0])
N = str(input())
Ds = str(input()).split(" ")
answer = 0
 
for di in range(len(Ds)):
  for dii in range(di):
    sum = Ds[di] + Ds[dii] 
    answer += sum
 
print (answer)


### FIXED CODE ###

ABInput = str(input())
 
AB = ABInput.split(" ")
 
A = int(AB[0])
B = int(AB[1])
 
TotalCartain = B * 2
 
if TotalCartain > A or TotalCartain == A:
  print (0)
else:
  print (A-TotalCartain)
X, N = [int(i) for i in input().split()]
if N == 0:
    print(X)
else:
    Ps = set([int(i) for i in input().split()])
    if not X in Ps:
        print(X)

    # print(f'{X} {sorted(Ps)}')
    diff = 0
    while True:
        a = X - diff
        if a not in Ps:
            print(a)
            break
        a = X + diff
        if a not in Ps:
            print(a)
            break
        diff += 1

### FIXED CODE ###

#!python
given = [int(i) for i in input().split()]
ans = [1,2,3,4,5]

for i in range(len(ans)):
    if ans[i] != given[i]:
        print(ans[i])
        break
s,t=list(input())
a,b=list(map(int,input().split()))
u=input()

if u==s:
  print(a-1)
else:
  print(b-1)

### FIXED CODE ###

s,t=list(input().split())
a,b=list(map(int,input().split()))
u=input()
 
if u==s:
  print(str(a-1)+" "+str(b))
else:
  print(str(a)+" "+str(b-1))
n = int(input())
a = [int(input()) for i in range(n)]

for a_i in a:
    b = a.copy()
    b.remove(a_i)
    print(max(b))


### FIXED CODE ###


n = int(input())
a = [int(input()) for i in range(n)]

a_max = max(a)
b = a.copy()
b.remove(a_max)
a_max_second = max(b)

for a_i in a:
    if a_i != a_max:
        print(a_max)
    else:
        print(a_max_second)
|A|,|B|,|C| = list(map(int,input().split()))
a,b,c=list(map(str,input().split()))
if a[|A|-1]==b[0] and b[|B|-1]==c[0] :print('YES')
else:print('NO')

### FIXED CODE ###

a,b,c=list(map(str,input().split()))
if a[-1]==b[0] and b[-1]==c[0]:print('YES')
else:print('NO')
mport math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K=int(input())

i=1
j=1
k=1
r=0
list=[2,3,5,7,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]

while(i<K+1):
  j=1
  f=0
  if(i in list == True):
    f=1
  while(j<K+1):
    k=1
    g=0
    if(j in list == True):
      g=1
    while(k<K+1):
      h=0
      if(k in list == True):
        h=1
      if(i==1 or j==1 or k==1):
        r+=1
      elif(f==1 and g==1 and h==1):
        if(i==j and j==k):
          r+=i
        else:
          r+=1
      else:
        r+=gcd(i, j, k)
      k+=1
    j+=1
  i+=1

print(r)


### FIXED CODE ###

import math

K=int(input())
r=0

for i in range(1,K+1):
  for j in range(1,K+1):
    a=math.gcd(i,j)
    for k in range(1,K+1):
      b=math.gcd(a,k)
      r+=b
print(r)
i=list(map(int,input().split(" ")))
print("{0} {1} {2:0.5f}".format(i[0]//i[1],i[0]%i[1],float(i[0])/float(i[1]))

### FIXED CODE ###

i=list(map(int,input().split(" ")))
print("{0} {1} {2:0.5f}".format(i[0]//i[1],i[0]%i[1],float(i[0])/float(i[1])))
while True:
	n=int(input())
	if n==0:
		break
	A=[]
	for i in range(n):
		A.append(int(input()))
	start=0
	for i in A:
		if i<=0:
			start+=1
		else:
			break
	B=A[start:]
	end=len(B)
	MAX=[0]*end
	for i in range(end):
		for j in range(i+1,end+1):
			s=sum(B[i:j])
			if MAX[i]<s:
				MAX[i]=s
	print(max(MAX))

### FIXED CODE ###

while True:
	n=int(input())
	if n==0:
		break
	A=[]
	for i in range(n):
		x=int(input())
		A.append(x)

	B=[int()]*n
	B[0]=A[0]
	for i in range(1,n):
		if A[i]>=A[i]+B[i-1]:
			B[i]=A[i]
		else:
			B[i]=A[i]+B[i-1]
	print(max(B))
import numpy as np
N=int(input())
A=np.zeros(N+1)
a=list(map(int,input().split()))
for i in range(N+1):
  A[i]=a[i]
v=0
j=0
k=0
for i in reversed(range(0, N+1)):
  j+=A[i]/(2**i)
  if i==N:
    k=A[i]
  else:
    k=min(k+A[i],2**i-np.sum(np.array([A[k]*(2**(i+1-(N-k))) for k in range(i)])))
  v+=k

if j>1:
  print(-1)
else:
  print(int(v))

### FIXED CODE ###

import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=np.sum(A)-np.cumsum(np.append(0, A[:len(A)-1]))
v=0
k=0
for i in range(N+1):
  if i==0:
    if N==0 and A[0]==1:
      k=1
    elif A[0]==0:
      k=1
    else:
      print(-1)
      break
  elif i==N:
    if B[i]<=2*(k-A[i-1]):
      k=B[i]
    else:
      k=0
      print(-1)
      break
  else:
    k=min(2*(k-A[i-1]),B[i])
    if k<=0:
      print(-1)
      break
  v+=k
if k>0:
  print(v)
N, Q = map(int,input().split())
S = input()

atgc_list= []

flag = 0
memo =0

for i in range (len(S)):
    if S[i]=='A':
        flag = 1
    if flag == 1 and S[i] == 'C':
        memo+=1
    if S[i] in ['T','G']:
        flag = 0
    atgc_list.append(memo)
        
atgc_list_np = np.array(atgc_list)

for j in range (Q):
    l, r = map(int,input().split())
    low = atgc_list[l-1]
    high = atgc_list[r-1]
    print(high - low)

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()

atgc_list= []

flag = 0
memo =0

for i in range (len(S)):
    if S[i]=='A':
        flag = 1
    elif flag == 1 and S[i] == 'C':
        memo+=1
        flag = 0
    elif S[i] in ['T','G','C']:
        flag = 0
    atgc_list.append(memo)
        

for j in range (Q):
    l, r = map(int,input().split())
    low = atgc_list[l-1]
    high = atgc_list[r-1]
    print(high - low)
A,B,K = map(int,input().split())
x = [A, B]
x.sort()
res = [1]
res_n=[1]
i = 2

while i <= x[0]:
    if x[0] % i == 0 and x[1] % i == 0:
        x = [x[0] / i, x[1] / i]
        res.append(i)
    else:
        i += 1

print(res[K-1])

### FIXED CODE ###

A,B,K = map(int,input().split())
if A>=B:
  A,B=B,A
new=[]

for i in range(1,A+1):
  if A%i==0 and B%i==0:
    new.append(i)
new.sort()

print(new[-K])
n, m = map(int, input().split())
a = list(map(int, input().split()))

dp = dict.fromkeys(range(n + 1))  # dp[n]: n本使うときの桁数
dp[0] = 0

num = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
anum = sorted(
    dict(filter(lambda e: e[0] in a, num.items())).items(), reverse=True
)  # 後の計算用にsortしておく

for i in range(n):
    dp[i + 1] = dp[i]
    for e in anum:
        if i + 1 - e[1] >= 0:
            dp[i + 1] = max(dp[i + 1], dp[i + 1 - e[1]] + 1)

ans = ""
while dp[n] > 1:
    for e in anum:  # anum は降順sortされているので, 大きい順に確認
        if n - e[1] >= 0:
            if dp[n - e[1]] == dp[n] - 1:
                ans += str(e[0])
                n -= e[1]
                break

# 末尾桁は n =0(ちょうど使い切るように決定)
ans += str(list(filter(lambda e: e[1] == n, anum))[0][0])

print(ans)


### FIXED CODE ###

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

dp = dict.fromkeys(range(n + 1))  # dp[n]: n本使うときの桁数
dp[0] = 0

num = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
anum = sorted(
    dict(filter(lambda e: e[0] in a, num.items())).items(), reverse=True
)  # 後の計算用にsortしておく

for i in range(n):
    dp[i + 1] = -float("inf")
    for e in anum:
        if i + 1 - e[1] >= 0:
            dp[i + 1] = max(dp[i + 1], dp[i + 1 - e[1]] + 1)

ans = ""
while dp[n] > 1:
    for e in anum:  # anum は降順sortされているので, 大きい順に確認
        if n - e[1] >= 0:
            if dp[n - e[1]] == dp[n] - 1:
                ans += str(e[0])
                n -= e[1]
                break

# 末尾桁は n =0(ちょうど使い切るように決定)
ans += str(list(filter(lambda e: e[1] == n, anum))[0][0])

print(ans)
n=input()
a_1 = [int(i) for i in input().split()]
a_2 = [int(i) for i in input().split()]

output = 0
for i in range(1,n+1):
    tmp = sum(a_1[:i]) + sum(a_2[i-1:])
    if tmp > output:
        output = tmp

print(output)

### FIXED CODE ###

n=int(input())
a_1 = [int(i) for i in input().split()]
a_2 = [int(i) for i in input().split()]

output = 0
for i in range(1,n+1):
    tmp = sum(a_1[:i]) + sum(a_2[i-1:])
    if tmp > output:
        output = tmp

print(output)