Harryxun/stf_run huggingface dataset:
import sys

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

    a, b, m = input().split()
    a, b, m = int(a), int(b), int(m)
    alist = input().split()
    blist = input().split()

    waribiki = [input().split() for _ in range(m)]
    
    res = [200000] * 200001
    count = 0
    for i in range(a):
      for j in range(b):
        res[count] = int(alist[i]) + int(blist[j])
        count += 1

    for i in range(m):
        res[count] = int(alist[int(waribiki[i][0])-1]) + int(blist[int(waribiki[i][1])-1]) - int(waribiki[i][2])
        count += 1
      
    print(min(res))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

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

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

    waribiki = [input().split() for _ in range(m)]
    
    res = [200000] * (m + 1)
    count = 0

    for i in range(m):
        res[count] = alist[int(waribiki[i][0])-1] + blist[int(waribiki[i][1])-1] - int(waribiki[i][2])
        count += 1

    res[count] = min(alist) + min(blist)
      
    print(min(res))


if __name__ == '__main__':
    main()
N, M = map(int, input().split())
p_S = []
for i in range(0,M):
    a, b = input().split()
    a = int(a)
    p_S.append([a,b])
s, t = 0, 0
res = []
for i in range(0,N):
    res.append([i,0])
for i in range(0,M):
    if p_S[i][1] == "WA":
        res[p_S[i][0]][1] = res[p_S[i][0]][1]+1
    elif res[p_S[i][0]][1] >= 0:
        s, t = s+1, t+res[p_S[i][0]][1]
        res[p_S[i][0]][1] = -1
print(s, t)

### FIXED CODE ###

N, M = map(int, input().split())
p, S = [0]*M, [0]*M
for i in range(0,M):
    p[i], S[i] = input().split()
    p[i] = int(p[i])
s, t = 0, 0
res = []
for i in range(0,N):
    res.append([i,0])
for i in range(0,M):
    if S[i] == "WA":
        res[p[i]-1][1] = res[p[i]-1][1]+1
    elif res[p[i]-1][0] != -1:
        s, t = s+1, t+res[p[i]-1][1]
        res[p[i]-1][0] = -1
print(s, t)
import math
from collections import defaultdict
N = int(input())
d = defaultdict(int)
def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial):
            input_list[s] = False
l = sieve_of_erastosthenes(int(pow(N,0.5))+2)
cnt = 0
while N != 1 and cnt<len(l):

    while l[cnt] and N%cnt == 0:
        d[cnt] += 1
        N //=cnt
    cnt += 1
ans = 0
for i in d.values():
    tmp = 1
    while i - tmp >= 0:
        i -= tmp
        tmp += 1
        ans += 1
print(ans)

### FIXED CODE ###

import copy
from collections import defaultdict

N = int(input())
tmp = copy.copy(N)
d = defaultdict(int)
if N == 1:
    print(0)
    exit()
for i in range(2, int(N ** 0.5) + 3):
    while N % i == 0:
        N //= i
        d[i] += 1
if N > 1:
    d[N] += 1
ans = 0
for i in d.values():
    tmp = 1
    while i - tmp >= 0:
        i -= tmp
        tmp += 1
        ans += 1
print(ans)
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import numpy as np
N, K = map(int, raw_input().split())
R = []
for i in xrange(K):
    ia, ib = map(int, raw_input().split())
    R.extend([ia, ib])

R = sorted(R)
R.reverse()

count = 1
c = 0
r = R.pop()

for i in xrange(N):
    while count == r and len(R) > 0:
        c += 1
        r = R.pop()

    print c
    count += 1
    c = 0

### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N, K = map(int, raw_input().split())
R = [0] * (10**5+10) 

for i in xrange(N):
     ia, ib = map(int, raw_input().split())
     R[ia] += ib

k = 0
c = 0
while k < K:
    c += 1
    k += R[c]
print c
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

N,M=map(int,input().split())
if M==1:
  print(1)
