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

# A - Multiple Array
import numpy as np

N = int(input())
A = np.zeros(N, dtype=int)
B = np.zeros(N, dtype=int)
ans = 0
for i in range(N):
    A[i], B[i] = map(int, input().split())
for i in range(1,N+1):
    tmp = -A[N-i] % B[N-i]
    A[:N-i] += tmp * np.ones(N-i, dtype=int)
    ans += tmp
    
print(ans)

### FIXED CODE ###

# A - Multiple Array
import numpy as np

N = int(input())
A = np.zeros(N, dtype=int)
B = np.zeros(N, dtype=int)
ans = 0

for i in range(N):
    A[i], B[i] = map(int, input().split())
for i in range(1,N+1):
    tmp = -(A[N-i] + ans) % B[N-i]
    ans += tmp
    
print(ans)
### BUGGY CODE ###

N = int(input())
P = [int(x) for x in input().split()]
L = [0] * (N + 2)
R = [N + 1] * (N + 2)
I = list(range(N + 1))
for i in range(N):
  I[P[i]] = i
ans = 0
ST = [0] * (N + 2)
def cnt(i):
  ret = 0
  while i:
    ret += ST[i]
    i -= i & (-i)
  return ret
def update(i):
  while i <= N + 1:
    ST[i] += 1
    i += i & (-i)
def ls(idx):
  b = cnt(idx)
  if b == 0:
    return 0
  s = 0
  t = idx
  while t - s > 1:
    m = (s + t) // 2
    if cnt(m) < b:
      s = m
    else:
      t = m
  return t
def rs(idx):
  b = cnt(idx)
  s = idx
  t = N + 1
  while t - s > 1:
    m = (s + t) // 2
    if cnt(m) > b:
      t = m
    else:
      s = m
  return t
for i in range(N, 0, -1):
  index = I[i]
  idx = index + 1
  L[idx] = ls(idx)
  R[idx] = rs(idx)
  L[R[idx]] = idx
  R[L[idx]] = idx
  update(idx)
  ans += i * ((idx - L[idx]) * (R[R[idx]] - R[idx]) + (L[idx] - L[L[idx]]) * (R[idx] - idx))
print(ans)

### FIXED CODE ###

N = int(input())
P = [int(x) for x in input().split()]
L = [0] * (N + 2)
R = [N + 1] * (N + 2)
I = list(range(N + 1))
for i in range(N):
  I[P[i]] = i
ans = 0
ST = [0] * (N + 2)
def cnt(i):
  ret = 0
  while i:
    ret += ST[i]
    i -= i & (-i)
  return ret
def update(i):
  while i <= N + 1:
    ST[i] += 1
    i += i & (-i)
def ls(idx):
  b = cnt(idx)
  if b == 0:
    return 0
  s = 0
  t = idx
  while t - s > 1:
    m = (s + t) // 2
    if cnt(m) < b:
      s = m
    else:
      t = m
  return t
def rs(idx):
  b = cnt(idx)
  s = idx
  t = N + 1
  while t - s > 1:
    m = (s + t) // 2
    if cnt(m) > b:
      t = m
    else:
      s = m
  return t
for i in range(N, 0, -1):
  index = I[i]
  idx = index + 1
  L[idx] = ls(idx)
  R[idx] = rs(idx)
  L[R[idx]] = idx
  R[L[idx]] = idx
  update(idx)
  ans += i * ((idx - L[idx]) * (R[R[idx]] - R[idx]) + (L[idx] - L[L[idx]]) * (R[idx] - idx))
print(ans)
### BUGGY CODE ###

s = input()
k = int(input())


list_pair = []
i = 0
while i <= len(s):
    for j in range(i+1,len(s)+1):
        list_pair.append(s[i:j])
    i = i + 1

list_pair = list(set(list_pair))

for i in range(k-1):
    list_pair.remove(min(list_pair))

print(min(list_pair))

### FIXED CODE ###

s = input()
k = int(input())


list_pair = []
i = 0
while i <= len(s):
    for j in range(1,min(len(s)-i+1,k+1)):
#        print(j,s[i:i+j])
        list_pair.append(s[i:i+j])
    i = i + 1

list_pair = list(set(list_pair))

list_pair.sort()
print(list_pair[k-1])
### BUGGY CODE ###

n = int(input())
s = input()
s = [s[i:i+1] for i in range(n)]
mcost = 10 ** 9
for i in range(n):
  cost = s[0:i].count('W')
  cost += s[i + 1:n].count('E')
  if mcost > cost:
    mcost = cost
