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

s = input()
q = int(input())
num = 0
ans = "0"

for _ in range(q):
  query = list(input().split())
  if len(query) == 1:
    num += 1
  else:
    if int(query[1]) == 1:
      if num%2 == 0:        
        # 先頭
        ans = query[2] + ans
      else:
        ans = ans + query[2]
    else:
      if num%2 == 0:
        # 後方
        ans = ans + query[2]
      else:
        ans = query[2] + ans
        
mes = ans.replace("0", s)
if num%2 == 0:
  print(mes)
else:
  print(mes[::-1])

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
num = 0
ans = deque(s)

for _ in range(q):
  query = list(input().split())
  if len(query) == 1:
    num += 1
  else:
    if int(query[1]) == 1:
      if num%2 == 0:        
        # 先頭
        ans.appendleft(query[2])
      else:
        ans.append(query[2])
    else:
      if num%2 == 0:
        # 後方
        ans.append(query[2])
      else:
        ans.appendleft(query[2])     

if num%2 == 0:
  print(''.join(ans))
else:
  ans.reverse()
  print(''.join(ans))
### BUGGY CODE ###

from collections import defaultdict

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

d = defaultdict(int)
for i in range(2, M+1):
    while M % i == 0:
        d[i] += 1
        M //= i
    if M == 1:
        break


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


mod = 10**9+7  # 出力の制限
n = 100100
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

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


ans = 1
for v in d.values():
    # print(v, cmb(v+N, N, mod))
    ans *= cmb(v+N-1, N-1, mod)

print(ans % mod)


### FIXED CODE ###

from collections import defaultdict

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

d = defaultdict(int)
for i in range(2, M+1):
    while M % i == 0:
        d[i] += 1
        M //= i
    if M == 1:
        break


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


mod = 10**9+7  # 出力の制限
n = 100100
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

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


ans = 1
for v in d.values():
    # print(v, cmb(v+N, N, mod))
    ans *= cmb(v+N-1, N-1, mod)

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

h,w,m=map(int,input().split())
bomb=sorted([list(map(int, input().split())) for _ in range(m)])
res1=[0 for _ in range(h)]
res2=[0 for _ in range(w)]
for i in range(m):
    res1[bomb[i][0]-1]+=1
    res2[bomb[i][1]-1]+=1
ans1=max(res1)
ans2=max(res2)
ans=ans1+ans2
s1=0
l1=[]
for j in range(h):
    if res1[j]>s1:
            l1=[j+1]
            s1=res1[j]
    elif res1[j]==s1:
            l1.append(j+1)
s2=0
l2=[]
for k in range(w):
    if res2[k]>s2:
            l2=[k+1]
            s2=res2[k]
    elif res2[k]==s2:
            l2.append(k+1)
count=0
for l in range(m):
    if bomb[l][0] in l1 and bomb[l][1] in l2:
        count+=1

if count!=len(l1)*len(l2):
    print(ans)
else:
    print(ans-1)


### FIXED CODE ###

from collections import deque

h,w,m=map(int,input().split())
bomb=[list(map(int, input().split())) for _ in range(m)]
res1=[0]*h
res2=[0]*w
for i in range(m):
    bomb1=bomb[i]
    res1[bomb1[0]-1]+=1
    res2[bomb1[1]-1]+=1
ans1=max(res1)
ans2=max(res2)
ans=ans1+ans2
s1=0
l1=deque()
for j in range(h):
    res3=res1[j]
    if res3>s1:
            l1=[j+1]
            s1=res3
    elif res3==s1:
            l1.append(j+1)
s2=0
l2=deque()
for k in range(w):
    res4=res2[k]
    if res4>s2:
            l2=[k+1]
            s2=res4
    elif res4==s2:
            l2.append(k+1)
l3=set(l1)
l4=set(l2)
count=0

for l in range(m):
    bomb2=bomb[l]
    if bomb2[0] in l3 and bomb2[1] in l4:
        count+=1

if count!=len(l1)*len(l2):
    print(ans)
else:
    print(ans-1)
### BUGGY CODE ###

import itertools
l = []
n,m,q=map(int, input().split())

tmp = 0
max = 0
c = []