else:
  primes0=prime_factorize(M)
  keys=list(set(primes0))
  primes={}
  for i in range(len(keys)):
    k=keys[i]
    primes[k]=0
    for j in range(len(primes0)):
      if primes0[j]==k:
        primes[k]+=1

  def cmb(n, k, mod, fac, ifac): #calc nCk under mod
      if n < k or n < 0 or k < 0:
          return 0
      else: 
          k = min(k, n-k)
          return fac[n] * ifac[k] * ifac[n-k] % mod

  def make_tables(mod, n): #Make factorial and inverse tables under mod 
      fac = [1, 1] # factorial table
      ifac = [1, 1] #factorial of inverse table
      inverse = [0, 1] #inverse

      for i in range(2, n+1):
          fac.append((fac[-1] * i) % mod)
          inverse.append((-inverse[mod % i] * (mod//i)) % mod)
          ifac.append((ifac[-1] * inverse[-1]) % mod)
      return fac, ifac

  mod=10**9+7
  fac,ifac = make_tables(mod,N*2)
  ans=1
  for i in range(len(keys)):
    ans*=cmb(N+primes[keys[i]]-1, primes[keys[i]], mod, fac, ifac)
    ans%=mod
  print(ans)

### FIXED CODE ###

x=list(map(int,input().split()))
x.sort()
print(x[-1]*10+x[-2]+x[-3])
print((int(input())+1)//sorted([input() for _ in range(5)])+5)

### FIXED CODE ###

a=sorted([int(input()) for _ in range(5)])
print("Yay!" if a[4]-a[0]<=int(input()) else ":(")
x,y=map(int,input().split())
ma=max(x,y)
for i in range(1,ma):
    if x%i==0 or y%i==0:
        gcd=i
print(max(gcd))


### FIXED CODE ###

if __name__ == '__main__':
    s = input().split()
    if s[0] < s[1]:
        tmp = s[0]
        s[0] = s[1]
        s[1] = tmp
    while True:
        x = int(s[0]) % int(s[1])
        if x==0:
            break
        s[0] = s[1]
        s[1] = x
 
    print (s[1])
import numpy as np

n,m = map(int,input().split())
h = list(map(int,input().split()))
n = int(n)
m = int(m)
#base = np.zeros(n)
seen = np.zeros((n,n))

for i in range(m):
  a,b = map(int,input().split())
  seen[a-1,b-1] = 1
  seen[b-1,a-1] = 1
  
ans = 0
for i in range(n):
  temp = np.multiply(seen[i],h)
  temp_1 = np.max(temp)
  if (h[i] > temp_1) and (temp_1 != 0):
    ans += 1
  elif temp_1 == 0:
    ans += 1
    
print(ans)

### FIXED CODE ###

import numpy as np
n,m = map(int,input().split())
h = list(map(int,input().split()))

base = np.ones(n)

for i in range(m):
  a,b =  map(int,input().split())
  if h[a-1] > h[b-1]:
    base[b-1] = 0
  elif h[a-1] < h[b-1]:
    base[a-1] = 0
  elif h[a-1] == h[b-1]:
    base[a-1] = 0
    base[b-1] = 0
    
print(int(np.sum(base)))
N, L=map(int, input().split(""))
s=[]
for i in range(n):
  s.append(input())
print(''.join(sorted(s)))

### FIXED CODE ###

# 入力
N,L=map(int,input().split())

l=[]
for i in range(N):
  l.append(input())

# ソート
l.sort()

# 出力
print(''.join(l))
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def query2(s,f,c,ct):
    if ct%2==1:
        s.reverse()
    
    if f=='1':
        s=c+s
    else:
        s=s+c
    
    
    #print(s)
    return s
    
def do():
    S=STR()
    q=INT()
    ct=0
    for i in range(q):
        qt=LISTS()
        if qt[0]=='1':
            ct+=1
        else:
            S=query2(S,qt[1],qt[2],ct)
            ct=0
    
    if ct%2==1:
        S.reverse()
    
    print(S)
    
if __name__ == '__main__':
    do()

### FIXED CODE ###

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    s=STR()
    q=INT()
    l=''
    r=''
    ct=0
    for i in range(q):
        fc=LISTS()
        if fc[0]=="1":
            ct+=1
        else:
            if fc[1]=="1":
                if ct%2==0:
                    l=fc[2]+l
                else:
                    r=r+fc[2]
            else:
                if ct%2==1:
                    l=fc[2]+l
                else:
                    r=r+fc[2]
    
    sums=l+s+r
    if ct%2==1:
        ans=""
        for i in range(len(sums)-1,-1,-1):
            ans=ans+sums[i]
    else:
        ans=sums
    
    print(ans)
                
if __name__ == '__main__':
    do()
N = int(input())
A = (input().split())
i_count = 0
test = []
 for i in A:
  num = int(i) % 2
  if num == 0 :
    test.append(i)
 
 for i in test:
  num3 = int(i) % 3
  num5 = int(i) % 5
  if num3 == 0 or num5 ==0:
    i_count += 1
 
 if i_count == len(test):
  print("APPROVED")
else:
  print("DENIED")

### FIXED CODE ###

#入力
N = int(input())
A = list(map(int,input().split()))
#2で割り切れるものいれるリスト,要素として0は入らないのでとりあえず0
B = [0 for _ in range(N)]
#2で割り切れるリストの数カウント
count = 0
#2で割り切れるリストに偶数要素を代入&要素数カウント
for i in range(N):
  if A[i] % 2 == 0:
    B[i] = A[i]
    count += 1
#0は後からいれた要素ではありえないので削除
C = [i for i in B if i != 0]
#3と5のどちらでも割り切れない場合はだめ
flag = 0
for i in range(count):
  if C[i] % 3 != 0 and C[i] % 5 != 0:
    flag += 1
if flag == 0:
  print('APPROVED')
else:
  print('DENIED')
import numpy as np

n, w = list(map(int,input().split()))
w_v = [list(map(int,input().split())) for i in range(n)]
#dp = [[0] * (10**9+1) for i in range(101)]
dp = np.zeros((100,10**9+1),dtype=np.int64)

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

    dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[n][w])


### FIXED CODE ###

n, W = list(map(int,input().split()))
w_v = [list(map(int,input().split())) for i in range(n)]
w = [w_v[i][0] for i in range(n)]
v = [w_v[i][1] for i in range(n)]
inf = 10**9+1
dp = [[inf] * (sum(v)+1) for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
  for j in range(sum(v)+1):
    if j - v[i] >= 0:
      dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i])

    dp[i+1][j] = min(dp[i+1][j], dp[i][j])


for i in range(sum(v)+1):
  if dp[n][i] > W:
    pass
  else:
    ans = i
print(ans)
h = 0
w = 0
list1 = []

def dfs(x, y, f):
    list1[y] = list1[y][:x] + '1' + list1[y][x+1:]

    if y - 1 >= 0:
        if list1[y - 1][x] == f:
            dfs(x, y - 1, f)
    if y + 1 < h:
        if list1[y + 1][x] == f:
            dfs(x, y + 1, f)
    if x - 1 >= 0:
        if list1[y][x - 1] == f:
            dfs(x - 1, y, f)
    if x + 1 < w:
        if list1[y][x + 1] == f:
            dfs(x + 1, y, f)
    return 1

while True:
    h, w = list(map(lambda x: int(x),input().split(" ")))
    if 0 in (h, w):
        break
    n = 0
    for i in range(0, h):
        list1.append(input())
    for i in range(0, h):
        for j in range(0, w):
            if list1[i][j] != '1':
                n += dfs(j, i, list1[i][j])
    print(n)
    list1=[]

### FIXED CODE ###

h = w = 0
slist =[]
list1=[]
def dfs(f):
    while True:
        if len(slist) == 0:
            return 1
        coordinate= slist.pop()
        #print(coordinate)
        x = coordinate[0]
        y = coordinate[1]

        list1[y] = list1[y][:x] + '1' + list1[y][x + 1:]
        if x + 1 < w:
            if list1[y][x + 1] == f:
                slist.append([x + 1,y])
        if x - 1 >= 0:
            if list1[y][x-1] == f:
                slist.append([x - 1, y])
        if y + 1 < h:
            if list1[y + 1][x] == f:
                slist.append([x, y + 1])
        if y -1 >= 0:
            if list1[y -1][x] == f:
                slist.append([x, y - 1])

while True:
    h, w = list(map(lambda x: int(x),input().split(" ")))
    if 0 in (h, w):
        break
    n = 0
    for i in range(0, h):
        list1.append(input())
    for i in range(0, h):
        for j in range(0, w):
            if list1[i][j] != '1':
                slist.append([j,i])
                n += dfs(list1[i][j])
            #print(list1)
    print(n)
    list1=[]
n = int(input())
a = sorted(map(int,input().split()))
b = [(a[i + 1] - a[i], i) for i in range(n -1)]
b.sort(key = lambda x:x[0])
if b[0][1] < n - 2:print((a[-1] + a[-2]) / c)
elif b[0][1] == n - 3:
    if b[1][1] == n - 2:print(max((a[-1] + a[-2]) / b[2][0], (a[-1] + a[-4]) / b[0][0], (a[-3] + a[-4]) / b[1][0]))
    else:print(max((a[-1] + a[-2]) / b[1][0], (a[-1] + a[-4]) / b[0][0]))
else:
    if b[1][1] == n - 3:print(max((a[-1] + a[-2]) / b[2][0], (a[-1] + a[-4]) / b[1][0], (a[-3] + a[-4]) / b[0][0]))
    else:print(max((a[-1] + a[-2]) / b[1][0], (a[-3] + a[-4]) / b[0][0]))


### FIXED CODE ###

n = int(input())
a = sorted(map(int,input().split()))
b = [(a[i + 1] - a[i], i) for i in range(n -1)]
b.sort(key = lambda x:x[0])
if b[0][1] < n - 2:print((a[-1] + a[-2]) / b[0][0])
elif b[0][1] == n - 3:
    if b[1][1] == n - 2:print(max((a[-1] + a[-2]) / b[2][0], (a[-1] + a[-4]) / b[0][0], (a[-3] + a[-4]) / b[1][0]))
    else:print(max((a[-1] + a[-2]) / b[1][0], (a[-1] + a[-4]) / b[0][0]))
else:
    if b[1][1] == n - 3:print(max((a[-1] + a[-2]) / b[2][0], (a[-1] + a[-4]) / b[1][0], (a[-3] + a[-4]) / b[0][0]))
    else:print(max((a[-1] + a[-2]) / b[1][0], (a[-3] + a[-4]) / b[0][0]))
n, x = map(int, input().split())
l = input().split()
for i in range(n):
    l[i] = int(l[i])

j = 0
sum = 0
while x >= sum:
    sum += l[j]
    j += 1
    
print(j)

### FIXED CODE ###

n, x = map(int, input().split())
l = input().split()
for i in range(n):
    l[i] = int(l[i])

cnt = 1
sum = 0
for i in range(n):
    sum += l[i]
    if sum > x:
        break
    cnt += 1
    
print(cnt)
n = input()
p = [0 for raw in range(101)]
m = [[0 for col in range(n+1)] for row in range(n+1)] 
for i in range(1,n+1):
  m[i][i] = 0

  p[i-1], p[i] = map(int, raw_input().split())

for m in range(2,n+1):
  for i in range(1,n-m+1+1):
    j = i + m - 1
    m[i][j] = 999999999999999
    for k in range(i,j-1+1):
      m[i][j] = min(m[i][j], m[i][k] + m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j])

print m[1][n]

### FIXED CODE ###

n = int(raw_input())
p = [0 for i in range(0, 101)]
m = [[0 for i in range(0, 101)] for j in range(0, 101)]
for i in range(1, n+1):
    p[i-1], p[i] = map(int, raw_input().split())
     
for l in range(2, n+1):
    for i in range(1, n-l+2):
        j = i+l-1
        m[i][j] = float("inf")
        for k in range(i, j):
            m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j])
 
