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

def comb(n, k, p):
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n - k) % p
    return (a * power_func(b, p - 2, p) * power_func(c, p - 2, p)) % p


def power_func(a, b, p):
    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, p)
        return d * d % p
    if b % 2 == 1:
        return (a * power_func(a, b - 1, p)) % p

X, Y = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7
if X > Y:
    X, Y = Y, X
##Yのほうが大きいとして考える
if not (X + Y) % 3 == 0 or Y > 2 * X:
    ans = 0
else:
    n = (X + Y) // 3
    d = Y - X
    a = 2*n - X
    ans = comb(n, a, mod)
print(ans)


### FIXED CODE ###

def comb(n, k, mod):
    if k > (n // 2):
        k = n - k
    a = 1
    for i in range(k):
        a *= (n - i)
        a %= mod
    for i in range(k - 1):
        a = (a * pow(k - i, mod - 2, mod)) % mod

    return a

X, Y = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7
if X > Y:
    X, Y = Y, X
##Yのほうが大きいとして考える
if not (X + Y) % 3 == 0 or Y > 2 * X:
    ans = 0
else:
    n = (X + Y) // 3
    d = Y - X
    a = 2*n - X
    ans = comb(n, a, mod)
print(ans)
### BUGGY CODE ###

N,M,V = list(map(int,input().split()))
A=list(map(int,input().split()))
B=list(map(int,input().split()))
S=list(map(int,A+B))
ans=0
time=0
if sum(S)<=V:
  print(N+M)
  exit()
K=sorted(S)
for i in range(N+M):
  if K[0]+time<=V:
    time+=K[0]
    K.pop(0)
    ans+=1
  else:
    print(ans)
    exit()

### FIXED CODE ###

a,b,money=list(map(int,input().split()))
A=[0]+list(map(int,input().split()))
B=[0]+list(map(int,input().split()))
for i in range(1,a+1):
  A[i]+=A[i-1]
for j in range(1,b+1):
  B[j]+=B[j-1]
ans=0
b_cnt=b
for a_cnt in range(a+1):
  if A[a_cnt]>money:
    continue
  while A[a_cnt]+B[b_cnt]>money:
    b_cnt-=1
  ans=max(ans,a_cnt+b_cnt)
print(ans)
### BUGGY CODE ###

import bisect as bs
N=int(input())
y=list(map(int, input().split()))
y.sort()
ans=0
for i in range(N-2):
  for j in range(i+1, N-1):
    tmp=y[i]+y[j]
    ans+=bs.bisect_left(y[(j+1):],tmp)
    
print(ans)



### FIXED CODE ###

import bisect as bs
N=int(input())
y=list(map(int, input().split()))
y.sort()
ans=0
for i in range(N-2):
  for j in range(i+1, N-1):
    tmp=y[i]+y[j]
    ans+=bs.bisect_left(y[(j+1):],tmp)
    
print(ans)
### BUGGY CODE ###

#C
import copy
n = int(input())
a = [int(input()) for _ in range(n)]
for i in range(n):
    tmp = copy.copy(a)
    tmp.pop(i)
    tmp.sort()
    print(tmp[-1])


### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
max_a = max(a)
max_idx = a.index(max_a)
for i in range(n):
    if i == max_idx:
        tmp = a
        tmp.sort(reverse=True)
        print(tmp[1])
    else:
        print(max_a)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc063/submissions/5323989 参照

def func(idx, points, N, lst_s, dp):
    # base case
    if idx == N:
        if points % 10 == 0:
            return 0
        else:
            return points
    
    # check memo
    if dp.get((idx, points)):
        return dp[(idx, points)]
    
    # recursive
    ret = max(
        func(idx = idx + 1, points = points, N = N, lst_s = lst_s, dp = dp), 
        func(idx = idx + 1, points = points + lst_s[idx], N = N, lst_s = lst_s, dp = dp)
        )
    dp[(idx, points)] = ret

    return ret


N = int(input())
lst_s = [int(input()) for _ in range(N)]
dp = {}
ans = func(0, 0, N, lst_s, dp)
print(ans)

### FIXED CODE ###

N = int(input())
lst_s = [int(input()) for _ in range(N)]
lst_s.sort()
max_grade = sum(lst_s)
ans = 0


if max_grade % 10 != 0:
    ans = max_grade
else:
    for s in lst_s:
        tmp_grade = max_grade - s
        if tmp_grade % 10 != 0:
            ans = max(ans, tmp_grade)

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

H, W = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if S[i][j] == ".":
			if j == 0:
				L[i][j] = 1
			else:
				L[i][j] = L[i][j - 1] + 1

# print(L)

for i in range(H):
	for j in range(W - 1, -1, -1):
		if S[i][j] == ".":
			if j == W - 1:
				R[i][j] = 1
			else:
				R[i][j] = R[i][j + 1] + 1

# print(R)

for j in range(W):
	for i in range(H - 1, -1, -1):
		if S[i][j] == ".":
			if i == H - 1:
				D[i][j] = 1
			else:
				D[i][j] = D[i + 1][j] + 1

# print(D)

for j in range(W):
	for i in range(H):
		if S[i][j] == ".":
			if i == 0:
				U[i][j] = 1
			else:
				U[i][j] = U[i - 1][j] + 1

# print(U)


ans = 0
X = [[0] * W for _ in range(H)]
for i in range(H):
	for j in range(W):
		X[i][j] = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
	ans = max(ans, max(X[i]))

# print(X)
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if S[i][j] == ".":
			if j == 0:
				L[i][j] = 1
			else:
				L[i][j] = L[i][j - 1] + 1

# print(L)

for i in range(H):
	for j in range(W - 1, -1, -1):
		if S[i][j] == ".":
			if j == W - 1:
				R[i][j] = 1
			else:
				R[i][j] = R[i][j + 1] + 1

# print(R)

for j in range(W):
	for i in range(H - 1, -1, -1):
		if S[i][j] == ".":
			if i == H - 1:
				D[i][j] = 1
			else:
				D[i][j] = D[i + 1][j] + 1

# print(D)

for j in range(W):
	for i in range(H):
		if S[i][j] == ".":
			if i == 0:
				U[i][j] = 1
			else:
				U[i][j] = U[i - 1][j] + 1

# print(U)


ans = 0
X = [[0] * W for _ in range(H)]
for i in range(H):
	for j in range(W):
		X[i][j] = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3
	ans = max(ans, max(X[i]))

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

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

bit = [0] * 61
for i in range(N):
    for x in range(61):
        if 2**x > A[i]:
            break
        elif 2**x & A[i] > 0:
            bit[x] += 1

ans = 0
for i in range(61):
    ans += 2**i * (bit[i] * (N-bit[i]))
    ans %= MOD

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

bit = [0] * 61
for i in range(N):
    for x in range(61):
        if 2**x > A[i]:
            break
        elif (1<<x) & A[i] > 0:
            bit[x] += 1

ans = 0
for i in range(61):
    ans += 2**i * (bit[i] * (N-bit[i]))
    ans %= MOD

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

N,Y = input().split()
N = int(N)
Y = int(Y)

for a in range(N+1):
  for b in range(N+1):
    X = 10000*a + 5000*b + 1000*(N-int(a)-int(b))
    #c = N-int(a)-int(b)
    if X==Y and N-int(a)-int(b)>=0:
      c = N-int(a)-int(b)
      print(a,b,c)
      exit()

print(-1,-1,-1)

### FIXED CODE ###

N, Y = map(int, input().split())
for x in range(N+1):
    for y in range(N-x+1):
        z = N-x-y
        if 0 <= z <= 2000 and 10000*x+5000*y+1000*z == Y:
            print(x, y, z)
            exit()
print(-1, -1, -1)
### BUGGY CODE ###

h, w, m = map(int, input().split())
a = [[0 for _ in range(w)] for _ in range(h)]
for i in range(m):
    hi, wi = map(lambda x:int(x) - 1, input().split())
    a[hi][wi] = 1

mh = [sum(a[i][:]) for i in range(h)]
mw = [sum([r[i] for r in a]) for i in range(w)]
s = [["B" for _ in range(w)] for _ in range(h)]

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == 0:
            v = mh[i] + mw[j]
            s[i][j] = v
        else:
            v = mh[i] + mw[j] - 1

        if v >= ans:
            ans = v
print(ans)

### FIXED CODE ###

h, w, m = map(int, input().split())
a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
mh = [0 for i in range(h)]
mw = [0 for j in range(w)]

for i, j in a:
    mh[i] += 1
    mw[j] += 1 

hmax = max(mh)
wmax = max(mw)
ans = hmax + wmax

flag = mh.count(hmax) * mw.count(wmax)
for i,j in a:
    if mh[i] == hmax and mw[j] == wmax:
        flag -= 1

if flag == 0:
    print(ans - 1)
else:
    print(ans)
### BUGGY CODE ###

from fractions import Fraction
from decimal import Decimal

n=int(input())
a=[Fraction(Decimal(input())) for _ in range(n)]

num=[aa.numerator*10**9//aa.denominator for aa in a]

cnt=[[0]*40 for _ in range(40)]
pair=[]

for nu in num:
    c2=0
    c5=0
    while nu>0 and nu%2==0:
        nu//=2
        c2+=1
    
    while nu>0 and nu%5==0:
        nu//=5
        c5+=1
    
    cnt[c2][c5]+=1
    pair.append((c2,c5))
ans=0

for c2,c5 in pair:
    for cc2 in range(18-c2,40):
        for cc5 in range(18-c5,40):
            ans+=cnt[cc2][cc5]
    if c2>=9 and c5>=9:
        ans-=1

print(ans//2)

### FIXED CODE ###

from fractions import Fraction
from decimal import Decimal

n=int(input())
a=[Fraction(Decimal(input())) for _ in range(n)]

num=[aa.numerator*10**9//aa.denominator for aa in a]

cnt=[[0]*50 for _ in range(50)]
pair=[]

for nu in num:
    c2=0
    c5=0
    while nu>0 and nu%2==0:
        nu//=2
        c2+=1
    
    while nu>0 and nu%5==0:
        nu//=5
        c5+=1
    
    cnt[c2][c5]+=1
    pair.append((c2,c5))
ans=0

for i in range(49,-1,-1):
    for j in range(49,-1,-1):
        if i+1<49:
            cnt[i][j]+=cnt[i+1][j]
        if j+1<49:
            cnt[i][j]+=cnt[i][j+1]

        if i+1<49 and j+1<49:
            cnt[i][j]-=cnt[i+1][j+1]

for c2,c5 in pair:
    ans+=cnt[max(0,18-c2)][max(0,18-c5)]
    if c2>=9 and c5>=9:
        ans-=1

print(ans//2)
### BUGGY CODE ###

from itertools import takewhile, islice


S = input()
total = 0
for idx in range(len(S) + 1):
    left = sum(1 for _ in takewhile(lambda x: x == "<", reversed(S[:idx])))
    right = sum(1 for _ in takewhile(lambda x: x == ">", islice(S, idx, None)))
    total += max((left, right))
print(total)


### FIXED CODE ###

S = input()
A = [0 for _ in range(len(S) + 1)]

for idx in range(len(S)):
    if S[idx] == "<":
        A[idx + 1] = max(A[idx + 1], A[idx] + 1)

for idx in reversed(range(len(S))):
    if S[idx] == ">":
        A[idx] = max(A[idx], A[idx + 1] + 1)

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

N, X, Y = list(map(int, input().split()))
for K in range(1,N):
    res = 0
    for i in range(N-1):
        for j in range(i+1,N):
            min_dist = min(abs(j-i), abs(X-1-i)+1+abs(Y-1-j), abs(Y-1-i)+1+abs(X-1-j))
            if min_dist == K:
                res += 1
    print(res)

### FIXED CODE ###

def min_dist(i, j, X, Y):
    return min(abs(j-i), abs(X-1-i)+1+abs(Y-1-j), abs(Y-1-i)+1+abs(X-1-j))

N, X, Y = list(map(int, input().split()))
dists = [min_dist(i, j, X, Y) for i in range(N-1) for j in range(i+1, N)]
dist_dic = { i: 0 for i in range(1,N)}
for dist in dists:
    dist_dic[dist] += 1
for K in range(1,N):
    print(dist_dic[K])
### BUGGY CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


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


def segfunc(x,y):
    return (x|y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,b):
    k += num-1
    if seg[k]=={b}:
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele =set()

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set() for i in range(2*num)]

for i in range(N):
    update(i,ord(S[i]))

for q in range(Q):
    type, i, c = input().split()
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]

def segfunc(x,y):
    return (x|y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1]|seg[2*i+2]

def update(k,b):
    k += num-1
    if seg[k]=={b}:
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = seg[k*2+1]|seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=set()
    while q-p>1:
        if p&1 == 0:
            res = res|seg[p]
        if q&1 == 1:
            res = res|seg[q]
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = res|seg[p]
    else:
        res = res|seg[p]|seg[q]
    return res

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set()] * (2*num)

for i in range(N):
    seg[i+num-1]={ord(S[i])}
for k in range(num-2,-1,-1):
    seg[k] = seg[k*2+1]|seg[k*2+2]
for type, i, c in Query:
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)
### BUGGY CODE ###

N, *A = map(int, open(0).read().split())
A = [0] + A + [0]
diff = [abs(A[i + 1] - A[i]) for i in range(N + 1)]
diff_i = [abs(A[i + 2] - A[i]) for i in range(N)]
for i in range(N):
  print(sum(diff) + diff_i[i] -  (diff[i] + diff[i + 1]))

### FIXED CODE ###

N, *A = map(int, open(0).read().split())
A = [0] + A + [0]
diff = [abs(A[i + 1] - A[i]) for i in range(N + 1)]
diff_i = [abs(A[i + 2] - A[i]) for i in range(N)]
a = sum(diff)
for i in range(N):
  print(a + diff_i[i] -  (diff[i] + diff[i + 1]))
### BUGGY CODE ###

S=input()
Q=int(input())
Que=[list(map(str, input().split())) for _ in range(Q)]
#print(Que)
for i in range(Q):
    if Que[i][0]=="1":
        S=S[::-1]
    elif Que[i][0]=="2":
        if Que[i][1]=="2":
            S=S+Que[i][2]
        elif Que[i][1]=="1":
            S=Que[i][2]+S
#    print(S)
print(S)


### FIXED CODE ###

from collections import deque
S=input()
s=deque(S)
Q=int(input())
Que=[list(map(str, input().split())) for _ in range(Q)]
#print(Que)
a=0
for i in range(Q):
    if Que[i][0]=="1":
        a+=1
    elif Que[i][0]=="2":
        if a%2==0:
            if Que[i][1]=="2":
                s.append(Que[i][2])
            elif Que[i][1]=="1":
                s.appendleft(Que[i][2])
        else:
            if Que[i][1]=="1":
                s.append(Que[i][2])
            elif Que[i][1]=="2":
                s.appendleft(Que[i][2])
s=list(s)
if a%2==1:
    s=s[::-1]
ans="".join(s)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
dig=[0 for i in range(40)] # 10^12 < 2^40

for i in range(n) :
    temp = a[i] 
    for j in range(40) :
        if temp <= 0 :
            break
        if temp % 2 == 1 :
            dig[j] += 1
        temp = temp // 2

bin = 1 << 39 # 2^39
sum0 = 0
i = 39
# leading_zero of k
while(bin > k) :
    sum0 += bin * dig[i]
    bin //= 2
    i += -1

memo={}

def solve (k, bin, i) :
    if i < 0 :
        return 0, 0
    if (k,bin) in memo:
        return memo[(k,bin)]
    if k >= bin :  # this digit can be 1 or 0
        sum1, ans1 = solve(k-bin, bin//2, i-1)
        sum1 += bin * (n- dig[i]) 
        sum0, ans0 = solve(k,bin//2, i-1)
        sum0 += bin * dig[i]
        if sum1 >= sum0 :
            sum = sum1
            ans = ans1 + bin
        else :
            sum = sum0
            ans = ans0
    else :         # this digit must be 0
        sum, ans = solve(k,bin//2, i-1)
        sum += bin * dig[i]
    memo[(k,bin)] = sum, ans
    return sum, ans

sum, ans = solve(k, bin, i)

print (sum+sum0)
#print(sum, sum0)
#print (ans)




### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
dig=[0 for i in range(40)] # 10^12 < 2^40

for i in range(n) :
    temp = a[i] 
    for j in range(40) :
        if temp <= 0 :
            break
        if temp % 2 == 1 :
            dig[j] += 1
        temp = temp // 2

bin = 1 << 39 # 2^39
sum0 = 0
i = 39
# leading_zero of k
while(bin > k) :
    sum0 += bin * dig[i]
    bin //= 2
    i += -1

memo={}

def solve (k, bin, i) :
    if i < 0 :
        return 0, 0
    if (k,bin) in memo:
        return memo[(k,bin)]
    if k >= bin :  # this digit can be 1 or 0
        sum1, ans1 = solve(k-bin, bin//2, i-1)
        sum1 += bin * (n- dig[i]) 
        sum0, ans0 = solve(bin-1,bin//2, i-1)
        sum0 += bin * dig[i]
        if sum1 >= sum0 :
            sum = sum1
            ans = ans1 + bin
        else :
            sum = sum0
            ans = ans0
    else :         # this digit must be 0
        sum, ans = solve(k,bin//2, i-1)
        sum += bin * dig[i]
    memo[(k,bin)] = sum, ans
    return sum, ans

sum, ans = solve(k, bin, i)

print (sum+sum0)
#print(sum, sum0)
#print (ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
kouji=[]
for i in range(0,N):
    s,t,x=map(int,input().split())
    kouji.append([x,s,t])

d=[]
for i in range(0,Q):
    d.append(int(input()))

kouji.sort(reverse=True)

# N: 処理する区間の長さ

N0 = 2**(Q-1).bit_length()
data = [None]*(2*N0)
INF = (-1,-1)
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]

time=0
for i in range(0,N):
    x,s,t=kouji[i]
    start=0
    end=Q-1
    while end-start>1:
        test=(end+start)//2
        if d[test]>=s-x:
            end=test
        else:
            start=test
    if d[start]>=s-x:
        l=start
    elif d[end]>=s-x:
        l=end
    else:
        l=Q

    start=0
    end=Q-1
    while end-start>1:
        test=(end+start)//2
        if t-x-1>=d[test]:
            start=test
        else:
            end=test
    if t-x-1>=d[end]:
        r=end
    elif t-x-1>=d[start]:
        r=start
    else:
        r=-1
    if r!=-1 and l!=Q and r>=l:
        update(l,r+1,(time,x))
    time+=1

for i in range(0,Q):
    print(query(i))

### FIXED CODE ###

import sys

input=sys.stdin.readline

N,Q=map(int,input().split())
kouji=[]
for i in range(0,N):
    s,t,x=map(int,input().split())
    kouji.append([x,s,t])

d=[]
for i in range(0,Q):
    d.append(int(input()))

kouji.sort(reverse=True)

# N: 処理する区間の長さ

N0 = 2**(Q-1).bit_length()
data = [None]*(2*N0)
INF = (-1,-1)
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]

time=0
for i in range(0,N):
    x,s,t=kouji[i]
    start=0
    end=Q-1
    while end-start>1:
        test=(end+start)//2
        if d[test]>=s-x:
            end=test
        else:
            start=test
    if d[start]>=s-x:
        l=start
    elif d[end]>=s-x:
        l=end
    else:
        l=Q

    start=0
    end=Q-1
    while end-start>1:
        test=(end+start)//2
        if t-x-1>=d[test]:
            start=test
        else:
            end=test
    if t-x-1>=d[end]:
        r=end
    elif t-x-1>=d[start]:
        r=start
    else:
        r=-1
    if r!=-1 and l!=Q and r>=l:
        update(l,r+1,(time,x))
    time+=1

for i in range(0,Q):
    print(query(i))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

N,K=map(int,input().split())
SIZE=5*10**5+1; MOD=10**9+7 #998244353 #ここを変更する
 
SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
  inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
  fac[i] = fac[i-1]*i%MOD
  finv[i]= finv[i-1]*inv[i]%MOD

def narabekae(n,r): #nPr mod MOD の計算
  if n-r<0:
    return 0
  return fac[n]*finv[n-r]%MOD

branch=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  branch[a-1].append(b-1)
  branch[b-1].append(a-1)

ans=1

def draw(parent,nord):
  global ans
  children=len(branch[nord])-(parent !=-1)
  if children==0:
    return
  #(K-2)*(K-1)*... をchildrenの数だけ掛ける。
  ans=ans*narabekae(K-1-(parent !=-1),children)%MOD
  for b in branch[nord]:
    if b != parent:
      draw(nord,b)

draw(-1,0)
print(ans*K%MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N,K=map(int,input().split())
MOD=10**9+7
branch=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  branch[a-1].append(b-1)
  branch[b-1].append(a-1)

if K==1:
  if N==1:
    print(1)
  else:
    print(0)
  exit()
  
P=[0]*(K-1)
P[K-2]=K-2
for i in range(K-3,0,-1):
  P[i]=P[i+1]*i%MOD
  
def PPP(start,num):
  if start<num:
    return 0
  if start==K-2:
    return P[start-num+1]
  if start==K-1:
    return P[start-num+2]*(K-1)%MOD
  
ans=1

def draw(parent,nord):
  global ans
  children=len(branch[nord])-(parent !=-1)
  if children==0:
    return
  #(K-2)*(K-1)*... をchildrenの数だけ掛ける。
  ans=ans*PPP(K-1-(parent !=-1),children)%MOD
  for b in branch[nord]:
    if b != parent:
      draw(nord,b)

for i in range(len(branch[0])+1):
  ans=ans*(K-i)%MOD
for bra in branch[0]:
  draw(0,bra)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
counter = 1
while counter <= n:
    for see in a:
        if see == counter:
            ans.append(a.index(see) + 1)
            counter += 1
            break
[print(x, end=' ')for x in ans]


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
L = {}
for i in range(len(a)):
    L[i] = a[i]
sort_L = sorted(L.items(), key=lambda x: x[1])
[print(j[0]+1, end=' ')for j in sort_L]
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for i in range(Q)]
# print(N)
# print(A)
# print(Q)
# print(B)

total = sum(A)

for i in range(Q):
    Bi = BC[i][0]
    Ci = BC[i][1]

    diff = 0
    for j in range(len(A)):
        if A[j] == Bi:
            diff += Ci - A[j]
            A[j] = Ci

    total += diff
    print(total)


### FIXED CODE ###

import itertools

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for i in range(Q)]
# print(N)
# print(A)
# print(Q)
# print(B)

distribution = {}
max_A = max(A)
max_BC = max(list(itertools.chain.from_iterable(BC)))
maximum = max([max_A, max_BC])
# print(max_A, max_BC, maximum)
for i in range(maximum + 1):
    distribution[i] = 0

for Ai in A:
    distribution[Ai] += 1
# print(distribution)

total = sum(A)
for i in range(Q):
    Bi = BC[i][0]
    Ci = BC[i][1]
    num_Bi = distribution.get(Bi)
    diff = (Ci - Bi) * num_Bi

    distribution[Bi] = 0
    # print(num_Bi, distribution.get(Bi), Ci)
    distribution[Ci] += num_Bi

    total += diff
    print(total)