for i in range(q):
    c.append([int(j) for j in input().split()])

for i in range(1,m+1):
    l.append(str(i))
a = list(itertools.combinations_with_replacement(l, n))

for k in range(len(a)): 
    for i in range(q):
        if int(a[k][c[i][1]-1]) - int(a[k][c[i][0]-1]) == c[i][2]:
            tmp = tmp + c[i][3]
        if max < tmp:
            max = tmp
    tmp = 0

print(max)


### FIXED CODE ###

import itertools
n,m,q=map(int, input().split())
 
tmp = 0
max = 0
a = []
b = []
c = []
d = []
 
for i in range(q):
  A, B, C, D = map(int, input().split())
  a.append(A)
  b.append(B)
  c.append(C)
  d.append(D)
 
nums = range(1, m + 1)
 
for retsu in itertools.combinations_with_replacement(nums, n): 
    for i in range(q):
        if int(retsu[b[i]-1]) - int(retsu[a[i]-1]) == c[i]:
            tmp = tmp + d[i]
        if max < tmp:
            max = tmp
    tmp = 0
 
print(max)
### BUGGY CODE ###

import sys
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
if s[0][0]=="#" or s[h-1][w-1]=="#":
  print(-1)
  exit()
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans += 1
s = [["#"] + i + ["#"] for i in s]
s = [["#" for i in range(w+2)]] + s + [["#" for i in range(w+2)]]
pos = [[1, 1, 0]]
for i in range(h*w):
  for j in range(len(pos)):
    x, y, cnt = pos[j]
    if x == h and y == w:
        print(ans-(cnt+1))
        sys.exit()
    s[x][y] = "~"
    if s[x-1][y] == ".":
        pos.append([x-1, y, cnt+1])
    if s[x+1][y] == ".":
        pos.append([x+1, y, cnt+1])
    if s[x][y-1] == ".":
        pos.append([x, y-1, cnt+1])
    if s[x][y+1] == ".":
        pos.append([x, y+1, cnt+1])
print(-1)

### FIXED CODE ###

import sys
H,W=map(int,input().split())
L = [[0 for j in range(W)] for i in range(H)]
c=0
for i in range(H):
  a=list(input())
  c+=a.count(".")
  L[i]=a
#幅優先探索？
subete=[[0,0]]
ans = [[] for i in range(H*W+1)]
ans[0].append([0,0])
for i in range(H*W+1):
  for j in range(len(ans[i-1])):
    a,b=ans[i-1][j][0],ans[i-1][j][1]
    if a+1!=H:
      if [a+1,b] not in subete and L[a+1][b]==".":
        ans[i].append([a+1,b])
        subete.append([a+1,b])
    if a!=0:
      if [a-1,b] not in subete and L[a-1][b]==".":
        ans[i].append([a-1,b])
        subete.append([a-1,b])
    if b+1!=W:
      if [a,b+1] not in subete and L[a][b+1]==".":
        ans[i].append([a,b+1])
        subete.append([a,b+1])
    if b!=0:
      if [a,b-1] not in subete and L[a][b-1]==".":
        ans[i].append([a,b-1])
        subete.append([a,b-1])
  if [H-1,W-1] in subete:
    print(c-i-1)
    sys.exit()
print(-1)
### BUGGY CODE ###

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

dic={}
for i in range(97,123):
    for j in range(len(s)):
        if s[j]==chr(i):
            for l in range(j+1,len(s)+1):
                dic[s[j:l]]=1
    if len(dic)>=k:
            break
    
dic=sorted(dic.items(),key=lambda x:x[0])

print(dic[k-1][0])

### FIXED CODE ###

s=input()
kk=int(input())

dic={}
for i in range(len(s)):
    dic[s[i]]=1
    
dic=sorted(dic,key=lambda x:x[0])
check=0
se=set()
for i in dic:
    for j in range(len(s)):
        if s[j]!=i:
            continue
        k=j+1
        se.add(i)
        sss=i
        while k<len(s):
            sss+=s[k]
            se.add(sss)
            k+=1
            if k-j>kk:
                break
    if len(se)>=kk:
        break
se=sorted(list(se))
print(se[kk-1])
### BUGGY CODE ###

