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

import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
#COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l


q = deque([(1, 0)])
while(q):
    a, ca = q.popleft()
    bs = PT[a]

    c = list(range(1, cmax+1))
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        if COLOR[(na, nb)] == 0:
            clr = c.pop()
            if clr == ca:
                clr = c.pop()

            COLOR[(na, nb)] = clr
            q.append((b, clr))

print(cmax)

clr = []
for a, b in PATH:
    clr.append(COLOR[(a, b)])

print("\n".join(map(str, clr)))


### FIXED CODE ###

import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
#COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    '''
    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l
    '''

q = deque([(1, -1)])
while(q):
    a, ng = q.popleft()
    bs = PT[a]

    c = 1
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        cab = COLOR[(na, nb)]

        if cab == ng:
            continue

        if cab == 0:
            if c == ng:
                c += 1
            clr = c
            COLOR[(na, nb)] = clr
            q.append((b, clr))
            c += 1

print(max(COLOR.values()))

clr = []
for a, b in PATH:
    clr.append(COLOR[(a, b)])

print("\n".join(map(str, clr)))
### BUGGY CODE ###

import sys
 
a = []
for l in sys.stdin:
    if l == '\n' or l == '\r':
        break
    else :
        a.append(l)
 
target = a[int(a[0])]
num = 0

sortedA = []

for i in a:
    sortedA.append(''.join(sorted(i)))
sortedA.pop(0)

for i in range(0, len(a) - 1):
    for j in range(i + 1, len(a) - 1):
        flag = False
        if sortedA[i] == sortedA[j]:
            flag = True
            num = num + 1
print(num)

### FIXED CODE ###

import sys
import collections

n=int(input())
a=[''.join(sorted(input())) for _ in range(n)]

ans = 0
for v in collections.Counter(a).values():
    if v != 1:
        ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
for i in a:
    dp[i] = 0
for i in range(2, n+1):
    if i not in a:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
print(dp[n])

### FIXED CODE ###

import sys
n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
b = [0] * (m+1)
ans = 1
step = [0] * (n+1)
step[0] = 1
step[1] = 1
for i in range(2, n+1):
    step[i] = (step[i-1] + step[i-2]) % 1000000007
if m == 0:
    print(step[n])
    sys.exit()
for i in range(m-1):
    if a[i] + 1 == a[i+1]:
        print("0")
        quit()
if m > 0:
    b[0] = a[0] - 1
    b[m] = n - a[-1] - 1   
if m >= 2:
    for i in range(m-1, 0, -1):
        b[i] = a[i] - a[i-1] - 2
for i in b:
    ans = ans * step[i] % 1000000007
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(len(A)-1):
    ans += A[i]*sum(A[i+1:])
ans %= (10**9 + 7)
print(ans)

### FIXED CODE ###

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

sumA = sum(A)
ans = 0
for i in range(len(A)-1):
    sumA -= A[i]
    tmp1 = A[i] % (10**9 + 7)
    tmp2 = sumA % (10**9 + 7)
    ans += tmp1 * tmp2
    ans %= (10**9 + 7)
    
print(ans)
### BUGGY CODE ###

N = int(input())
#P = [int(i) for i in input().split()]
P = list(map(int, input().split()))
P_min = min(P)

count = 1
for i in range(N-1):
    if P[i+1] == P_min:
        count+=1
        break
    if min(P[:i+1]) > P[i+1]:
        count+=1

print(count)

### FIXED CODE ###

# https://atcoder.jp/contests/abc152/submissions/9600286
N = int(input())
P = list(map(int, input().split()))
c = 10**9
count = 0
for i in P:
    #リストの始めから探索
    #minを保持していく
    if i < c:
        c=i
        count+=1
print(count)
### BUGGY CODE ###

import numpy
k=int(input())
a=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      if i<=j<=l:
        if i==j==l:
          a=a+i
        elif i==j and j!=l:
          a=a+3*numpy.gcd.reduce([i,l])
        elif i!=j and j==l:
          a=a+3*numpy.gcd.reduce([i,j])
        elif i!=j and j!=l:
          a=a+6*numpy.gcd.reduce([i,j,l])
      else:
        a=a+0
print(a)

### FIXED CODE ###

import math
k=int(input())
a=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      if i<=j<=l:
        if i==j==l:
          a=a+i
        elif i==j and j!=l:
          a=a+3*math.gcd(i,l)
        elif i!=j and j==l:
          a=a+3*math.gcd(i,l)
        elif i!=j and j!=l:
          a=a+6*math.gcd(i,math.gcd(j,l))
      else:
        a=a+0
print(a)
### BUGGY CODE ###

n = int(input())
dam = list(map(int, input().split()))
mt = [0]*n
# a[i]]は山iと山i+1に降った平均
total = sum(dam)
for i in range(n):
    if i-2 < 0:
        mt[i] = total - 2*sum(dam[i+1::2])
    else:
        mt[i] = total - 2*(sum(dam[i-2::-2])+sum(dam[i+1::2]))

print(' '.join(map(str, mt)))


### FIXED CODE ###

n = int(input())
dam = list(map(int, input().split()))
mt = [0]*n
# a[i]]は山iと山i+1に降った平均
mt[0] = sum(dam) - 2*sum(dam[1::2])
mt[n-1] = dam[n-1]*2-mt[0]
for i in range(1, n-1):
    mt[i] = dam[i-1]*2-mt[i-1]
print(' '.join(map(str, mt)))
### BUGGY CODE ###

#134d
import math

#input
#3
#1 0 0
#output
#1
#1

N = int(input()) #1≤N≤2×10^5

#Nの後半は入力と一致するので直接代入   
ans = list(map(int, input().split()))

#N 個の空の箱が横一列に並んでいます。 左から i  (1≤i≤N) 番目の箱には整数 iが書かれています。
#それぞれの箱に対してボールを 1個入れるか何も入れないかを選ぶことができます。
#ここで、以下の条件を満たすようなボールの入れ方を、いいボールの入れ方と定めます。

# 1以上 N 以下の任意の整数 i について、i の倍数が書かれた箱に入っているボールの個数の和を 2 で割った余りが aiである。

#いいボールの入れ方は存在するでしょうか。存在するならば 1つ求めてください。

if N%2==0:
    first = int(N/2)-1
else:
    first = int((N-1)/2)-1

#前半部分を処理
for i in range(first,-1,-1): # Max:10^5ループ
    #print(i,"→",i+1,":",ans[i])
    
    multiple_list = [j for j in range(1,N+1) if j%(i+1)==0]
    #print("倍数:",multiple_list)
    #content = [ans[j-1] for j in multiple_list]
    #print("中身:",content)
    total = sum([ans[j-1] for j in multiple_list])
    
    if ans[i]==1 and total%2==0:
        ans[i] = 0
    elif ans[i]==0 and total%2==1:
        ans[i] = 1
        
#print(' '.join(map(str,ans)))
print(sum(ans))
print(' '.join(map(str,[j+1 for j in range(0,N) if ans[j]==1])))

### FIXED CODE ###

#134d
import math
 
#input
#3
#1 0 0
#output
#1
#1
 
N = int(input()) #1≤N≤2×10^5
 
#Nの後半は入力と一致するので直接代入   
ans = list(map(int, input().split()))
 
#N 個の空の箱が横一列に並んでいます。 左から i  (1≤i≤N) 番目の箱には整数 iが書かれています。
#それぞれの箱に対してボールを 1個入れるか何も入れないかを選ぶことができます。
#ここで、以下の条件を満たすようなボールの入れ方を、いいボールの入れ方と定めます。
 
# 1以上 N 以下の任意の整数 i について、i の倍数が書かれた箱に入っているボールの個数の和を 2 で割った余りが aiである。
 
#いいボールの入れ方は存在するでしょうか。存在するならば 1つ求めてください。
 
if N%2==0:
    first = int(N/2)-1
else:
    first = int((N-1)/2)-1

#前半部分を処理
for i in range(first,-1,-1): # Max:10^5ループ
    #print(i,"→",i+1,":",ans[i])
    
    multiple_list = [(i+1)*j for j in range(1,1+N//(i+1))]
    #print(N,",",N//(i+1))
    #print(i+1,"の倍数:",multiple_list)
    #content = [ans[j-1] for j in multiple_list]
    #print("中身:",content)
    total = sum([ans[j-1] for j in multiple_list])
    
    if ans[i]==1 and total%2==0:
        ans[i] = 0
    elif ans[i]==0 and total%2==1:
        ans[i] = 1
        
#print(' '.join(map(str,ans)))
print(sum(ans))
print(' '.join(map(str,[j+1 for j in range(0,N) if ans[j]==1])))
### BUGGY CODE ###

#---------------for input--------------------
numberN=int(input())
arrayS=list(map(int,input().split()))

numberQ=int(input())
arrayT=list(map(int,input().split()))
#---------------for input----------------------

def linearSearch(arrayS,arrayT,numberQ):
    machedNumber=0
    listForMached=[]
    index=0
    while index<numberQ:
        for s in arrayS:
            if arrayT[index] == s:
                if not s in listForMached:
                    listForMached.append(arrayT[index])
                    machedNumber+=1
            elif arrayT[index]<s:
                break
        index+=1
    print(machedNumber) 

#----------------for main------------------------
linearSearch(arrayS,arrayT,numberQ)
#----------------for main------------------------



### FIXED CODE ###

n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

count = 0
for elT in t:
    minI = 0
    maxI = len(s)-1
    while minI <= maxI:
        middle = (minI+maxI)//2
        if s[middle] == elT:
            count+=1
            break
        elif s[middle] < elT:
            minI = middle+1
        else:
            maxI = middle-1
print(count)
### BUGGY CODE ###

H, W, A, B = [int(i) for i in input().split(" ")]

from collections import deque

per = 10**9 + 7

goal_cnt = 0
que = deque([])
que.append((0, 0))

while que:
    p = que.popleft()
    if p[0] == H-1 and p[1] == W-1:
        goal_cnt += 1
        goal_cnt %= per
    else:
        for vh, vw in [[1, 0], [0, 1]]:
            pos_h = p[0] + vh
            pos_w = p[1] + vw
            
            if 0 <= pos_h <= H-1 and 0 <= pos_w <= W-1 and not(pos_w <= B-1 and pos_h >= H - A):
                que.append((pos_h, pos_w))
print(goal_cnt)

### FIXED CODE ###

U = 2*10**5
MOD = 10**9+7
 
fact = [1] * (U+1)
fact_inv = [1] * (U+1)

# 階乗のテーブル作成
for i in range(1, U+1):
    fact[i] = (fact[i-1] * i) % MOD

# 階乗の逆元のテーブル作成
fact_inv[U] = pow(fact[U], MOD-2, MOD)
for i in range(U, 0, -1):
    fact_inv[i-1] = (fact_inv[i] * i) % MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    x = fact[n]
    x *= fact_inv[k]
    x %= MOD
    x *= fact_inv[n-k]
    x %= MOD
    return x

H, W, A, B = [int(i) for i in input().split(" ")]

ans = 0
# 経路の足し上げ C(縦+横, 縦(or横)) (重複のある組み合わせ)
for i in range(B, W):
    ans += comb((H-A-1) + i, i) * comb((A - 1) + (W-1-i), W-1- i) % MOD
    ans %= MOD
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
  b.append(str(a[i]))
  b.reverse()
print(" ".join(b))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
left = []
right = []
for i in range(n):
  right.append(str(a[i]))
  left,right = right,left
left.reverse()
print(" ".join(left+right))
### BUGGY CODE ###

from sys import stdin, stdout
import numba as nb 

@nb.njit()
def solve(n,w,weights, values):
	dp = [[0 for _ in range(w+1)] for k in range(n+1)]
	for i in range(1,n+1):
		for j in range(1,w+1):
			if weights[i] <= j:
				dp[i][j] = max(dp[i-1][j],
			   	dp[i-1][j-weights[i]] + values[i])
			else:
				dp[i][j] = dp[i-1][j]
	return dp[n][w]

def main():
	n, w = map(int, stdin.readline().split())
	values = []
	weights = []

	for _ in range(n):
		v,a = map(int, stdin.readline().split())
		values.append(a)
		weights.append(v)

	values = [0] + values
	weights = [0] + weights
	print(solve(n,w,weights,values))

if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
 
import numba as nb
import numpy as np
 
input = sys.stdin.readline
 
 
@nb.njit("i8(i8,i8,i8[:],i8[:])")
def solve(N, W, w, v):
    dp = np.full(shape=(N + 1, np.sum(v) + 1), fill_value=(N * W), dtype=np.int64)
    dp[:, 0] = 0
    for i in range(N):
        np.minimum(w[i], dp[i][:v[i]], dp[i + 1][:v[i]])
        np.minimum(w[i] + dp[i][: - v[i]], dp[i][v[i]:], dp[i + 1][v[i]:])
    return np.where(dp[-1] <= W)[0][-1]
 
 
def main():
    N, W = map(int, input().split())
 
    w = np.empty(shape=N, dtype=np.int64)
    v = np.empty(shape=N, dtype=np.int64)
    for i in range(N):
        w[i], v[i] = map(int, input().split())
 
    ans = solve(N, W, w, v)
    print(ans)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# coding: utf-8

from functools import reduce
import copy
import fractions

N = int(input())
integers = list(map(int, input().split()))
integer_set = set(integers)


gcds = []

for i in range(N):
    tmp_integers = copy.copy(integers)
    for x in integer_set:
        tmp_integers[i] = x
        gcds.append(reduce(fractions.gcd, tmp_integers))
print(max(gcds))


### FIXED CODE ###

# coding: utf-8

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

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a%b)

L = [0]
R = [0]

for i in range(n):
    L.append(gcd(L[i], A[i]))
    R.append(gcd(R[i], A[n-1-i]))
R.reverse()

result = []

for i in range(n):
    result.append(gcd(L[i], R[i+1])) 

print(max(result))
### BUGGY CODE ###

n = int(input())
*A, = map(int, input().split())
p = 10**9+7
A = [list(format(a, '060b'))[::-1] for a in A]
A = [[int(a[i]) for a in A] for i in range(60)]
s = 0
for i in range(60):
    Ai = A[i]
    c0 = Ai.count(0)
    c1 = Ai.count(1)
    c = c0*c1
    s = (s+c*(2**i)) % p
print(s)


### 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 ###

H, W = [int(i) for i in input().split(" ")]
S = []
for i in range(H):
  S.append(input())

import numpy as np
mat = np.full([H,W,2], -1)
  
def calc_c(S,r,c):
  count = 0
  c1 = c
  while True:
    c1 -= 1
    if c1 >=0 and S[r][c1]==".":
      count += 1
    else: break
      
  c1 = c
  while True:
    c1 += 1
    if c1 <W and S[r][c1]==".":
      count += 1
    else: break
  
  c1 = c
  while True:
    c1 += 1
    if c1 <W and S[r][c1]==".":
      mat[r,c1,1] = count
    else: break
  return count

def calc_r(S,r,c):
  count = 0
  r1 = r
  while True:
    r1 -= 1
    if r1 >= 0 and S[r1][c]==".":
      count += 1
    else: break
      
  r1 = r
  while True:
    r1 += 1
    if r1 < H and S[r1][c]==".":
      count += 1
    else: break
   
  r1 = r
  while True:
    r1 += 1
    if r1 < H and S[r1][c]==".":
      mat[r1,c,0]=count
    else: break
  return count

ans = 0
  
for r in range(H):
  for c in range(W):
    target = S[r][c]
    if target == "#":
      continue
      
    rc, cc = mat[r,c]
    if rc == -1:
    	rc = calc_r(S,r,c)
    if cc == -1:
    	cc = calc_c(S,r,c)
        
    ans = max(rc+cc+1, ans) 

print(int(ans))

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = []
for h in range(H):
  S.append(list(map(lambda s:0 if s=='#' else 1, input())))
S = np.array(S)
 
l,r,u,d = [np.zeros([H,W], dtype=int) for _ in range(4)]

for w in range(W):
  l[:,w] = (l[:,w-1]+1)*S[:,w]
  r[:,-w-1] = (r[:,-w]+1)*S[:,-w-1]

for h in range(H):
  u[h] = (u[h-1]+1)*S[h]
  d[-h-1] = (d[-h]+1)*S[-h-1]
  
ans = np.max((l+r+u+d-3)*S)

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

#!/usr/bin/env python3
import heapq
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [-1, +1,  0,  0]
    DY = [0,  0, -1, +1]

    # ダイクストラ法を使います。
    dist = [[INF]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = [(0, (x1, y1))]
    while Q:
        curr, (x, y) = heapq.heappop(Q)
        for dx, dy in zip(DX, DY):
            for k in range(1, K+1):
                # ヒープキューで管理していることから考えると
                # 値が存在する場所と比較しても更新できることはない。
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if dist[X][Y] < curr+1:
                    break
                if c[X][Y] == "@":
                    break
                # これ実質的に距離はcurrだけでよいのだけど
                dist[X][Y] = curr+1
                heapq.heappush(Q, (curr+1, (X, Y)))
        if dist[x2][y2] < INF:
            print(dist[x2][y2])
            # print(*dist, sep="\n")
            return
    print(-1)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
INF = float("inf")


def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(lambda x: int(x)-1, input().split())
    c = []
    for i in range(H):
        c.append(input())
    # 移動方法が4*K個考えられる無向グラフ
    # 到達可能性は最短経路を求めるだけでよい
    # 全ての箇所を探索するとO(H*W)必要に見える。
    # あれ、HW<=10^6がある。難しさは何？Kが大きいから枝が多すぎるということか。
    DX = [1, 0, -1,  0]
    DY = [0, 1, 0, -1]

    # 方向付きで、ダイクストラ法を使います。
    dist = [[-1]*W for _ in range(H)]
    dist[x1][y1] = 0
    Q = []                      # ヒープなんてもう知らない！
    M = 10**6
    Q.append((0, x1, y1, 0b1111))
    i = 0

    while i < len(Q):
        curr, x, y, DXY = Q[i]
        for j in range(4):
            if (DXY >> j) & 1 == 0:
                continue
            dx, dy = DX[j], DY[j]
            for k in range(1, K+1):
                X = x+k*dx
                Y = y+k*dy
                if not (0 <= X < H):
                    break
                if not (0 <= Y < W):
                    break
                if 0 < dist[X][Y] < curr+1:
                    break
                if dist[X][y] == curr+1:
                    continue
                if c[X][Y] == "@":
                    break
                dist[X][Y] = curr+1
                flag = (1 << ((j+1) % 4)) | (1 << ((j-1) % 4))
                if k != K:
                    Q.append((curr+1, X, Y, flag))
                else:
                    flag |= 1 << j % 4
                    Q.append((curr+1, X, Y, flag))
            if 0 < dist[x2][y2]:
                print(dist[x2][y2])
                return
        i += 1
    print(-1)
    return


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

import sys
input = sys.stdin.readline

S=list(input()[:-1])
Q=int(input()[:-1])
f=0

for _ in range(Q):
    q=input().split()
    if int(q[0])==1:
        f = (f+1)%2
    if int(q[0])==2:
        if int(q[1])==1:
            if f==0:
                SS=[q[2]]
                SS.extend(S)
                S=SS
            else:
                S.append(q[2])
        else:
            if f==0:
                S.append(q[2])
            else:
                SS=[q[2]]
                SS.extend(S)
                S=SS
if f==0:
    print("".join(S))
else:
    print("".join(S[::-1]))


### FIXED CODE ###

import sys
input = sys.stdin.readline

S=list(input()[:-1])
Q=int(input()[:-1])
f=0
back=[]
forward=[]

for _ in range(Q):
    q=input().split()
    if int(q[0])==1:
        f = (f+1)%2
    if int(q[0])==2:
        if int(q[1])==1:
            if f==0:
                forward.append(q[2])
            else:
                back.append(q[2])
        else:
            if f==0:
                back.append(q[2])
            else:
                forward.append(q[2])

if f==0:
    print("".join(forward[::-1]+S+back))
else:
    print("".join((forward[::-1]+S+back)[::-1]))
### BUGGY CODE ###

n,q=map(int,input().split())
s=str(input())
t=s
l=[0]*q
r=[0]*q
for i in range(q):
        l[i],r[i]=map(int,input().split())
for j in range(q):
        s=t
        c=s[l[j]-1:r[j]].replace('A'+'C','__')
        print(c.count('__'))




### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q=map(int,input().split())
s=str(input())

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

import numpy as np
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
  H, W = map(int, input().split())
  G = [list(input()) for _ in range(H)]
  direction = [[0,1],[0,-1],[1,0],[-1,0]]
  black = np.zeros((H,W))
  que = []
  ans = 0
  for i in range(H):
    for j in range(W):
      if G[i][j] == '#':
        que.append([i,j])
        black[i][j] = 0
  while que:
    qq = []
    ans += 1
    for nh, nw in que:
      dh, dw = 0,1
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
      dh, dw = 0,-1
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
      dh, dw = 1,0
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
      dh, dw = -1,0
      if 0<=nh+dh<=H-1 and 0<=nw+dw<=W-1 and black[nh+dh][nw+dw] == 0:
        qq.append([nh+dh,nw+dw])
        black[nh+dh][nw+dw] = black[nh][nw]+1
    que = qq
  print(ans-1)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  G = [['#' == x for x in input()] for _ in range(H)]
 
  black = deque([(i, j) for i in range(H) for j in range(W) if G[i][j]])
 
  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not G[bi - 1][bj]:
        G[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not G[bi][bj - 1]:
        G[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not G[bi + 1][bj]:
        G[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not G[bi][bj + 1]:
        G[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def list_euclid(int_list):
    ans = int_list[0]
    for i in range(1,len(int_list)):
        ans = euclid(ans, int_list[i])
    return ans
n = int(input())
a = list(map(int, input().split()))
max = 0
if n < 5:
    for i in range(0,n):
        p = a.pop(0)
        x = list_euclid(a)
        if max < x:
            max = x
        a.append(p)
else:
    for i in range(0,n):
        p = a.pop(0)
        k = n // 2
        y = list_euclid(a[0:k])
        z = list_euclid(a[k:n-1])
        x = euclid(y, z)
        if max < x:
            max = x
        a.append(p)
print(max)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return int(a)
    
n = int(input())
a = list(map(int, input().split()))
if n==2:
  print(max(a))
  sys.exit(0)
elif n==3:
  lis = [gcd(a[0], a[1]), gcd(a[1], a[2]), gcd(a[2], a[0])]
  print(max(lis))
  sys.exit(0)
tmp_unused = gcd(a[0], a[1])
tmp_used = max(a[0], a[1])
#print("used=", tmp_used, "unused=", tmp_unused)
for i in range(2,n):
  #print(a[i])
  tmp_used = max(tmp_unused, gcd(tmp_used, a[i]))
  tmp_unused = gcd(tmp_unused, a[i])
  
  #print("used=", tmp_used, "unused=", tmp_unused)
print(tmp_used)
### BUGGY CODE ###

N = int(input())
A = input()
Q = int(input())
for _ in range(Q):
  B,C = input().split()
  A = A.replace(B,C)
  S = 0
  listA = list(A.split())
  for a in listA:
    S += int(a)
  print(S)


### FIXED CODE ###

from collections import Counter

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

counter = Counter(a)
sum_res = sum(a)  # はじめの合計、名前がsumだとsum関数とかぶってよくないので

# q回操作します。ループ変数は使わないので_とします（Pythonの慣習）
for _ in range(q):
    before, after = map(int, input().split())

    # 合計を変更します
    sum_res -= before * counter[before]
    sum_res += after * counter[before]

    # 個数を変更します
    counter[after] += counter[before]
    counter[before] = 0

    print(sum_res)