print m[1][n]
n, m = map(int,input().split())

la = []
for i in range(n):
    a, b = map(int, input().split())
    la.append((a,b))

ca = []
for i in la:
    a, b = map(int, input().split())
    ca.append((a,b))

for i in ca:
    mi = 1000000001
    ans = 0
    for j in range(len(ca)):
        if abs(i[0]-ca[j][0]) + abs(i[1]-ca[j][1]) < mi:
            mi = abs(i[0]-ca[j][0]) + abs(i[1]-ca[j][1])
            ans = j+1
    print(ans)



### FIXED CODE ###

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

la = []
for i in range(n):
    a, b = map(int, input().split())
    la.append((a,b))

ca = []
for i in range(m):
    a, b = map(int, input().split())
    ca.append((a,b))

for i in range(len(la)):
    mi = 1000000001
    ans = 0
    for j in range(len(ca)):
        p = abs(la[i][0]-ca[j][0]) + abs(la[i][1]-ca[j][1])
        if  p < mi:
            mi = p
            ans = j+1
    print(ans)
b = input()
aa = {"A":"T","T":"A","G":"C","C","G"}
print(aa[b])

### FIXED CODE ###

b = input()
aa = {"A":"T", "T":"A", "G":"C", "C":"G"}
print(aa[b])
a,b=int(input())
if a<b:
    print("a<b")