print(mcost)

### FIXED CODE ###

n = int(input())
s = input()
s = [s[i:i+1] for i in range(n)]
lcost = [0 for _ in range(n)]
rcost = [0 for _ in range(n)]
if s[0] == 'W':
  lcost[0] = 1
if s[-1] == 'E':
  rcost[-1] = 1
for i in range(1, n):
  if s[i] == 'W':
    lcost[i] = lcost[i - 1] + 1
  else:
    lcost[i] = lcost[i - 1]
for i in range(2, n + 1):
  if s[-i] == 'E':
    rcost[-i] = rcost[-i + 1] + 1
  else:
    rcost[-i] = rcost[-i + 1]
mincost = min(lcost[-1], rcost[0])
#print(lcost)
#print(rcost)
for i in range(1, n - 1):
  hoge = lcost[i - 1] + rcost[i + 1]
  if hoge < mincost:
    mincost = hoge
print(mincost)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from decimal import *
import numpy as np


getcontext().prec = 2

L = int(input())
L = Decimal(L)

x=y=z=0
x = Decimal(x)
y = Decimal(y)
z = Decimal(z)


p = 0.01
p = Decimal(p)

for x in np.arange(p,L+1,p):
    for y in np.arange(p,L+1,p):
        z = L-(x+y)
        V = x*y*z
        
        if x*y*z < V:
            V = x*y*z


print(V)

### FIXED CODE ###

L = int(input())

x=y=z=0

x=y=z=L/3

V = x*y*z




print(V)
### BUGGY CODE ###

N = int(input())
A = map(int, input().split())
answer = 1
for i in A:
    answer *= i

if answer > 1e18:
    print(-1)
else:
    print(answer)

### FIXED CODE ###

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

for i in A:
    answer = answer * i
    if i == 0:
        print(0)
        break
    if answer > 10 **18:
        print(-1)
        break
else:
        print(answer)
### BUGGY CODE ###

# フェルマーの小定理
K = int(input())
S = input()

m = 1000000007

l = len(S)
result = 0

a = pow(26, K, m)
inv26 = pow(26, -1, m)
b = 1
c = 1
d = 1
for i in range(K + 1):
    # result += pow(26, K - i, m) * mcomb(len(S) - 1 + i, i) * pow(25, i, m)
    result += a * (b * pow(c, m - 2, m)) * d
    result %= m
    a *= inv26
    a %= m
    b *= l + i
    b %= m
    c *= i + 1
    c %= m
    d *= 25
    d %= m
print(result)


### FIXED CODE ###

# フェルマーの小定理
K = int(input())
S = input()

m = 1000000007


def make_factorial_table(n):
    result = [0] * (n + 1)
    result[0] = 1
    for i in range(1, n + 1):
        result[i] = result[i - 1] * i % m
    return result


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m


fac = make_factorial_table(len(S) + K)

result = 0
for i in range(K + 1):
    result += pow(26, i, m) * mcomb(len(S) - 1 + K - i, len(S) - 1) * pow(25, K - i, m)
    result %= m
print(result)
### BUGGY CODE ###

import numpy as np
H, W, D = list(map(int, input().split()))

px, py = np.zeros(H*W+1, dtype=int), np.zeros(H*W+1, dtype=int)
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        px[A[j]] = i
        py[A[j]] = j

d = np.zeros(H*W+1, dtype=int)
for i in range(D+1, H*W+1):
    d[i]= d[i-D]+abs(px[i]-px[i-D])+abs(py[i]-py[i-D])

Q = int(input())

for i in range(Q):
    L, R = list(map(int, input().split()))
    print(d[R]-d[L])

### FIXED CODE ###

import numpy as np
H, W, D = list(map(int, input().split()))

px, py = [None for i in range(H*W+1)], [None for i in range(H*W+1)]
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        px[A[j]] = i
        py[A[j]] = j

d = [0 for i in range(H*W+1)]
for i in range(D+1, H*W+1):
    d[i]= d[i-D]+abs(px[i]-px[i-D])+abs(py[i]-py[i-D])

Q = int(input())

for i in range(Q):
    L, R = list(map(int, input().split()))
    print(d[R]-d[L])
### BUGGY CODE ###

N = int(input())
ans = 0
for n in range(N):
    ans += n
print(ans)

### FIXED CODE ###

N = int(input())
if(N % 2 == 0):
    print(int(N/2)*(N-1))
else:
    print(int((N-1)/2)*N)
### BUGGY CODE ###