n,t = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
dp = [[0]*(t+1) for i in range(n)]
ans = 0
for i in range(n-1):
    for j in range(t+1):
        if j < l[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-l[i][0]]+l[i][1])
    ans = max(ans,dp[i+1][t-1]+l[i+1][1])
print(ans)

### FIXED CODE ###

import numpy as np
n,t = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
dp = np.array([0]*t)
ans = 0
for a,b in l:
    ans = max(ans,dp[-1]+b)
    dp[a:] = np.maximum(dp[a:],dp[:-a]+b)
    
    
print(max(ans,dp[-1]))
### BUGGY CODE ###

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

hw = []
w = [0] * (W+1)
h = [0] * (H+1)
hw = [list(map(int,input().split())) for i in range(M)]
for h_i, w_j in hw:
    # h_i, w_j = map(int, input().split())
    # hw.append([h_i-1, w_j-1])
    h[h_i] += 1
    w[w_j] += 1

a = 0
d = 1
mxh_v = max(h)
mxw_v = max(w)

x = [i for i,j in enumerate(h) if j == mxh_v]
y = [i for i,j in enumerate(w) if j == mxw_v]

for i in x:
    for j in y:
        if not([i,j] in hw):
            print(mxh_v+mxw_v)
            exit()
print(mxh_v+mxw_v-d)

### FIXED CODE ###

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

hw = set()
w = [0] * 3*10**5
h = [0] * 3*10**5

for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.add((h_i-1) + (w_j-1)*3*10**6)
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 1
mxh_v = max(h)
mxw_v = max(w)

x = [i for i,j in enumerate(h) if j == mxh_v]
y = [i for i,j in enumerate(w) if j == mxw_v]

for i in x:
    for j in y:
        if not(i + j*3*10**6 in hw):
            print(mxh_v+mxw_v)
            exit()
print(mxh_v+mxw_v-d)
### BUGGY CODE ###

n,k=map(int, input().split())
l=list(map(int, input().split()))
if k>=n:
    print("0")
    exit(0)

for i in range(k):
    l.remove(max(l))

print(sum(l))


### FIXED CODE ###

n,k=map(int, input().split())
l=list(map(int, input().split()))
if k>=n:
    print("0")
    exit(0)

l.sort()

sum=0
for i in range(n-k):
    sum=sum+l[i]

print(sum)
### BUGGY CODE ###

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

ans = 0
for x in range(k+1):
    if x > s:
        break
    for y in range(k+1):
        xy = x+y
        if xy > s:
            break
        for z in range(k+1):
            xyz = x+y+z
            if xyz > s:
                break
            if xyz == s:
                ans += 1
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
 
ans = 0
for x in range(k+1):
    for y in range(k+1):
        ans += max(0, 0<=s-x-y<=k)
print(ans)
### BUGGY CODE ###

inf = float("inf")

N = int(input())
A = [int(i) for i in input().split()]

bmin = inf
bmax = -inf

for b in range(0, N):
    bmin = min(bmin, A[b] - b)
    bmax = max(bmax, A[b] - b)

bb = inf

mn = round(bmin + bmax)
for d in range(mn, bmin -1, -1):
    df = 0
    for b in range(0, N):
        df = df + abs(A[b] - (d + b))
    if df < bb:
        bb = df
    else:
        break

for d in range(mn, bmax + 1):
    df = 0
    for b in range(0, N):
        df = df + abs(A[b] - (d + b))
    if df < bb:
        bb = df
    else:
        break

print(bb)

### FIXED CODE ###

import numpy as np

N = int(input())
A = [int(i) for i in input().split()]

list = []

for b in range(0, N):
    list.append(A[b] - b)

md = int(np.median(list))

bb = 0
for b in range(0, N):
    bb += abs(list[b] - md)

print(bb)
### BUGGY CODE ###

def binary_search_ceiling(list, len_list, element):
    i = 0
    j = len_list - 1
    while i <= j:
        k = (i + j) // 2
        if list[0] == element:  # k - 1が0にならないので特例
            return 0
        elif list[k - 1] < element <= list[k]:
            return k
        elif list[k] < element < list[k + 1]:
            return k + 1
        elif list[k] < element:
            i = k  # elementがk番とk+1番の間にあるかもしれないのでi = k + 1 ではなくi = k
        else:
            j = k  # 上と同様に考えてj = k

    return None


