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

from pprint import pprint
h,w=map(int,input().split())
ch,cw=map(int,input().split())
ch-=1;cw-=1
dh,dw=map(int,input().split())
dh-=1;dw-=1
maze=[input() for _ in range(h)]

from collections import deque

dist=[[-1]*w for _ in range(h)]
q=deque()
p=[]
q.append((ch,cw))
dist[ch][cw]=0
cur=0 #ワープ回数
while q:
    # print("now cur:",cur)
    # print(q)
    while q:
        x,y=q.popleft()
        dist[x][y]=cur
        for i in range(-1,2):
            for j in range(-1,2):
                if abs(i)+abs(j)==1:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if dist[xx][yy]==-1:
                            if maze[xx][yy]==".":
                                dist[xx][yy]=cur
                                q.append((xx,yy))
                        if dist[xx][yy]>cur:
                            dist[xx][yy]=cur
                            q.append((xx,yy))
                                
        for i in range(-2,3):
            for j in range(-2,3):
                if abs(i)+abs(j)>=2:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if dist[xx][yy]==-1:
                            if maze[xx][yy]==".":
                                p.append((xx,yy))
    
    if len(q)==0:
        # print(p,q)
        for pp in p:
            if dist[pp[0]][pp[1]]==-1:
                q.append(pp)
        p=[]
        cur+=1
# pprint(dist)
print(dist[dh][dw])
  
    


### FIXED CODE ###

from pprint import pprint
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
ch-=1;cw-=1
dh,dw=map(int,input().split())
dh-=1;dw-=1
INF=float("inf")
maze=[input() for _ in range(h)]
dist=[[INF]*w for _ in range(h)]
q=deque()
p=[]
q.append((ch,cw))
dist[ch][cw]=0
cur=0
# pprint(dist)
# exit()
while q:
    while q:
        x,y=q.popleft()
        # (x,y)は到達訪問済み
        d=dist[x][y]
        for i in range(-2,3):
            for j in range(-2,3):
                # absの和が1、上下左右
                if abs(i)+abs(j)==1:
                    xx=x+i
                    yy=y+j
                    # 範囲内の時
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        # 道のとき
                        if maze[xx][yy]==".":
                            # 未到達の時
                            if dist[xx][yy]>d:
                                # 移動前のdist[x][y]と同じコスト
                                dist[xx][yy]=d
                                q.append((xx,yy))
                # ワープ 
                if abs(i)+abs(j)>=2:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if maze[xx][yy]==".":
                            if dist[xx][yy]>d+1:
                                dist[xx][yy]=d+1
                                p.append((xx,yy))
                                
   
    cur+=1
    q=deque(p)
    p=[]
            

# pprint(dist)
ans=dist[dh][dw]
if ans==INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N = int(input())
S = input()


def calculate(n, s):
    arr = list(s)
    result = []


    for i in range(n):
        left = arr[:i]
        right = arr[i + 1:]
        res = max(left.count('W'),right.count('R'))
        result.append(res)

    if len(result) == 0:
        print(-1)
    else:
        print(min(result))

calculate(N, S)


### FIXED CODE ###

# N = 8
# S = "WRWWRWRR"
#
# N = 2
# S = "RR"
#
# N = 3
# S = "WWW"

N = int(input())
S = input()

def calculate(n, s):
    arr = list(s)

    wNum = arr.count("W")
    RNum = arr.count("R")

    if wNum == 0 or RNum == 0:
        print(0)
        return

    leftW = 0
    rightR = RNum



    result = []
    for i in range(n):
        if arr[i] == "R":
            rightR -= 1
        if arr[i] == "W":
            leftW += 1

        result.append(max(leftW, rightR))

    print(min(result))


calculate(N, S)
### BUGGY CODE ###

n = int(input())
ListP = [int(val) for val in input().split()]

l = 0
r = 2
xlr = 0
tempMax = tempMax2 = max2 = 0
while (l < n - 1):
	tempMax2 = min(ListP[l : l + 2])
	xlr += tempMax2
	tempMax = max(ListP[l : l + 2])
	while (r < n):
		if (tempMax2 < ListP[r]):
			if (tempMax < ListP[r]):
				tempMax2 = tempMax
				tempMax = ListP[r]
			else:
				tempMax2 = ListP[r]
		if (tempMax2 == max2):
			xlr += (n - r) * max2
			break
		xlr += tempMax2
		r += 1
	if (l == 0):
		max2 = tempMax2
	l += 1
	r = l + 2
print(xlr)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
s = input()
passwords = defaultdict(int)
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            passwords[s[i] + s[j] + s[k]] += 1
        
print(len(passwords))

### FIXED CODE ###