import queue

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = queue.Queue()
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.put((i, j))
            D[i][j] = 0
    A.append(S)

ans = 0
while not q.empty():
    pos = q.get()
    py, px = pos[0], pos[1]
    ans = max(ans, D[py][px])
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = py + y
        nx = px + x
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if D[ny][nx] < 0:
            D[ny][nx] = D[py][px] + 1
            q.put((ny, nx))
print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = deque([])
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.append((i, j))
            D[i][j] = 0
    A.append(S)

while q:
    pos = q.popleft()
    py, px = pos[0], pos[1]
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = py + y
        nx = px + x
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if D[ny][nx] < 0:
            D[ny][nx] = D[py][px] + 1
            q.append((ny, nx))

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, D[i][j])
print(ans)
### BUGGY CODE ###

mod = 10**9+7
from bisect import bisect
from collections import defaultdict
N,M = 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 n in range(N):
    for m in range(M):
        dp[n][m] = dp[n-1][m]+dp[n][m-1]-dp[n-1][m-1]
        if S[n]==T[m]:
            dp[n][m] += dp[n-1][m-1]+1
        dp[n][m] %= mod

print(dp[N-1][M-1]+1)

### FIXED CODE ###

mod = 10**9+7
from bisect import bisect
from collections import defaultdict
N,M = 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 n in range(N):
    for m in range(M):
        dp[n][m] = dp[n-1][m]+dp[n][m-1]-dp[n-1][m-1]
        if S[n]==T[m]:
            dp[n][m] += dp[n-1][m-1]+1
        dp[n][m] %= mod

print(dp[N-1][M-1]+1)
### BUGGY CODE ###

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

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

explored = [0] * (n+1)
t = 1
cycle = 0
while True:
    if explored[t] == 2:
        k %= cycle
        explored[t] += 1
    elif explored[t] == 1:
        explored[t] += 1
        cycle += 1
    elif explored[t] == 0:
        explored[t] += 1
    k -= 1

    if k == 0:
        break
    else:
        t = a[t]
    

print(a[t])

### FIXED CODE ###

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

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

explored = [0] * (n+1)
t = 1
cycle = 0
while True:
    if explored[t] == 2:
        k %= cycle
        if k == 0:
            k = cycle
        explored[t] += 1
    elif explored[t] == 1:
        explored[t] += 1
        cycle += 1
    elif explored[t] == 0:
        explored[t] += 1

    k -= 1
    if k == 0:
        break
    else:
        t = a[t]
    

print(a[t])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
mod=10**9+7
for k in range(60):
    count=0
    for a in A:
        count+=int(a&(1<<k)>0)
    ans+=count*(N-count)*(2**k)
print(ans%mod)


### FIXED CODE ###

N=int(input())
A=[format(i,'060b') for i in map(int,input().split())]
ans=0
mod=10**9+7
for k in range(60):
    count=[a[60-1-k] for a in A].count('0')
    ans+=count*(N-count)*(2**k)%mod
print(ans%mod)
### BUGGY CODE ###

N = int(input())
li = list(map(int, input().split()))
ans = "Yes"
for i in range(1, N):
    if li[i] - li[i-1] < -1:
        ans = "No"
        break
    elif li[i] - li[i-1] == -1:
        if i != 1:
            tmp = i -2
            while tmp >= 0:
                if li[i] - li[tmp] <= -2:
                    ans = "No"
                    break
                tmp -= 1
            if ans == "No":
                break
print(ans)

### FIXED CODE ###

N = int(input())
li = list(map(int, input().split()))
ans = "Yes"
count = N - 1
while count >= 1:
    if li[count] - li[count-1] >= 0:
        pass
    elif li[count] - li[count-1] == -1:
        li[count-1] -= 1
    else:
        ans = "No"
        break
    count -= 1
print(ans)
### BUGGY CODE ###

import sys,math
sr = sys.stdin.readline
def I(i=0):return [int(x)-i for x in sr().split()]
L1,L2 = [],[]

N,D,A = I()
for i in range(N):
    X,H = I()
    L1.append([X,math.ceil(H/A)])
L1 = sorted(L1)
ans = 0
j = 1
L2 = [-1]*N
for i in range(N):
    lim = L1[i][0] + 2*D
    for k in range(j,N):
        if L1[k][0] > lim:
            L2[i] = k-1
            j = k-1
            break
        elif k == N-1:
            L2[i] = N-1
            j = N-1
for i in range(N):
    x,h = L1[i] 
    if h > 0:
        ans += h
        for j in range(i,L2[i]+1):
            L1[j][1] -= h