elif a>b:
    print("a>b")
else:
    print("a==b")

### FIXED CODE ###

a,b=map(int,input().split())
if a<b:
    print ("a < b")
elif a>b:
    print ("a > b")
else:
    print ("a == b")
import heapq
n,m=map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
q = []
ans=0
#ヒープソート
heapq.heapify(s)
heapq.heapify(q)
for k in range(m-2,-1,-1):
    if s!=[]:
        #最小値を返す
        p=heapq.heappop(s)
        if p[0]+k<=m:
            #heappush(list,item) listの葉にitemを追加して小さい要素を上に持ち上げる
            heapq.heappush(q,-p[1])
        else:
            heapq.heappush(s,p)
            break
    else:
        break
    if q!=[]:
        #最小値をヒープから取り出す
        p=heapq.heappop(q)
        ans+=-p
print(ans)


### FIXED CODE ###

a,b=map(int, input().split())
print(max(a+b,a-b,a*b))
L,R=map(int,input().split())
a=[]
if R-L>=2019:
	print(0)
else:
	for i in range(L,R+1):
		for j in range(i+1,R+1):
			a.append((i%2019)*(j%2019)%2019)

print(min(a))

### FIXED CODE ###

L,R=map(int,input().split())
a=[]
if R-L>=2019:
	print(0)