def main():
    A, B, Q = map(int, input().split())
    INF = 10 ** 11
    s_list = [-2 * INF, -INF] + [int(input()) for i in range(A)] + [INF, 2 * INF]
    t_list = [-2 * INF, -INF] + [int(input()) for i in range(B)] + [INF, 2 * INF]
    x_list = [int(input()) for i in range(Q)]

    len_s_list = A + 4
    len_t_list = B + 4
    for xi in x_list:
        ind_s = binary_search_ceiling(s_list, len_s_list, xi)
        ws = s_list[ind_s - 1]
        es = s_list[ind_s]

        ind_t = binary_search_ceiling(t_list, len_t_list, xi)
        wt = t_list[ind_t - 1]
        et = t_list[ind_t]

        dist_list = [
                     xi - min(ws, wt),
                     max(es, et) - xi,
                     xi + es - wt * 2,
                     xi + et - ws * 2,
                     (es * 2) - wt - xi,
                     (et * 2) - ws - xi
                     ]

        print(min(dist_list))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect as b


def main():
    A, B, Q = map(int, input().split())
    INF = 10 ** 11
    s_list = [-INF] + [int(input()) for i in range(A)] + [INF]
    t_list = [-INF] + [int(input()) for i in range(B)] + [INF]

    len_s = A + 1
    len_t = B + 1

    for i in range(Q):
        xi = int(input())
        ind_s = b.bisect_left(s_list, xi)
        ws = s_list[ind_s - 1]
        es = s_list[ind_s]

        ind_t = b.bisect_left(t_list, xi)
        wt = t_list[ind_t - 1]
        et = t_list[ind_t]

        dist_list = [
                     xi - min(ws, wt),
                     max(es, et) - xi,
                     xi + es - wt * 2,
                     xi + et - ws * 2,
                     (es * 2) - wt - xi,
                     (et * 2) - ws - xi
                     ]

        print(min(dist_list))


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

n = int(input())
A = list(map(int,input().split()))
a=A[0]
for i in range(1,n):
    a = a*A[i]
if(a>10**18):
    a=-1
print(a)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
if(0 in A):
    print(0)
else:
    a=A[0]
    for i in range(1,n):
        a = a*A[i]
        if(a>10**18):
            a=-1
            break
    print(a)
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections

n = int(input())
a = list(map(int,input().split()))
x = [0 for i in range(max(a)+1)]
for i in range(n):
    x[a[i]]+=1
li2 = [0]
li4 = [0]
for i in range(len(x)):
    if x[i]>=4:
        li4.append(i)
    elif x[i]>=2:
        li2.append(i)
ans = li4[-1]**2
ans2 = 0
if len(li2)>=2:
    ans2 = li2[-1]*li2[-2]
else:
    ans2 = 0
print(max(ans,ans2))

### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections

n = int(input())
a = list(map(int,input().split()))
c = collections.Counter(a)
li2 = [0,0]
li4 = [0]
for key,value in c.items():
    if value>=4:
        li4.append(key)
    elif value>=2:
        li2.append(key)
li2.sort()
li4.sort()
ans1 = li2[-1]*li2[-2]
ans2 = li4[-1]**2
ans3 = li4[-1]*li2[-1]
ans = max(ans1,ans2)
ans = max(ans,ans3)
print(ans)
### BUGGY CODE ###

from functools import reduce
from operator import add, mul

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

if p<=10**18:
  print(p)
else:
  print(-1)

### FIXED CODE ###

#A,B,C=(int(x) for x in input().split())
N=int(input())
A=list(map(int, input().split()))


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

if t<=10**18:
  print(t)
else:
  print(-1)
### BUGGY CODE ###

import itertools
import numpy as np
H, W, K = [int(_) for _ in input().split()]
S = np.array(
    [[0] * (W + 1)] + [[0] + list(map(int, input())) for _ in range(H)],
    dtype=np.int64)