print(ans)

### FIXED CODE ###

import sys,math
sr = sys.stdin.readline
def I(i=0):return [int(x)-i for x in sr().split()]
L1,L2 = [],[]

N,D,A = I()
for i in range(N):
    X,H = I()
    L1.append([X,math.ceil(H/A)])
L1 = sorted(L1)
j = 1
L2 = [-1]*N
for i in range(N):
    lim = L1[i][0] + 2*D
    for k in range(j,N):
        if L1[k][0] > lim:
            L2[i] = k-1
            j = k-1
            break
        elif k == N-1:
            L2[i] = N-1
            j = N-1
ans = 0
a,s = 0,0
for i in range(N):
    x,h = L1[i]
    h -= a
    if h > 0:
        ans += h
        a += h
        L1[i][1] = h
    else:
        L1[i][1] = 0
    while s < N and L2[s] <= i:
        a -= L1[s][1]
        s += 1
print(ans)
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())

mod = 10**9+7
fc = [0]*(2*10**6+2)
fc[0] = 1

for i in range(1, 2*10**6+2):
    fc[i] = fc[i-1]*i%mod
    
inv = [1]*(2*10**6+2)
lst = 2*10**6+1
inv[lst] = pow(fc[lst], mod-2, mod)

for i in range(lst, 0, -1):
    inv[i-1] = (inv[i]*i)%mod

def comb(n, r):
    return ((fc[n]*inv[r])%mod)*inv[n-r]%mod

cum=0
for i in range(r1, r2+1):
    d1 = comb(i+1+c2, c2)
    d2 = comb(i+c1, c1-1)
    cum = (cum+(d1-d2))%mod

print(cum)

### FIXED CODE ###

r1, c1, r2, c2 = map(int, input().split())

mod = 10**9+7
fc = [0]*(2*10**6+2)
fc[0] = 1

for i in range(1, 2*10**6+2):
    fc[i] = fc[i-1]*i%mod
    
inv = [1]*(2*10**6+2)
lst = 2*10**6+1
inv[lst] = pow(fc[lst], mod-2, mod)

for i in range(lst, 0, -1):
    inv[i-1] = (inv[i]*i)%mod

def comb(n, r):
    return ((fc[n]*inv[r])%mod)*inv[n-r]%mod

cum=0
for i in range(r1, r2+1):
    d1 = comb(i+1+c2, c2)
    d2 = comb(i+c1, c1-1)
    cum = (cum+(d1-d2))%mod

print(cum)
### BUGGY CODE ###

n = int(input())
seq = input().strip()
ans = 0
r = []
g = []
b = []
for i in range(len(seq)):
    if seq[i] == 'R':
        r.append(i)
    elif seq[i] == 'G':
        g.append(i)
    else:
        b.append(i)

for i in r:
    for j in g:
        for k in b:
            z,x,c = sorted([i,j,k])
            if x-z != c - x:
                ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
seq = input().strip()
ans = 0
r = set()
g = set()
b = set()
for i in range(len(seq)):
    if seq[i] == 'R':
        r.add(i)
    elif seq[i] == 'G':
        g.add(i)
    else:
        b.add(i)