else:
	for i in range(L,R+1):
		for j in range(i+1,R+1):
			a.append(((i%2019)*(j%2019))%2019)

	print(min(a))
a, b = input()
if a >= 2*b:
  print(a-2*b)
else:
  print(0)

### FIXED CODE ###

a, b = input().split()
num_a = int(a)
num_b = int(b)
dif = num_a - num_b*2
if dif >= 0:
  print(dif)
else:
  print(0)
N, *p = list(map(int, input().split()))
print(p)
count = 0
for i in range(N):
  if p[i] != i + 1:
    count += 1

if count <= 2:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

N, *P = list(map(int, open(0).read().split()))
count = sum(p != i + 1 for i, p in enumerate(P))

print('YES' if count <= 2 else 'NO')
import sys
input = sys.stdin.readline
s = input().rstrip("\n")
t = input().rstrip("\n")
dic = {"a":[],"b":[],"c":[],"d":[],"e":[],"f":[],"g":[],"h":[],"i":[],"j":[],"k":[],"l":[],"m":[],"n":[],"o":[],"p":[],"q":[],"r":[],"s":[],"t":[],"u":[],"v":[],"w":[],"x":[],"y":[],"z":[]}
for i,c in enumerate(s):
    dic[c] += [i]
else:
    l = i+1
#print(dic)
cnt = 0
ind = -1
ans = 0
for c in t:
    d = dic[c]
    if d:
        if d[-1] > i:
    #    print("c=",c,"d=",d)
        for i in d: #iは各文字のindex 昇順
    #        print("i=",i)
            if ind < i: #もし現在位置<iなら
                ind = i
    #            print("found, ind=",i)
                break
        else:
    #        print("not found")
            cnt += 1
            ind = d[0]
    else:
        ans = -1
        break
        