cum = S.cumsum(axis=0).cumsum(axis=1)
ans = 10**10
for h in range(H):
    for c in itertools.combinations(range(1, H), h):
        I = np.array([0] + list(c) + [H], dtype=int)
        cum2 = np.diff(cum[I, :], axis=0)
        j = 0
        i = 0
        cnt = h
        while True:
            i += 1
            if i > W:
                break
            if np.max(cum2[:, i] - cum2[:, j]) > K:
                j = i = i - 1
                cnt += 1
        ans = min(ans, cnt)
print(ans)


### FIXED CODE ###

import numpy as np
import itertools
H, W, K = [int(_) for _ in input().split()]
S = np.zeros((H + 1, W + 1), dtype=int)
S[1:, 1:] = [[int(_) for _ in input()] for _ in range(H)]
cum = S.cumsum(axis=0).cumsum(axis=1)
#sum(a,b -> x,y) (1-indexed)
#cum[x][y]+cum[a-1][b-1]-cum[a-1][y]-cum[x][b-1]
ans = 10**10
for bs in itertools.product([True, False], repeat=H - 1):
    bs = [True] + list(bs) + [True]
    idxs = []
    for i, b in enumerate(bs):
        if b:
            idxs += [i]
    cum2 = np.array([cum[i2] - cum[i1] for i1, i2 in zip(idxs, idxs[1:])])
    i = 0
    cnt = sum(bs) - 3
    while i < W:
        di = min(
            np.searchsorted(c[i + 1:] - c[i], K, side='right') for c in cum2)
        if di == 0:
            cnt = 10**10
            break
        i += di
        cnt += 1
    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall

N, *A = map(int, open(0).read().split())
A = list(zip(*[iter(A)] * N))

B = floyd_warshall(A, False).astype(int)

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if A[i][j] > B[i][j]:
            print(-1)
            quit()

        if A[i][j] == B[i][j] and all(B[i][j] != B[i][k] + B[k][j] for k in range(N) if k != i and k != j):
            ans += B[i][j]

print(ans)

### FIXED CODE ###

def WarshallFloyd(M):
    N = len(M)
    M = [m[:] for m in M]
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

N, *A = map(int, open(0).read().split())
A = list(map(list, zip(*[iter(A)] * N)))

B = WarshallFloyd(A)

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if A[i][j] > B[i][j]:
            print(-1)
            quit()

        if A[i][j] == B[i][j] and all(B[i][j] != B[i][k] + B[k][j] for k in range(N) if k != i and k != j):
            ans += B[i][j]

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

from fractions import gcd
a,b=map(int, input().split())

cd=[1]
for i in range(2,gcd(a,b)+1):
    if((a%i == 0)and(b%i == 0)):
        cd.append(i)
        
ans=[1]
for i in range(1,len(cd)):
    for j in range(len(ans)):
        if(gcd(cd[i],ans[j]) != 1):
            break
    else:
        ans.append(cd[i])
print(len(ans))



### FIXED CODE ###

from fractions import gcd
from collections import Counter

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 # +1だと2の倍数にもなっちゃうからね
    if n!=1:
        a.append(n)
    return a

a,b=map(int, input().split())

ab = gcd(a,b)
soinsu = prime_factorize(ab)
sosu = Counter(soinsu).keys()

print(len(sosu)+1)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
B = 0
for i in A:
    if A.count(i) >= 1:
        if A.count(i)%2 == 1:
            B += 1
    else :
        break
print(B)

### FIXED CODE ###

N = int(input())
list = set()
for i in range(N):
    i = int(input())
    if i not in list:
        list.add(i)
    elif i in list:
        list.remove(i)
print(len(list))
### BUGGY CODE ###

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

import math
import itertools
import re

# 入力
N = int(input())
S = str(input())
#M1, D1 = map(int, input().split())

si = ""
cnt = 0
for i in range(1000) :
  
  si = str(i).zfill(3)
  pattern = "^.*"+ si[0] + ".*" + si[1] + ".*" + si[2] + ".*$"
  
  if re.match(pattern, S) :
    cnt += 1

print (cnt)
    

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
import math
import itertools
import re
 
# 入力
N = int(input())
S = str(input())
#M1, D1 = map(int, input().split())
 