N = int(input())
S = input()

ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    if S.find(num[0]) == -1:
        continue
    S1 = S[S.find(num[0]) + 1:]
    if S1.find(num[1]) == -1:
        continue
    S2 = S1[S1.find(num[1]) + 1:]
    if S2.find(num[2]) == -1:
        continue
    ans += 1

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

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=map(int,input().split())

l=sorted(l)

ans=1
for _ in range(n-1):
    for i in l[1:]:
        if i[1]<l[0][0]:
            l.remove(i)
    l.remove(l[0])
    if len(l)!=0:
        ans+=1
    else:
        break

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=map(int,input().split())

l=sorted(l)

ans=1

c=l[0][0]
for i in range(m):
    if l[i][1]>=c:
        ans+=1
        c=l[i][0]
    else:
        continue
print(ans)
### BUGGY CODE ###

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

for i in range(N):
    tmp = x.pop(i)
    tmplst = sorted(x)
    print(tmplst[(N - 1) // 2])
    x.insert(i, tmp)


### FIXED CODE ###

import statistics

N = int(input())
x = list(map(int, input().split()))
sx = sorted(x)
tmp = statistics.median(sx)

for i in range(N):
    if x[i] <= tmp:
        print(sx[((N - 1) // 2) + 1])
    else:
        print(sx[(N - 1) // 2])
### BUGGY CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1= []
dp2= [[-1 for i in range(w)] for j in range(h)]
dp3=[]
dp4=[]


for i in range(h):
    dp1.append([])
    dp3.append([])
    dp4.append([])
    for j in range(w):
        dp1[i].append(-1)
        dp3[i].append(-1)
        dp4[i].append(-1)

        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]



for i in range(w):
    for j in range(h):
        if s[j][i] == "#":
            dp3[j][i] = 0
        elif j == 0:
            dp3[j][i] = 1
        else:
            dp3[j][i] = 1 + dp3[j-1][i]

        if s[h-j-1][i] == "#":
            dp4[h-j-1][i] = 0
        elif h-j-1 == h-1:
            dp4[h-j-1][i] = 1
        else:
            dp4[h-j-1][i] = 1 + dp4[h-j][i]


a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)

### FIXED CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1= []
dp2= [[-1 for i in range(w)] for j in range(h)]
dp3=[]
dp4=[[-1 for i in range(w)] for j in range(h)]


for i in range(h):
    dp1.append([])
    dp3.append([])
    for j in range(w):
        dp1[i].append(-1)
        dp3[i].append(-1)

        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]

        if s[i][j] == "#":
            dp3[i][j] = 0
        elif i == 0:
            dp3[i][j] = 1
        else:
            dp3[i][j] = 1 + dp3[i-1][j]

        if s[h-i-1][j] == "#":
            dp4[h-i-1][j] = 0
        elif h-i-1 == h-1:
            dp4[h-i-1][j] = 1
        else:
            dp4[h-i-1][j] = 1 + dp4[h-i][j]



        

a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import bisect

N = int(input())
s = input().split() 
s = list(s[0])

dp = [[0]*(N+1) for _ in range(N+1)]
ans=0
for i in reversed(range(N)):
    for j in reversed(range(N)):
        if s[i]==s[j]:
            dp[i][j]=min(abs(j-i),dp[i+1][j+1]+1)
            ans = max(ans,dp[i][j])
#print(dp)
print(ans)
        


### FIXED CODE ###

import sys
input = sys.stdin.readline

import bisect

N = int(input())
s = input().split() 
s = list(s[0])

dp = [[0]*(N+1) for _ in range(N+1)]
ans=0
for i in reversed(range(N)):
    for j in reversed(range(N)):
        if s[i]==s[j]:
            dp[i][j]=min(abs(j-i),dp[i+1][j+1]+1)
            ans = max(ans,dp[i][j])
#print(dp)
print(ans)
### BUGGY CODE ###

import sys
import queue
input = sys.stdin.readline
N, Q = map(int, input().split())

tree = [[] for i in range(N+1)]
values = [0] * (N+1)
visit = [False]*(N+1)
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

for _ in range(Q):
    p, x = map(int, input().split())
    values[p] += x


q = queue.Queue()
q.put(1)
visit[1] = True
while (not q.empty()):
    now = q.get()
    for next in tree[now]:
        if not visit[next]:
            values[next] += values[now]
            visit[next] = True
            q.put(next)

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


### FIXED CODE ###

import sys
import queue
input = sys.stdin.readline
N, Q = map(int, input().split())

tree = [[] for i in range(N+1)]
values = [0] * (N+1)
visit = [False]*(N+1)
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

for _ in range(Q):
    p, x = map(int, input().split())
    values[p] += x


q = queue.Queue()
q.put(1)
visit[1] = True
while (not q.empty()):
    now = q.get()
    for next in tree[now]:
        if not visit[next]:
            values[next] += values[now]
            visit[next] = True
            q.put(next)

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

import sys
from heapq import heapify, heappush, heappop

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
heapify(A)

B=[ map(int, sys.stdin.readline().split()) for i in range(M) ]

for b,c in B:
	for i in range(b):
		if A[0]<c:
			heappop(A)
			heappush(A, c)
		else:
			break

print sum(A)


### FIXED CODE ###

import sys

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

B=[ map(int, sys.stdin.readline().split()) for _ in range(M)] 
B.sort(key=lambda x: x[1], reverse=True)

i=0

for b,c in B:
	for i in range(i,N):
		if A[i]<c and 0<b:
			A[i]=c
			b-=1
		if b==0:
			break
	i+=1

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

from collections import defaultdict, deque, Counter
MOD = 10 ** 9 + 7


# 素因数分解
def prime_factorize(n):
    a = defaultdict(int)
    while n % 2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] += 1
    return a

def main():
    n = int(input())
    A = list(map(int, input().split()))
    l = defaultdict(int)
    for a in A:
        c = prime_factorize(a)
        for k, v in c.items():
            l[k] = max(l[k], v)
    ans = 0
    lcm = 1
    for k, v, in l.items():
        lcm *= k ** v
    for a in A:
        ans += lcm // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
# INF = float("inf")


# 最大公約数
def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b


# 最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)


def main():
    n = int(input())
    A = list(map(int, input().split()))
    l = 1
    for a in A:
        l = lcm(l, a)
    c = 0
    for a in A:
        c += pow(a, MOD - 2, MOD)
    ans = l * c % MOD
    print(ans)


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

import sys
from itertools import groupby

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def len_count(S):
    H, W = len(S), len(S[0])
    L = [[0] * W for _ in range(H)]
    for row_S, row_L in zip(S, L):
        vec = [1]
        for i in range(1, W):
            if row_S[i - 1] == row_S[i]:
                vec[-1] += 1
            else:
                vec.append(1)

        idx = 0
        valid = row_S[0] == '.'
        for n in vec:
            if valid:
                for i in range(idx, idx + n):
                    row_L[i] = n
            idx += n
            valid = not valid

    return L


def main():
    H, W = map(int, readline().split())
    S = [readline().strip() for _ in range(H)]

    L1 = len_count(S)
    L2 = list(zip(*len_count(list(zip(*S)))))

    ans = 0
    for row1, row2 in zip(L1, L2):
        for j in range(W):
            if ans < row1[j] + row2[j] - 1:
                ans = row1[j] + row2[j] - 1

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import groupby

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def len_count(S):
    H, W = len(S), len(S[0])
    L = [[0] * W for _ in range(H)]
    for row_S, row_L in zip(S, L):
        vec = [1]
        for i in range(1, W):
            if row_S[i - 1] == row_S[i]:
                vec[-1] += 1
            else:
                vec.append(1)

        idx = 0
        valid = row_S[0] == '.'
        for n in vec:
            if valid:
                for i in range(idx, idx + n):
                    row_L[i] = n
            idx += n
            valid = not valid

    return L


def main():
    H, W = map(int, readline().split())
    S = [readline().strip() for _ in range(H)]

    L1 = len_count(S)
    L2 = len_count(list(zip(*S)))

    ans = 0
    for i in range(H):
        for j in range(W):
            if ans < L1[i][j] + L2[j][i] - 1:
                ans = L1[i][j] + L2[j][i] - 1

    print(ans)
    return


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

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

for i in range(m):
    a = sorted(a)[::-1]
    a[0] //= 2

print(sum(a))

### FIXED CODE ###

import heapq

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

for i in range(n):
    a[i] *= -1

heapq.heapify(a)

for i in range(m):
    ref = heapq.heappop(a)*-1
    ref //= 2
    heapq.heappush(a, -ref)

print(sum(a)*-1)
### BUGGY CODE ###

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
count = 0
for i in range(n):
    for si in s[i+1:]:
        if s[i] == si:
            count += 1 
print(count)

### FIXED CODE ###

n = int(input())
count = 0
ls = dict([])
for i in range(n):
    si = ''.join(sorted(input()))
    if si in ls.keys():
        count += ls[si]
        ls[si] += 1
    else:
        ls[si] = 1
print(count)
### BUGGY CODE ###

# import math
# import decimal
# import queue
# import bisect
# import heapq
# import time
# import itertools

mod = int(1e9+7)

def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    x = [0]
    _sum = 0
    for i in range(1,max(p)+1):
        _sum += i
        x.append(_sum)
    v = []
    for i in range(n):
        v.append(x[p[i]]/p[i])
    ans = 0
    for i in range(n-k+1):
        res = 0
        for j in range(k):
            res += v[i+j]
        ans = max(ans,res)
    print(ans)
    return

if __name__=='__main__':
    main()


### FIXED CODE ###

# import math
# import decimal
# import queue
# import bisect
# import heapq
# import time
# import itertools

mod = int(1e9+7)

def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    x = [0]
    _sum = 0
    for i in range(1,max(p)+1):
        _sum += i
        x.append(_sum)
    v = []
    ans = 0
    res = 0
    for i in range(n):
        v.append(x[p[i]]/p[i])
        if i >= k:
            res += v[i] - v[i-k]
        else:
            res += v[i]
        ans = max(ans,res)
    print(ans)
    return

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

#!/usr/bin/env python3
import sys
from collections import deque
def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)

    answer = -1
    for start_node in range(N):
        group = [0]*N
        queue = deque([(start_node,1)])

        while queue:
            node,count = queue.popleft()
            if not group[node]:
                group[node] = count

            for next_node in matrix[node]:
                if not group[next_node]:
                    queue.append((next_node,count+1))
            # print(group)

        # 条件を満たしているか判定
        # print(answer)
        for i in range(N): 
            for j in matrix[i]:
                if abs(group[i]-group[j]) == 1:
                    continue
                else:
                    break
            else:
                continue
            break
        else:
            answer = max(answer,max(group))
    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[int]"
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    d = [[10**5]*N for _ in range(N)]

    for i in range(N):
        d[i][i] = 0
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)
                d[i][j] = 1
                d[j][i] = 1
    
    # ２部グラフ 判定
    stack = [(0,1)]
    color = [-1]*N

    while stack:
        node,c = stack.pop()
        color[node] = c

        for next in matrix[node]:
            if color[next] == -1:
                stack.append((next,~c))
            else:
                if c^color[next] == 0:
                    print(-1)
                    return


    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    answer = 0
    for i in range(N):
        answer = max(answer,max(d[i]))
    print(answer+1)
    return

def main():
    N = int(input())
    S = [input() for _ in range(N)]
    solve(N, S)

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

q = int(input())
primes = [2]
for i in range(q):
    l, r = map(int,input().split())
    maxprime = primes[len(primes) - 1]
    if r > maxprime:
        for j in range(maxprime+1 if maxprime == 2 else maxprime+2, r+1, 2):
            #print(j)
            flag = True
            for prime in primes:
                if j % prime == 0:
                    flag = False
                    break
            if flag:
                primes.append(j)
    ans = 0
    for j in range(l, r+1):
        if j in primes and (j + 1) // 2 in primes:
            ans += 1
    print(ans)

### FIXED CODE ###

q = int(input())
primes = [True for _ in range(100000)]
c = [0 for _ in range(100000)]

for i in range(2, 100000):
    if primes[i]:
        for j in range(2*i, 100000, i):
            primes[j] = False

#print(primes[:20])

for i in range(3, 100000, 2):
    if primes[i] and primes[(i+1)//2]:
        c[i] += 1

for i in range(3, 100000):
    c[i] += c[i-1]
#print(c[:20])

for i in range(q):
    l, r = map(int,input().split())
    print(c[r] - c[l-1])
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
c = collections.Counter(A)
counter_key = list(c.keys())
counter_value = list(c.values())
list_sum_A=[]
sum_A=sum(A)
list_sum_A.append(sum_A)
B_list = []
C_list = []
for i in range(Q):
    B,C= map(int,input().split())
    B_list.append(B)
    C_list.append(C)

for i in range(1,Q+1):
    B = B_list[i-1]
    C = C_list[i-1]
    if(B not in counter_key):
        list_sum_A.append(list_sum_A[i-1])
    else:
        key_index=counter_key.index(B)
        list_sum_A.append(list_sum_A[i-1]+C*counter_value[key_index]-B*counter_value[key_index])
        if(C not in counter_key):
            counter_key[key_index]=C
        else:
            C_value_index = counter_key.index(C)
            counter_value[C_value_index]=counter_value[C_value_index]+counter_value[key_index]
            counter_value.pop(key_index)
            counter_key.pop(key_index)
for i in range(1,Q+1):
    print(list_sum_A[i])

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    s = [0 for i in range(10**5+1)]
    sa = sum(a)
    for i in a:
        s[i] += 1
    q = int(input())
    for _ in range(q):
        b, c = map(int, input().split())
        s[c] += s[b]
        sa += (c-b)*s[b]
        s[b] = 0
        print(sa)

main()