print(cnt*l+ind+1 if ans > -1 else -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
import bisect

s = input().rstrip()
t = input().rstrip()
d = defaultdict(list)

for i,c in enumerate(s):
    d[c].append(i)
ans = 0
ind = -1
for c in t:
    #print("c=",c,"d[c]=",d[c])
    if not d[c]:
        ans = -1
        break
    ins = bisect.bisect_left(d[c],ind+1)
    if ins < len(d[c]):
        ind =d[c][ins]
     #   print("ins=",ins,end = "")
    else:
      #  print("追加",end = "")
        ans += len(s)
        ind = d[c][0]
    #print("ind=", ind)
    #print()
else:
    ans += ind+1

print(ans)
tree = dict()
cost = dict()

N = int(input())
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = []
        tree[a].append(b)
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = []
        tree[b].append(a)
    cost[(a, b)] = c
    cost[(b, a)] = c
starts = []
ends = []
Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    starts.append(x)
    ends.append(y)

depth = [100000000000001 for i in range(N)]

def dps(position, total_cost):
    if depth[position - 1] > total_cost:
        depth[position - 1] = total_cost
    for next_position in tree[position]:
        if depth[next_position - 1] == 100000000000001:
            dps(next_position, depth[position - 1] + cost[(position, next_position)])

depth[K-1] = 0
dps(K, 0)

for start, end in zip(starts, ends):
    print(depth[start - 1] + depth[end - 1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

tree = dict()
cost = dict()

N = int(input())
for i in range(N - 1):
    a, b, c = map(int, input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = []
        tree[a].append(b)
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = []
        tree[b].append(a)
    cost[(a, b)] = c
    cost[(b, a)] = c
starts = []
ends = []
Q, K = map(int, input().split())
for i in range(Q):
    x, y = map(int, input().split())
    starts.append(x)
    ends.append(y)

depth = [1000000000000000 for i in range(N)]

def dps(position, total_cost):
    if depth[position - 1] > total_cost:
        depth[position - 1] = total_cost
    for next_position in tree[position]:
        if depth[next_position - 1] == 1000000000000000:
            dps(next_position, depth[position - 1] + cost[(position, next_position)])

depth[K-1] = 0
dps(K, 0)

for start, end in zip(starts, ends):
    print(depth[start - 1] + depth[end - 1])
N=int(input())
B=list(map(int,input().split()))
ans=0
ans+=B[0]+B[-1]
for i in range(N-1):
  ans+=min(B[i],B[i+1])
print(ans)

### FIXED CODE ###

N=int(input())
B=list(map(int,input().split()))
ans=0
ans+=B[0]+B[-1]
for i in range(N-2):
  ans+=min(B[i],B[i+1])
print(ans)
import sys
input = sys.stdin.readline

import math

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N+1):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(math.floor(math.log(b)/math.log(2))+1)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now = now-x
  deme.append(x)
print(*deme[::-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

import math
import bisect

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

L = [(1<<i) -1 for i in range(1,M+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(bisect.bisect_left(L,b)+1)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now -= x
  deme.append(x)
print(*deme[::-1])
N=int(input())
S=input()
DP=[0]*N
l=0
for i,x in enumerate(S):
  DP[i]+=l
    if S[i]=="W":
      l+=1
r=0
for j,y in enumerate(S[::-1]):
  DP[N-1-j]+=r
    if S[N-1-j]=="E":
      r+=1
print(min(DP))
  

### FIXED CODE ###

N=int(input())
S=input()
DP=[0]*N
l=0
for i,x in enumerate(S):
  DP[i]+=l
  if x=="E":
    l+=1
r=0
for i,y in enumerate(S[::-1]):
  DP[N-1-i]+=r
  if y=="W":
    r+=1
print(N-1-max(DP))
n = int(input())
x = input()

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    one_mod = (one_mod * 2 + int(b)) % one_pop_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count


#f の前計算

f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1

#pow2 の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count
    
# n-1, n-2, ,, 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        nxt = one_mod
        #todo
        nxt -= one_pow2[i]
        nxt %= one_pop_count
        print(f[nxt] + 1)
    if x[n-1-i] == '0':
        nxt = zero_mod
        #todo
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt] + 1)
        

### FIXED CODE ###

n = int(input())
x = input()

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_pop_count != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count


#f の前計算

f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1

#pow2 の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count
    
# n-1, n-2, ,, 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt] + 1)