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

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = int(input())

print(0)
l = input()
if l == 'Vacant':
    exit()
print(n-1)
r = input()
if r == 'Vacant':
    exit()

ng,ok = 0,n-1

def is_ok(p):
    print(p)
    q = input()
    if q == 'Vacant':
        exit()
    return (not (p-ng)%2 ^ (l == q), q)

while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    iss,x = is_ok(mid)
    if iss:
        ok = mid
        r = q
    else:
        ng = mid
        l = q


### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = int(input())
print(0)
l = input()
r = l
if l == "Vacant":
    exit()

ng,ok = 0,n
while True:
    mid = (ng + ok) // 2
    print(mid)
    q = input()
    if q == "Vacant":
        exit()
    if (q == l) ^ ((mid - ng)%2 == 1):
        ng = mid
        l = q
    else:
        ok = mid
        r = q
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(0, N-1):
  for j in range(i+1, N):
    ans += A[i]*A[j]
    ans = ans % (10**9 + 7)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
S = sum(A) - A[0]
for i in range(0, N-1):
  ans = (ans + A[i] * S) % (10**9+7)
  S -= A[i+1]
print(ans)
### BUGGY CODE ###

from collections import defaultdict

n, k = map(int, input().split())
k2 = k * 2
requires = defaultdict(lambda: [0, 0])
for i in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)
    requires[x % k2, y % k2][c == 'B'] += 1