ans = len(r)*len(g)*len(b)
for i in r:
    for j in g:
        if (i+j) % 2 == 0 and ((i + j) //2) in b:
            ans -= 1
        if max(i,j) + (max(i,j) - min(i,j)) in b:
            ans -= 1
        if min(i,j) - (max(i,j) - min(i,j)) in b:
            ans -= 1
        
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
data = [int(input()) for k in range(n)]
for i in range(n):
	data2 = data.copy()
	data2[i] = 0
	data2.sort()
	print(data2[-1])


### FIXED CODE ###

n = int(input())
data = [int(input()) for k in range(n)]
m1,m2 = sorted(data, reverse=1)[:2]
b = [m2 if x==m1 else m1 for x in data]
print('\n'.join(map(str,b)))
### BUGGY CODE ###

def main():
        N = int(input())
        A = list(map(int, input().split()))
        ans = 1

        for i in range(N):
                ans = ans*A[i]

        if ans>10**18:
                ans = -1

        return ans


if __name__=="__main__":
        ans = main()
        print(ans)

### FIXED CODE ###

def main():
        N = int(input())
        A = list(map(int, input().split()))
        ans = 1

        if 0 in A:
                ans = 0
        else:
                for i in range(N):
                        ans = ans*A[i]
                        if ans>10**18:
                                ans = -1
                                break

        return ans


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

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

A = []
A.append(list('@'*(W+2)))
for i in range(H):
  a = list('@'+input()+'@')
  A.append(a)
A.append(list('@'*(W+2)))

b_count = 0
b_list,w_list = [],[]
for i in range(H+2):
 if((i != 0)and(i != H+1)):
  for j in range(W+2):
   if((j != 0)and(j != W+1)):
    if(A[i][j] == '#'):  b_list.append([i,j])
    elif(A[i][j] == '.'): w_list.append([i,j])

ans = 0
for i in range(len(w_list)):
 tmp_min = float('inf')
 w_y,w_x = w_list[i][0],w_list[i][1]
 for j in range(len(b_list)):
  b_y,b_x = b_list[j][0],b_list[j][1]
  tmp = abs(w_y-b_y)+abs(w_x-b_x)
  tmp_min = min(tmp_min,tmp)
 ans = max(ans,tmp_min)
 
print(ans)      
  

### FIXED CODE ###

from collections import deque

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

by,bx= deque(),deque()
Map = []
Map.append('@'*(W+2))
for i in range(H):
  c = list('@'+input()+'@')
  Map.append(c)
  for j in range(W+2):
    if(c[j] == '#'):
      Map[i+1][j] = 0
      by.append(i+1),bx.append(j)
Map.append('@'*(W+2))      

cnt = 0
while(1):
  if(len(by) == 0):
    break
   
  ny,nx = by.popleft(),bx.popleft()
  vec_y,vec_x = [1,-1,0,0],[0,0,1,-1]
  for i in range(4):
      if(Map[ny+vec_y[i]][nx+vec_x[i]] == '.'):
         Map[ny+vec_y[i]][nx+vec_x[i]] = Map[ny][nx] + 1
         cnt = max(cnt, Map[ny][nx] + 1) 
         by.append(ny+vec_y[i]),bx.append(nx+vec_x[i])
  
print(cnt)
### BUGGY CODE ###

n,m= map(int,input().split())
lr = [0]*m
import numpy as np
for i in range(m):
    lr[i]=list(map(int, input().split()))

#1~10**5
# print(10**5)
allcount = np.zeros(10**5,dtype=np.int)
# print(allcount)
for i in range(m):
    st = lr[i][0]-1
    g = lr[i][1]
    allcount=np.hstack((allcount[:st],allcount[st:g]+1,allcount[g:]))

# print(allcount)

allcount = list(allcount)
print(allcount.count(m))


    



### FIXED CODE ###

n,m= map(int,input().split())
lr = [0]*m
for i in range(m):
    lr[i]=list(map(int, input().split()))


left = lr[0][0]
right = lr[0][1]
for i in range(1,m):
    if left < lr[i][0]:
        left = lr[i][0]
    if right > lr[i][1]:
        right = lr[i][1]
    
    if left > right:
        break




if left > right:
    print(0)

if left <= right:
    print(right-left+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

A=a.count(1)
B=a.count(2)
C=a.count(3)


dp=[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
def c():
    for k in range(C+1):
        for j in range(B+C+1-k):
            for i in range(n+1-k-j):
                if i==0 and j==0 and k==0:
                    continue
                res=n
                if i>0:
                    res+=i*dp[i-1][j][k]
                if j>0:
                    res+=j*dp[i+1][j-1][k]
                if k>0:
                    res+=k*dp[i][j+1][k-1]
                dp[i][j][k]=res/(i+j+k)
    print(dp[A][B][C])
c()

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

A=a.count(1)
B=a.count(2)
C=a.count(3)

dp=[[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
def c():
    for k in range(C+1):
        for j in range(B+C+1-k):
            for i in range(n+1-k-j):
                if i==0 and j==0 and k==0:
                    continue
                res=1.0*n
                if i>0:
                    res+=i*dp[i-1][j][k]
                if j>0:
                    res+=j*dp[i+1][j-1][k]
                if k>0:
                    res+=k*dp[i][j+1][k-1]
                dp[i][j][k]=res/(i+j+k)
    print(dp[A][B][C])
c()
### BUGGY CODE ###

N = int(input())
tmp = [[] for i in range(N + 1)]
tmp[0] = [0]
s = [1]

for i in range(5):
    s.append(9** (i + 1))
for i in range(6):
    s.append(6** (i + 1))
s.sort()

for i in range(1, N + 1):
    t_l = []
    for j in range(len(tmp[i - 1])):
        for k in range(12):
            a = tmp[i - 1][j] + s[k]
            if a <= N:
                t_l.append(a)
    tmp[i].extend(t_l)
    if N in tmp[i]:
        break
print(i)

### FIXED CODE ###

N = int(input())
tmp = [-1 for i in range(N + 1)]
tmp[0] = 0
s = [1]

for i in range(5):
    s.append(9** (i + 1))
for i in range(6):
    s.append(6** (i + 1))

for i in range(1, N+1):
    for j in range(N+1):
        if tmp[j] == i - 1:
            for k in range(12):
                a = j + s[k]
                if a <= N and tmp[a] == -1:
                    tmp[a] = i
    if tmp[N] > -1:
        break
print(i)
### BUGGY CODE ###

s = input()
dp = [[0 for _ in range(len(s) + 1)] for _ in range(4)]
# 0文字目までで0個の照合が住んだ数
dp[0][0] = 1
for i in range(0,4):
  for j in range(1, len(s) + 1):
    # ABCを進めない道
    if s[j-1] == '?':
      dp[i][j] += dp[i][j - 1] * 3
    else:
      dp[i][j] += dp[i][j - 1]
    # ABCを進める道
    if 0 < i and (s[j - 1] == '?' or s[j - 1] == 'ABC'[i - 1]):
      dp[i][j] += dp[i - 1][j - 1]

print(dp[3][len(s)] % 1000000007)


### FIXED CODE ###

s = input()
dp = [[0 for _ in range(len(s) + 1)] for _ in range(4)]
# 0文字目までで0個の照合が住んだ数
dp[0][0] = 1
for i in range(0,4):
  for j in range(1, len(s) + 1):
    # ABCを進めない道
    if s[j-1] == '?':
      dp[i][j] += dp[i][j - 1] * 3
    else:
      dp[i][j] += dp[i][j - 1]
    # ABCを進める道
    if 0 < i and (s[j - 1] == '?' or s[j - 1] == 'ABC'[i - 1]):
      dp[i][j] += dp[i - 1][j - 1]
    dp[i][j] %= 1000000007

print(dp[3][len(s)])
### BUGGY CODE ###

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

ans = 0

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

print(ans)

### FIXED CODE ###

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

result = 0

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

S = input()
K = int(input())
n=1
while n <= 5000e12:
    if len(S) > K:
        S = S[:K-1]
    str_new_number = ""
    for str_number in S:
        number = int(str_number)
        str_new_number = str_new_number + str_number*number
    S = str_new_number
    n += 1
print(S[K-1])


### FIXED CODE ###

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

k = 1
while k <= K:
    if S[k-1] != "1":
        print(S[k-1])
        break
    k += 1
else:
    print(1)
### BUGGY CODE ###

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

for i in range(1,n+1):
    print(a.count(i))


### FIXED CODE ###

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

ans = [0 for i in range(n)]
for i in a:
    ans[i-1] += 1

for i in ans:
    print(i)
### BUGGY CODE ###

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

happiness = 0

li = []
lamp = 1
for i in range(n-1):
    if s[i] == s[i+1]:
        lamp += 1
    else:
        li.append(lamp)
        lamp = 1
li.append(lamp)

flag = False
num = 1
while k != 0:
    if len(li) == 2 and k > 0:
        print(n-1)
        quit()
    for i in range(1, len(li)-1):
        if li[i] == num:
            a = li[i-1] + li[i] + li[i+1]
            li[i-1:i+2] = [a]
            k -= 1
            flag = True
            break
        flag = False
    if flag == False:
        num += 1
    if len(li) == 2:
        break

for i in li:
    happiness += i-1

print(happiness)



### FIXED CODE ###

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

s = list(s)

li = []
que = []
for i in range(n-1):
    if s[i] != s[i+1]:
        li.append(i)
li.append(n-1)
if len(li) == 1:
    print(n-1)
    exit()

for i in range(0,len(li)-1, 2):
    if k > 0:
        char = s[li[i]]
        a = s[li[i]+1:li[i+1]+1]
        s[li[i]+1:li[i+1]+1] = char * (li[i+1] - li[i])
    k -= 1

happiness = 0

for i in range(n):
    if i == 0:
        if s[i] == 'R' and s[i+1] == 'R':
            happiness +=1
    elif i == n-1:
        if s[i] == 'L' and s[i-1] == 'L':
            happiness += 1
    else:
        if s[i] == 'R' and s[i + 1] == 'R':
            happiness += 1
        elif s[i] == 'L' and s[i - 1] == 'L':
            happiness += 1

print(happiness)