si = ""
cnt = 0
for i in range(1000) :
  
  si = str(i).zfill(3)
  
  c = 0
  for x in range(N) :
    if S[x] == si[c] :
      c += 1
      if c == 3 :
        cnt += 1
        break    

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

N,M = map(int,input().split(' '))
A = list(map(int,input().split(' ')))
BC = []
for i in [0]*M:
	#BC.append(list(map(int,input().split(' '))))
	b,c = map(int,input().split(' '))
	A.extend([c]*b)

A.sort(reverse=True)
print(sum(A[:N]))







### FIXED CODE ###

N,M = map(int,input().split(' '))
A = list(map(int,input().split(' ')))
A.sort(reverse=True)
A.append(-1)


ans = 0
BC = [list(map(int,input().split(' '))) for i in [0]*M]
BC.sort(reverse=True, key= lambda x:x[1])
BC.append([0,-1])

i = 0
j = 0
k = N
while(True):
	if k <= 0:
		break
	a = A[i]
	b,c = BC[j]
	if a > c:
		k = k-1
		ans += A[i]
		i = i+1
	else:
		if b < k:
			ans += b*c
			k = k-b
			j = j+1
		else:
			ans += k*c
			break

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

from queue import Queue

#全体に同じものを足すときは累積和を考えたい

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

graph = [set([]) for _ in range(N+1)]

for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]
check[1] = True
for p,x in PX:
    counter[p] += x

def bfs(graph,counter,edge):
    que = Queue()
    que.put(edge)
    while not que.empty():
        p = que.get()
        for e in graph[p]:
            if check[e]:
                continue
            counter[e] += counter[p]
            que.put(e)
            check[e] = True

bfs(graph,counter,1)

ans = " ".join(map(str,counter[1:]))
print(ans)


### FIXED CODE ###

#全体に同じものを足すときは累積和を考えたい

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

graph = [[] for _ in range(N+1)]

for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
parent = [None for _ in range(N+1)]

for p,x in PX:
    counter[p] += x

def dfs(graph,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

dfs(graph,counter,1)

ans = " ".join(map(str,counter[1:]))
print(ans)
### BUGGY CODE ###

n = int(input())
s = len(input())
mod = 10**9+7
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  dp[i][0] = (dp[i-1][0] + dp[i-1][1])%mod
  for j in range(1,n):
    dp[i][j] = (dp[i-1][j-1]*2 + dp[i-1][j+1])%mod
  dp[i][n] = dp[i-1][n-1]*2%mod
s2 = pow(2,s,mod)
rev = pow(s2,mod-2,mod)
print(dp[n][s]*rev%mod)

### FIXED CODE ###

n = int(input())
s = len(input())
mod = 10**9+7
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  dp[i][0] = (dp[i-1][0] + dp[i-1][1])%mod
  for j in range(1,n):
    dp[i][j] = (dp[i-1][j-1]*2 + dp[i-1][j+1])%mod
  dp[i][n] = dp[i-1][n-1]*2%mod
s2 = pow(2,s,mod)
rev = pow(s2,mod-2,mod)
print(dp[n][s]*rev%mod)
### BUGGY CODE ###

N, A, B = [int(v) for v in input().strip().split(" ")]

loop, m = divmod(N, A + B)
cnt_b = 0
cnt_all = 0
for _ in range(loop):
    cnt_b += A
if m < A:
    cnt_b += m
else:
    cnt_b += A
print(cnt_b)

### FIXED CODE ###

N, A, B = [int(v) for v in input().strip().split(" ")]

loop, m = divmod(N, A + B)
print(loop * A + (m if m < A else A))
### BUGGY CODE ###

import sys
a=sys.stdin
while 1:
 if'0'==a.readline():break
 s=list(map(int,a.readline().split()))
 c=0
 while 1:
  t=s;s=[t.count(e)for e in t]
  if t==s:break
  c+=1
 print(c);print(*s)


### FIXED CODE ###

import sys
a=sys.stdin
while 1:
 if'0\n'==a.readline():break
 s=list(map(int,a.readline().split()))
 c=0
 while 1:
  t=s;s=[t.count(e)for e in t]
  if t==s:break
  c+=1
 print(c);print(*s)