ans = 0
for dx in range(k):
    for dy in range(k):
        cnt_w, cnt_b = 0, 0
        for (x, y), (w, b) in requires.items():
            f = ((x + dx) // k + (y + dy) // k) & 1
            if f:
                cnt_w += b
                cnt_b += w
            else:
                cnt_w += w
                cnt_b += b
        ans = max(ans, cnt_b, cnt_w)
print(ans)


### FIXED CODE ###

from itertools import accumulate

n, k = map(int, input().split())
k2 = k * 2
req_b = [[0] * k for _ in range(k)]
req_w = [[0] * k for _ in range(k)]
bc, wc = 0, 0
for i in range(n):
    x, y, c = input().split()
    x, y = int(x), int(y)
    rx, ry = x % k2, y % k2
    b = c == 'B'
    if rx >= k:
        rx -= k
        if ry >= k:
            ry -= k
        else:
            b = not b
    elif ry >= k:
        ry -= k
        b = not b
    if b:
        req_b[rx][ry] += 1
        bc += 1
    else:
        req_w[rx][ry] += 1
        wc += 1

req_b[0] = list(accumulate(req_b[0]))
req_w[0] = list(accumulate(req_w[0]))

for i in range(1, k):
    req_b[i][0] += req_b[i - 1][0]
    req_w[i][0] += req_w[i - 1][0]
    for j in range(1, k):
        req_b[i][j] += req_b[i][j - 1] + req_b[i - 1][j] - req_b[i - 1][j - 1]
        req_w[i][j] += req_w[i][j - 1] + req_w[i - 1][j] - req_w[i - 1][j - 1]

ans = 0
for dx in range(k):
    dxk_b = req_b[dx][-1]
    dxk_w = req_w[dx][-1]
    for dy in range(k):
        b1 = req_b[dx][dy]
        b2 = bc - req_b[k - 1][dy] - dxk_b + b1
        w1 = req_w[dx][dy]
        w2 = wc - req_w[k - 1][dy] - dxk_w + w1
        b, w = b1 + b2, w1 + w2
        ans = max(ans, b + wc - w, w + bc - b)
        # print(dx, dy, b, w, b + wc - w, w + bc - b)
print(ans)
### BUGGY CODE ###

from functools import lru_cache
n,a,b,c,d=map(int,input().split())

mod=10**9+7
fac=[1]*(n+3)
finv=[1]*(n+3)

t=1
for i in range(1,n+3):
    t*=i
    t%=mod
    fac[i]=t

t=1
for i in range(1,n+3):
    t*=pow(i,mod-2,mod)
    t%=mod
    finv[i]=t

@lru_cache()
def comb(a,b):
    if a<b:return 0
    return fac[a]*(finv[a-b]*finv[b]%mod)%mod

dp=[[0 if i else 1 for i in range(n+2)] for _ in range(n+2)]

for i in range(a,b+1):
    for j in range(n+1):
        if not dp[i][j]:continue
        if j:dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod
        p=1
        for k in range(1,1+(n-j)//i):
            if not k<=d:break
            p=((p*comb(n-j-i*(k-1),i)%mod)*pow(k,mod-2,mod))%mod

            if k>=c:
                dp[i+1][j+i*k]+=(dp[i][j]*p%mod)
                dp[i+1][j+i*k]%=mod

print(dp[b+1][n]%mod)


### FIXED CODE ###

from functools import lru_cache
n,a,b,c,d=map(int,input().split())

mod=10**9+7
fac=[1]*(n+3)
finv=[1]*(n+3)

t=1
for i in range(1,n+1):
    t*=i
    t%=mod
    fac[i]=t
t=1
for i in range(1,n+1):
    t*=pow(i,mod-2,mod)
    t%=mod
    finv[i]=t

finvp = [finv]
for i in range(n-1):
    p=finvp[-1]
    q=[p[i]*finv[i]%mod for i in range(n+1)]
    finvp.append(q)

dp = [[0 for _ in range(n+1)] for _ in range(b+1)]
dp[a-1][0] = 1

for i in range(a-1,b):
    for j in range(n+1):
        dp[i+1][j]=dp[i][j]
        for k in range(c,1+min(d,j//(i+1))):
            x=j-k*(i+1)
            dp[i+1][j]+=fac[j]*finv[x]*finvp[k-1][i+1]*finv[k]*dp[i][x]%mod
        dp[i+1][j]%=mod
print(dp[b][n])
### BUGGY CODE ###

def main():
    N = int(input())
    V = list(map(int, input().split()))
    C = list(map(int, input().split()))
    arr = list()
    ans = list()
    for i in range(0, N):
        arr.append(V[i]-C[i])
    for j in range(1 << len(arr)):
        output = []
        for k in range(len(arr)):
            if ((j >> k) & 1) == 1:
                output.append(arr[k])
        if len(output) != 0:
            ans.append(sum(output))
    ma_ans = max(ans)
    if ma_ans > 0:
        print(ma_ans)
    else:
        print(0)
main()

### FIXED CODE ###

def main():
    N = int(input())
    V = list(map(int, input().split()))
    C = list(map(int, input().split()))
    ans = 0
    for i in range(N):
        ans += max(V[i]-C[i], 0)
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math

n = int(input())
y = 0

for i in range(n):
  for j in range(n):
    for k in range(n):
      y_ = math.gcd(math.gcd(i+1, j+1), k+1)
      y += y_
 
print(y)

### FIXED CODE ###

import math
import numpy as np
import numba
import math

n = int(input())

@numba.jit
def main(n):
  lis = np.zeros((n, n, n))
  for i in range(n):
    for j in range(n):
      for k in range(n):
        lis[i][j][k] = math.gcd(math.gcd(i+1, j+1), k+1)
  return int(np.sum(lis))

print(main(n))
### BUGGY CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort()
#dp = [[0 for _ in range(X+1)] for _ in range(N+1)]
dp = [[0] * (X+1) for _ in range(N+1)]

#dp[0] = [x for x in range(X+1)]
#from collections import defaultdict
#dp = [defaultdict(int) for _ in range(N+1)]
dp[0] = [x for x in range(X+1)]

for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        dp[i+1][x] += dp[i][x] * i #% MOD

print(dp[N][X] % MOD)


### FIXED CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort(reverse=True)


dp = {X: 1}

for i, n in enumerate(numbers):
    tmp_dp = {}
    for k, v in dp.items():
        if k < n:
            tmp_dp[k] = (tmp_dp.get(k,0)+v*(N-i))
        else:
            tmp_dp[k]=(tmp_dp.get(k,0)+v*(N-i-1)) 
            tmp_dp[k%n]=(tmp_dp.get(k%n,0)+v) 
    dp = tmp_dp.copy()
        
ans = 0
for k, v in dp.items():
    ans += k *  v

print(ans % MOD)
### BUGGY CODE ###

# ABC110d
import sys
from collections import Counter
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)


ans = 1
pr = Counter(prime_factorize(m))
for i in pr.values():
    # print(i)
    t = combinations_count(n + i - 1, i)
    # print(t)
    ans = ans*t % MOD
# print(pr)
# print(len(pr))
print(ans)

### FIXED CODE ###

# ABC110d
import sys
from collections import Counter
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


dp = dict()


def combinations_count(n, r):
    if dp.get(n) != None and dp.get(n).get(r) != None:
        return dp[n][r]
    if dp.get(n) == None:
        dp[n] = dict()
    dp[n].update({r: math.factorial(
        n) // (math.factorial(n - r) * math.factorial(r))})
    return dp[n][r]


def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)


ans = 1
pr = Counter(prime_factorize(m))
for i in pr.values():
    # print(i)
    t = combinations_count(n + i - 1, i)
    # print(t)
    ans = ans*t % MOD
# print(pr)
# print(len(pr))
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
S = input()
ans = 0
table = collections.defaultdict(list)
for i in range(1, N//2 + 1):
    for j in range(N-i+1):
        table[S[j:j+i]].append(j)
ans = 0
for x in table:
    n = len(x)
    if table[x][-1] - table[x][0] >= n:
        ans = max(ans, n)

print(ans)


### FIXED CODE ###

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

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

s=[[0]*N for i in range(N)]
k=0
for k in range(N):
  s[k]= [0]*k + z_algo(S[k:])

ans=0
for i in range(N):
  for j in range(i+1,N):
    if s[i][j]+i > j:
      ans = max(ans,j - i)
    else:
      ans=max(s[i][j],ans)
    
print(ans)
### BUGGY CODE ###

import math

K = int(input())
ans = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            ans1 = math.gcd(a, b)
            ans2 = math.gcd(ans1, c)
            ans += ans2

print(ans)


### FIXED CODE ###

from math import gcd

K = int(input())
ans = 0
for i in range(1, K + 1):
    ans += i
for i in range(1, K + 1):
    for j in range(i + 1, K + 1):
        ans += gcd(i, j) * 6

for i in range(1, K - 1):
    for j in range(i + 1, K):
        for k in range(j + 1, K + 1):
            ans += gcd(gcd(i, j), k) * 6

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

import math
A, B, N = map(int, input().split())
x = N // 2
def floor(t):
    return math.floor(t)
li = []
if B > N:
    for i in range(1, N + 1):
        li.append(floor((A*i) / B) - A * floor(i/B))
else:
     for i in range(1, B + 1):
        li.append(floor((A*i) / B) - A * floor(i/B))
print(max(li))

### FIXED CODE ###

import math
A, B, N = map(int, input().split())
x = N // 2
def floor(t):
    return math.floor(t)
li = []
if B < N:
    print(floor((A*(B - 1)) / B) - A * floor((B - 1)/B))
elif B == N:
    print(floor((A*(N - 1)) / B) - A * floor((N - 1)/B))
else:
    print(floor((A*(N)) / B) - A * floor((N)/B))
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
arr = np.concatenate(
    [np.array(list(map(int, input().split()))), np.zeros(k, dtype=int)])

INF = 1 << 60

# dp初期化
dp = np.full([k, n + k], INF, dtype=int)
for i in range(k):
    dp[i, i + 1] = np.abs(arr[i + 1] - arr[0])

for i in range(1, n):
    for j in range(1, k + 1):
        dp[j - 1, i + j] = dp[:, i].min() + np.abs(arr[i + j] - arr[i])

print(dp[:, n - 1].min())

### FIXED CODE ###

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

# dp初期化
dp = [float("inf")] * n
dp[0] = 0

for i in range(1, n):
    dp[i] = min(dp[j] + abs(arr[i] - arr[j]) for j in range(max(i - k, 0), i))

print(dp[n - 1])
### BUGGY CODE ###

h,w,m=map(int,input().split())
r=dict()
c=dict()
pos=[]
for i in range(m):
    row,col=map(int,input().split())
    if(row in r):
        r[row]+=1
    else:
        r[row]=1
    if(col in c):
        c[col]+=1
    else:
        c[col]=1

    pos.append(str(row)+str(col))

ans=-100
for i in r.keys():
    for j in c.keys():
        tmp=r[i]+c[j]
        if((str(i)+str(j)) in pos):
            tmp-=1
        ans=max(ans,tmp)
print(ans)

### FIXED CODE ###

h,w,m=map(int,input().split())
row=[0 for i in range(h)]
col=[0 for i in range(w)]
a=[]
for i in range(m):
    r,c=map(lambda x:int(x)-1,input().split())
    a.append([r,c])
    row[r]+=1
    col[c]+=1
rmax=max(row)
cmax=max(col)
ans=rmax+cmax
flag=row.count(rmax)*col.count(cmax)
for i,j in a:
    if(row[i]==rmax and col[j]==cmax):
        flag-=1
if(flag==0):
    ans-=1
print(ans)
### BUGGY CODE ###

def resolve():
    n, k = map(int, input().split())
    S = []
    L, R = [], []
    for _ in range(k):
        l1, r1 = map(int, input().split())
        L.append(l1)
        R.append(r1)

    dp = [0 for i in range(n + 1)]
    dpsum = [0 for i in range(n + 1)]
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, n + 1):
        for j in range(k):
            Li = i - R[j]
            Ri = i - L[j]
            if Ri < 0:
                continue
            Li = max(1, Li)
            dp[i] += dpsum[Ri] - dpsum[Li - 1]  # dp[Li] ~ dp[Ri]

        dpsum[i] = dpsum[i - 1] + dp[i]

    print(dp[n] % 998244353)

resolve()

### FIXED CODE ###

def resolve():
    n, k = map(int, input().split())
    S = []
    L, R = [], []
    for _ in range(k):
        l1, r1 = map(int, input().split())
        L.append(l1)
        R.append(r1)

    dp = [0 for i in range(n + 1)]
    dpsum = [0 for i in range(n + 1)]
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, n + 1):
        for j in range(k):
            Li = i - R[j]
            Ri = i - L[j]
            if Ri < 0:
                continue
            Li = max(1, Li)
            dp[i] += dpsum[Ri] - dpsum[Li - 1]  # dp[Li] ~ dp[Ri]
            dp[i] %=  998244353

        dpsum[i] = (dpsum[i - 1] + dp[i]) % 998244353

    print(dp[n])

resolve()
### BUGGY CODE ###

import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist 小数はfloat
    return list(map(float,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

a = l()

dp = [0 for i in range(n+1)]
dp[0] = 1
ans = [0 for i in range(n+1)]
for i in range(n):
    for j in range(n+1):
        ans[j] = 0
    for j in range(0,n+1):
        if j == 0:
            ans[0] = dp[0]*(1-a[i])
        elif j == n:
            ans[-1] = dp[-2]*a[i]
        else:
            ans[j] = dp[j-1]*a[i] + dp[j]*(1-a[i])
    dp = ans[:]
    

print(sum(dp[(n+1)//2:]))





### FIXED CODE ###

import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist 小数はfloat
    return list(map(float,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

a = l()

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

for i in range(n):
    for j in range(0,n+1):
        if j == 0:
            dp[i+1][0] = dp[i][0]*(1-a[i])
        elif j == n:
            dp[i+1][-1] = dp[i][-2]*a[i]
        else:
            dp[i+1][j] = dp[i][j-1]*a[i] + dp[i][j]*(1-a[i])
    

print(sum(dp[-1][(n+1)//2:]))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
while all( a%2 == 0 for a in A ):
        a = [ i/2 for i in A ]
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
while all(A%2 == 0 for A in a):
	a = [i/2 for i in a ]
	ans += 1
print(ans)
### BUGGY CODE ###

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

a = abs(N-K)

b = abs(a-K)

while a > b:
    a = b
    b = abs(b-K)

print(a)

### FIXED CODE ###

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

a = N%K

b = abs(a-K)

while a > b:
    a = b
    b = abs(b-K)

print(a)
### BUGGY CODE ###

H,W = map(int, input().split())
A = []
for _ in range(H):
    v = 0
    for w, x in zip(range(W), input()):
        if x == "#":
            v |= 1 << w
    A += [ v ]

import numpy as np


A = np.array(A)
WK = np.zeros(A.shape)
MASK = pow(2, W) - 1
MASKSUM = MASK * H
i = 0
while True:
    if np.sum(A) == MASKSUM:
        break
    WK = 0+A
    A[:-1] |= WK[1:]
    A[1:] |= WK[:-1]
    A |= ((WK << 1)&MASK) | (WK >> 1)
    i += 1

print(i)


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)
### BUGGY CODE ###

import itertools

n, k = map(int, input().split())

prices = list(map(int, input().split()))

ans = 9999999999

for i in itertools.combinations(prices, k):
    ans = min(ans, sum(i))

print(ans)

### FIXED CODE ###

import itertools

n, k = map(int, input().split())

prices = list(map(int, input().split()))

prices = sorted(prices)

print(sum(prices[:k]))
### BUGGY CODE ###

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

Number = [A.count(i+1) for i in range(N)]
Total = sum([Number[i]*(Number[i]-1)/2 for i in range(N)])

for Ak in A:
    print(int(Total - Number[Ak-1]+1))



### FIXED CODE ###


import collections

# 入力 : N
# 入力 : A1 A2 ... AN
N = int(input())
A = list(map(int, input().split()))

C = collections.Counter(A)

Total = sum([i*(i-1)/2 for i in C.values()])

for Ak in A:
    print(int(Total - C[Ak]+1))
### BUGGY CODE ###

from bisect import bisect_right
n = input()
a = sorted([int(x) for x in raw_input().split()])
b = sorted([int(x) for x in raw_input().split()])
c = sorted([int(x) for x in raw_input().split()])
ans = 0
for ai in a:
	index = bisect_right(b, ai)
	for bi in b[index:]:
		ans += (n - bisect_right(c, bi))
print ans

### FIXED CODE ###

from bisect import bisect_left, bisect_right
br, bl = bisect_right, bisect_left
n = input()
a = sorted([int(x) for x in raw_input().split()])
b = sorted([int(x) for x in raw_input().split()])
c = sorted([int(x) for x in raw_input().split()])
ans = 0
for bi in b:
	ans += (bl(a, bi) * (n - br(c, bi)))
print ans
### BUGGY CODE ###

import numpy as np
n, q = map(int, input().split())
s = input()
ac_list = np.array([0]*len(s))
i = 0
'''while True:
    ac_index = s[i:].find("AC")
    if ac_index == -1:
        break
    else:
        ac_list[ac_index+i] = 1
        i = ac_index + i + 2'''

for i in range(len(s)-1):
    if s[i:i+2] == 'AC':
        ac_list[i+1:] += 1

# print(ac_list)
for _ in range(q):
    l, r = map(int, input().split())
    print(ac_list[r-1] - ac_list[l-1])

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ac_list = [0]*len(s)

'''while True:
    ac_index = s[i:].find("AC")
    if ac_index == -1:
        break
    else:
        ac_list[ac_index+i] = 1
        i = ac_index + i + 2'''

for i in range(len(s)-1):
    if s[i:i+2] == 'AC':
        ac_list[i+1] = ac_list[i] + 1
    else:
        ac_list[i+1] = ac_list[i]
# print(ac_list)
for _ in range(q):
    l, r = map(int, input().split())
    print(ac_list[r-1] - ac_list[l-1])
### BUGGY CODE ###

def solve():
    #start here
    n, W = map(int,input().split())
    if (W > 10**5+1):
        ans = 0
        for i in range(n):
            w, v = map(int,input().split())
            ans+=v
        print(ans)
    l = []
    dp = [[0 for i in range(W+1)] for j in range(n)]
    for i in range(n):
        w, v = map(int,input().split())
        for j in range(1, W+1):
            if(w>j):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], v+dp[i-1][j-w])
    print(dp[n-1][W])
solve()

### FIXED CODE ###

n, W = map(int,input().split())
dp = [[float('inf') for i in range(10**5+1)] for j in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
ans = 0
for i in range(1, n+1):
    w, v = map(int,input().split())
    for j in range(1, 10**5+1):
        if v>j:
            dp[i][j] = dp[i-1][j]
            continue
        dp[i][j] = min(dp[i-1][j], w+dp[i-1][j-v])
        if dp[i][j] <= W:
            ans = max(ans, j)
print(ans)
### BUGGY CODE ###

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

cnt_all = 0
cnt_right = 0
cnt_minA_all = []
cnt_minA_right = []


for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            cnt_all += 1
            if i < j:
                cnt_right += 1
    else:
        cnt_minA_all.append(cnt_all)
        cnt_all = 0
        cnt_minA_right.append(cnt_right)
        cnt_right = 0

ans = 0
for i in reversed(range(1, K+1)):
    ans += (sum(cnt_minA_all) * (K-i) % (10**9+7) + sum(cnt_minA_right)) % (10**9+7)

print(ans)

### FIXED CODE ###

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

whole = 0
right = 0
whole_list = []
right_list = []

for i in range(N):
    for j in range(N):
        if A[i] > A[j]:
            whole += 1
            if i < j:
                right += 1
    else:
        whole_list.append(whole)
        whole = 0
        right_list.append(right)
        right = 0

mod = 10 ** 9 + 7
ans = sum(right_list) * K
ans += sum(whole_list) * (K - 1) * K // 2

print(ans % mod)
### BUGGY CODE ###

N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]

tmp1 = 1
tmp2 = 1

res = 2
for l in L:
    i = 1
    while True:
        if i * l[0] >= tmp1 and i * l[1] >= tmp2:
            res += (i * l[0] - tmp1) + (i * l[1] - tmp2)
            tmp1 = i * l[0] 
            tmp2 = i * l[1] 
            break
        i += 1
            
print(res)

### FIXED CODE ###

N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]

tmp1 = 1
tmp2 = 1

for l in L:
    i = max(1, tmp1//l[0] if tmp1%l[0] == 0 else tmp1//l[0] + 1, tmp2//l[1] if tmp2%l[1] == 0 else tmp2//l[1] + 1)
    tmp1 = i * l[0] 
    tmp2 = i * l[1] 
            
print(tmp1 + tmp2)