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

import sys
sys.setrecursionlimit(3 * 10 ** 5)

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

v = [[] for i in range(N)]  #もともとの木構造
for i in range(N-1):
  a, b = map(int, input().split())
  #vのindexが頂点番号、各indexの要素が繋がっている要素を表す
  v[a-1].append(b-1) #頂点idが1から始まっているため0にずらす
  v[b-1].append(a-1)

f = [0] * N #足し算するもの
for i in range(Q):
  p, x = map(int, input().split())
  f[p-1] += x  #それぞれの頂点に足すべき項目をあらかじめ追加して整理

#print(v)
#print(f)

#再帰関数dfsの定義:終了条件はd[y]==0となったら
def dfs(x, d, s): # x:計算する頂点, d:計算了否配列(まだ1完了0), s:頂点xの値
  for y in v[x]:  #頂点xとつながる各頂点yの計算
    if d[y]:      #計算される頂点yが計算未了の場合
      s += f[y]   #頂点xの値sにf[y](頂点yの値)を足す
      ans[y] = s  #頂点yの値をsに確定
      d[y] = 0    #計算済に変更
      dfs(y,d,s)  #頂点yの下層についても再帰的に計算
      s -= f[y]   #頂点yの下層の計算が終わったのでsを頂点xの値に戻す

ans = [0] * N
d = [1] * N #全部未計算にセット
d[0] = 0 #0が"根" 0は計算済(※f[0]が答えだから)
ans[0] = f[0]
s = f[0]
dfs(0,d,s)
print(*ans) #*と配列でスペース区切りで表示

### FIXED CODE ###

import sys
input = sys.stdin.readline   #sys.std.readlineのほうが10倍速い
N, Q = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N-1)]
PX = [tuple(map(int, input().split())) for i in range(Q)]
es = [[] for _ in range(N)]  #グラフ配列

for a,b in AB:
  a -= 1
  b -= 1
  es[a].append(b)
  es[b].append(a)
ps = [0] * N   #処理配列(当該のものをプラスする)
for p,x in PX:
  ps[p-1] += x
  
#print(es)
#print(ps)

ans = [0] * N #回答配列
ans[0] = ps[0]
stack = [0]  #待ち配列
visited = [0] * N #訪れたかどうか配列、最初は0、訪れたら1
visited[0] = 1
while stack: #空であればFalse、中身が入ってればTrueを返す性質
  v = stack.pop()
  for i in es[v]:
    if visited[i]:
      continue
    visited[i] = 1
    ans[i] = ans[v] + ps[i]
    stack.append(i)
print(*ans)
### BUGGY CODE ###

from collections import deque

H, W = list(map(int, input().split()))
field = [input() for _ in range(H)]
dist = [[5000] * W for _ in range(H)]

def bfs():
  q = deque()
  for y in range(H):
    for x in range(W):
      if field[y][x] == '#':
        q.append((y, x))
        dist[y][x] = 0
  while len(q) > 0:
    y, x = q.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
      ny, nx = y + dy, x + dx
      if ny < 0 or ny >= H or nx < 0 or nx >= W:
        continue
      if field[ny][nx] == '#':
        continue
      if dist[ny][nx] < dist[y][x] + 1:
        continue
      dist[ny][nx] = dist[y][x] + 1
      q.append((ny, nx))
      
bfs()
print(max([max(d) for d in dist]))

### FIXED CODE ###

from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append((x-1,y))
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append((x,y-1))
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append((x+1,y))
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append((x,y+1))
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

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

n = int(input())
path = [[0 for i in range(n)] for j in range(n)]

for i in range(n-1):
    a, b, c = map(int, input().split())
    path[min(a-1, b-1)][max(a-1, b-1)] = c


q, k = map(int, input().split())
distance = [None] * n
distance[k-1] = 0
queue = [k-1]
while(len(queue)):
    p = queue.pop()
    for i in range(n):
        if(path[min(i,p)][max(i,p)]!=0 and distance[i] == None):
            distance[i] = distance[p] + path[min(i,p)][max(i,p)]
            queue.append(i)

for i in range(q):
    x, y = map(int, input().split())
    print(distance[x-1]+distance[y-1])


### FIXED CODE ###

n = int(input())
path = [[] for i in range(n)]

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


q, k = map(int, input().split())
distance = [None] * n
distance[k-1] = 0
queue = [k-1]
while(len(queue)):
    p = queue.pop()
    for i,c in path[p]:
        if(distance[i] == None):
            distance[i] = distance[p] + c
            queue.append(i)

for i in range(q):
    x, y = map(int, input().split())
    print(distance[x-1]+distance[y-1])
### BUGGY CODE ###

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

for i in range(k):
    if a >= 1:
        a -= 1
    elif b >= 1:
        b -= 1

print(a,b)


### FIXED CODE ###

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

if k < a:
    print(a-k,b)
else:
    if a+b > k:
        print(0,a+b-k)
    else:
        print(0,0)
### BUGGY CODE ###

import bisect

N = int(input())
L = [int(_) for _ in input().split()]
L.sort()

ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        r = L[i] + L[j]
        # 同じ長さでも違う棒はOK
        ri = bisect.bisect_left(L, r, lo=j + 1)
        ans += ri - j - 1
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
L = [int(_) for _ in input().split()]
L.sort()

ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        r = L[i] + L[j]
        # 同じ長さでも違う棒はOK
        ri = bisect.bisect_left(L, r, lo=j)
        ans += ri - j - 1

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

N = int(input())
A = list(map(int, input().split()))
S = sorted(set(A), reverse=True)
w, h = 0, 0

cnt = 0
for s in S:
  if A.count(s) > 1:
    if cnt == 0:
      if A.count(s) > 3:
        w, h = s, s
        cnt += 2
        break
      else:
        w = s
        cnt += 1
    else:
      h = s
      cnt += 1
      break
ans = w * h
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
S = sorted(A, reverse=True)
w, h = 0, 0

cnt = 0
tmp = S[0]
for i in range(N):
  if S[i] == tmp:
    cnt += 1
    if cnt == 2:
      if w == 0:
        w = tmp
        cnt = 0
      else:
        h = tmp
        break
  else:
    cnt = 1
    tmp = S[i]
        
ans = w * h
print(ans)
### BUGGY CODE ###

from sys import stdin
# stdin = open('b_1.txt')

input = stdin.readline

MOD = 998244353
def main():
    A, B, C, D = map(int, input().rstrip().split())
    DP = [[0 for _ in range(D + 1)] for _ in range(C + 1)]
    for i in range(A, C + 1):
        for j in range(B, D + 1):
            if i == A and j == B:
                DP[i][j] = 1
                continue
            DP[i][j] = ((DP[i -1][j] * j) + (DP[i][j -1] * i) - (DP[i -1][j - 1] * (i - 1) * (j  - 1))) % MOD
    print(DP[C][D] % MOD)

if __name__ == "__main__":
    main()



### FIXED CODE ###

from sys import stdin
# stdin = open('b_1.txt')

input = stdin.readline

MOD = 998244353
def main():
    A, B, C, D = map(int, input().rstrip().split())
    DP = [[0 for _ in range(D + 1)] for _ in range(C + 1)]
    for i in range(A, C + 1):
        for j in range(B, D + 1):
            if i == A and j == B:
                DP[i][j] = 1
                continue
            DP[i][j] = ((DP[i -1][j] * j) + (DP[i][j -1] * i) - (DP[i -1][j - 1] * (i - 1) * (j  - 1))) % MOD
    print(DP[C][D] % MOD)

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

N,X,Y=map(int,input().split())
ans=[0]*(N-1)
for i in range(N-1):
  for j in range(i+1,N):
      ans[min(abs(j-i), abs(X-i-1) + 1 + abs(j+1-Y ), abs(Y-i-1) + 1 + abs(j+1-X))-1]+=1
for i in range(N-1):
    print(ans[i])

### FIXED CODE ###

N,X,Y=map(int,input().split())
ans=[0]*(N-1)
for i in range(1,N):
  for j in range(i+1,N+1):
      ans[min(abs(j-i), abs(X-i) + 1 + abs(j-Y ), abs(Y-i) + 1 + abs(j-X))-1]+=1
for i in range(N-1):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
list_score = list(map(int, input().split()))
list_value = [-1 for _ in range(n)]
ans = 0

for i in range(1, n+1):
    a = list_score.index(i)
    b = list_value[0:a+1]
    #print(a)
    #print(b)
    #print(sum(b), -(a+1))
    if sum(b) == -(a+1):
        ans += 1
    list_value[a] = 1

print(ans)

### FIXED CODE ###

n = int(input())
list_score = list(map(int, input().split()))
min_value = list_score[0]
ans = 0

for i in range(0, n):
    min_value = min(min_value, list_score[i])
    if list_score[i] == min_value:
        ans += 1
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
def bfs():
    while len(q) > 0:
        now,cnt = q.popleft()
        step = cnt % 3
        vis[now][step] = cnt
        if now == T and step  == 0:  
            return cnt
        for x in path[now]:
            if vis[x][(step+1)%3] == -1:
                q.append((x,cnt+1))
    return -3
vis[S][0] = 1
q.append([S,0])
print(bfs()//3)





### FIXED CODE ###

N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            vis[x][(step+1)%3] = cnt
            q.append((x,cnt+1))

if vis[T][0] == -1:
    print(-1)
else:
    print(vis[T][0]//3+1)
### BUGGY CODE ###

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

mod = 10**9+7

ans = 0
for i in range(N):
    for j in range(i+1, N):
        ans = (ans % mod + A[i]*A[j] % mod) % mod
print(ans)

### FIXED CODE ###

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

mod = 10**9+7

tmp = 0
for i in range(N):
    tmp += A[i]
    tmp = tmp % mod
all = (tmp % mod)**2
all = all % mod

tmp = 0
for i in range(N):
    tmp += (A[i]* A[i]) % mod
di = tmp % mod

ans = all - di
ans *= (mod + 1) // 2
ans %= mod

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

n = int(input())

A = []

for i in range(n):
    a = int(input())
    A.append(a)

for i in A:
    copy = A[:]
    copy.remove(i)
    print(max(copy))

### FIXED CODE ###

n = int(input())

A = []

for i in range(n):
    a = int(input())
    A.append(a)

maxa = max(A)

copy = A[:]

copy.remove(maxa)

maxa2 = max(copy)

for i in A:
    if i == maxa:
        print(maxa2)
    else:
        print(maxa)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H, W, N = map(int, input().split())
ab = set(tuple(map(int, input().split())) for i in range(N))

dxy = {0:[0, 1, 2], 1:[-1, 0, 1], 2:[-2, -1, 0]}
num_all = (H - 2) * (W - 2)
num = [0] * 10
for a, b in ab:
  for i in range(3):
    Da = dxy[i]
    for j in range(3):
      n = 0
      flag = False
      Db = dxy[j]
      for da in Da:
        aa = a + da
        for db in Db:
          bb = b + db
          if aa < 1 or H < aa or bb < 1 or W < bb:
            flag = True
            break
          if (aa, bb) in ab:
            n += 1
        if flag:
          break
      if flag:
        continue
      num[n] += 1

for i in range(2, 10):
  num[i] //= i

num[0] = num_all - sum(num[1:])
print(*num, sep='\n')

### FIXED CODE ###

H, W, N = map(int, input().split())
ab = set(tuple(map(int, input().split())) for i in range(N))

dxy = {0:[0, 1, 2], 1:[-1, 0, 1], 2:[-2, -1, 0]}
num_all = (H - 2) * (W - 2)
num = [0] * 10
for a, b in ab:
  for i in range(3):
    Da = dxy[i]
    for j in range(3):
      n = 0
      flag = False
      Db = dxy[j]
      for da in Da:
        aa = a + da
        for db in Db:
          bb = b + db
          if aa < 1 or H < aa or bb < 1 or W < bb:
            flag = True
            break
          if (aa, bb) in ab:
            n += 1
        if flag:
          break
      if flag:
        continue
      num[n] += 1

for i in range(2, 10):
  num[i] //= i

num[0] = num_all - sum(num[1:])
print(*num, sep='\n')
### BUGGY CODE ###

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
S = [input() for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append((Ch, Cw))

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append((nh, nw))
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw] + 1:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.append((nh, nw))

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])

### FIXED CODE ###

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
S = [input() for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw] + 1:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.appendleft([nh, nw])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])
### BUGGY CODE ###

N,Q=list(map(int,input().split(" ")))
s=input()
for z in range(0,Q):
  i=list(map(int,input().split(" ")))
  buf=s[i[0]-1:i[1]]
  print(buf.count("AC"))

### FIXED CODE ###

N,Q=list(map(int,input().split(" ")))
s=input()

arr=[0]*N
for i,z in enumerate(arr):
  if i==0:
    continue
  if s[i-1]=="A" and s[i]=="C":
    arr[i]=arr[i-1]+1
  else:
    arr[i]=arr[i-1]
for z in range(0,Q):
  i=list(map(int,input().split(" ")))
  print(arr[i[1]-1]-arr[i[0]-1])
### BUGGY CODE ###

import itertools

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

n_li = list(range(n+1))

ans = 0

for i in range(k, n+2):
  ans += len(set(list(map(sum, list(itertools.combinations(n_li,i))))))

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    MOD = 1000000007
    n, k = map(int, input().split())

    n_li = list(range(n+1))

    ans = 0

    while(k <= n+1):
        p = (k - 1) * k / 2
        q = ((n + n - k + 1) * k) / 2

        ans += q - p + 1
        ans %= MOD
        k += 1

    print(int(ans))

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

"""
"""
A, B, C, K = map(int, input().split())
sum = 0
for i in range(K):
    if A >= 1:
        sum += 1
        A -= 1
    elif B >= 1:
        B -= 1
    else:
        sum -= 1

print(sum)


### FIXED CODE ###

"""
"""
A, B, C, K = map(int, input().split())
sum = 0

if A >= 1:
    if K - A >= 0:
        sum += A
        K -= A
    else:
        sum += K
        K = 0
if B >= 1 and K >= 1:
    if K - B >= 0:
        K -= B
    else:
        K = 0

if C >= 1 and K >= 1:
    if K - C >= 0:
        sum -= C
        K -= C
    else:
        sum -= K
        K = 0

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

import bisect
import sys
input = sys.stdin.readline


def initialize(a, value=float('inf')):
    n = len(a)
    N = 1 << (n-1).bit_length()
    seg_data = [value]*(N-1) + a + [value]*(N-n)
    lazy = [None] * (2*N - 1)
    for i in range(2*N-2, 0, -2):
        seg_data[(i-1)>>1] = min(seg_data[i], seg_data[i-1])
    return seg_data, lazy, N

def indices_generator(i, j, N):
    # [i, j)
    # [idx1, idx2)を部分的に含むインデックスを降順にyieldするジェネレータ
    idx1 = N + i
    idx2 = N + j
    lm = (idx1 // (idx1 & -idx1)) >> 1
    rm = (idx2 // (idx2 & -idx2)) >> 1
    while idx1 < idx2:
        if idx2 <= rm:
            yield idx2-1
        if idx1 <= lm:
            yield max(0, idx1-1)
        idx1 >>= 1
        idx2 >>= 1
    while idx1:
        yield idx1-1
        idx1 >>= 1
    
def propagate(indices):
    # 遅延させていた値を伝搬させる
    # indicesは昇順
    for idx in indices:
        v = lazy[idx]
        if v is None:
            continue
        _idx = 2*idx + 1
        lazy[_idx] = lazy[_idx+1] = v
        seg_data[_idx] = seg_data[_idx+1] = v
        lazy[idx] = None
        
def update(i, j, x, N):
    # [i, j)の区間の値をxに変更する
    *should_prop, = indices_generator(i, j, N)
    propagate(should_prop[::-1])
    idx1 = N - 1 + i
    idx2 = N - 2 + j
    while idx1 < idx2 + 1:
        if idx1&1 == 0: # idx1が偶数
            lazy[idx1] = seg_data[idx1] = x
        if idx2&1 == 1: # idx2が奇数
            lazy[idx2] = seg_data[idx2] = x
        idx1 >>= 1
        idx2 >>= 1
        idx2 -= 1        
    for idx in should_prop:
        _idx = 2*idx + 1
        seg_data[idx] = min(seg_data[_idx], seg_data[_idx+1])
    

INF = float('inf')
N, Q = map(int, input().split())
STX = [list(map(int, input().split())) for i in range(N)]
STX.sort(key=lambda x:x[2], reverse=True)
seg_data, lazy, N0 = initialize([INF]*Q)
d = [int(input()) for i in range(Q)]

for s, t, x in STX:
  il = bisect.bisect_left(d, s-x)
  ir = bisect.bisect_right(d, t-x-1)
  if il == ir:
    continue
  update(il, ir, x, N0)

propagate([i for i in range(N0-1)])
ans = [x if x<INF else -1 for x in seg_data[N0-1:N0-1+Q]]
print(*ans, sep='\n')

### FIXED CODE ###

import sys
from heapq import heappop, heappush

input = sys.stdin.readline
N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

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

ans = []
event_list.sort()
x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heappop(x_list)
    if x_list:
      ans.append(x_list[0])
    else:
      ans.append(-1)

print(*ans, sep='\n')
### BUGGY CODE ###

A,B = map(int, input().split())
def cf(A,B):
    Af = []
    Bf = []
    for i in range(1,round(A**0.5)+1):
        if A % i == 0:
            Af.append(i)
            Af.append(A//i)
    for i in range(1,round(B**0.5)+1):
        if B % i == 0:
            Bf.append(i)
            Bf.append(B//i)
    cf = list(set(Af).intersection(Bf))
    return cf
L = cf(A,B)
ans = 0
def is_prime(n):
    cd = []
    for i in range(1,round(n**0.5)+1):
        if n % i == 0:
            cd.append(i)
    if cd == [1]:
        return True
    else:
        return False
for i in L:
    if is_prime(i):
        ans += 1
print(ans)

### FIXED CODE ###

A,B = map(int, input().split())
def cf(A,B):
    Af = []
    Bf = []
    for i in range(1,round(A**0.5)+1):
        if A % i == 0:
            Af.append(i)
            Af.append(A//i)
    for i in range(1,round(B**0.5)+1):
        if B % i == 0:
            Bf.append(i)
            Bf.append(B//i)
    cf = list(set(Af).intersection(Bf))
    return cf
L = cf(A,B)
ans = 0
def is_prime(n):
    cd = []
    for i in range(1,round(n**0.5)+1):
        if n % i == 0:
            cd.append(i)
    if cd == [1]:
        return True
    else:
        return False
for i in L:
    if is_prime(i):
        ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
bucket = [0]*100001

for i in range(100000):
    bucket[i] = A.count(i)

sum = sum(A)

for i in range(Q):
    b, c = list(map(int, input().split()))
    sum += (c - b) * bucket[b]
    bucket[c] += bucket[b]
    bucket[b] = 0
    print(sum)

### FIXED CODE ###

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

B, C = [0]*Q, [0]*Q
for i in range(Q):
    B[i], C[i] = list(map(int, input().split()))

bucket = [0]*100001
for i in A:
    bucket[i] += 1

sum = sum(A)

for i in range(Q):
    sum += (C[i] - B[i]) * bucket[B[i]]
    bucket[C[i]] += bucket[B[i]]
    bucket[B[i]] = 0
    print(sum)
### BUGGY CODE ###

n = int(input())
s = input()
def multi_index(l,x):
  return [i for i,_x in enumerate(l) if _x == x]

ans = 0
for i in range(10):
  e = 0
  if str(i) in s:
    c = multi_index(s,str(i))[0]
    for j in range(10):
      if str(j) in s and i!=j and c<=len(s)-2:
        chk = s[c+1:]
        #print(chk)
        if str(j) in chk:
          d = multi_index(chk,str(j))[0]+c+1
        else:
          d = -1
      elif str(j) in s and i==j and len(multi_index(s,str(i)))>=2:
        d = multi_index(s,str(i))[1]
      else:
        d = -1
      if d > c:
        for l in range(10):
          if str(l) in s and i!=j and j!=l and i!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
              #print(i,j,l)
          if str(l) in s and i!=j and j==l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
              #print(i,j,l)
          if str(l) in s and i==j and j!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
              #print(i,j,l)
          if str(l) in s and i==j and j==l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
              #print(i,j,l)
          if str(l) in s and i==l and j!=l:
            e = multi_index(s,str(l))[-1]
            #print(i,j,l,c,d,e)
            if e > d:
              ans += 1
              #print(i,j,l)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
def multi_index(l,x):
  return tuple([i for i,_x in enumerate(l) if _x == x])

ans = 0
for i in range(10):
  e = 0
  if str(i) in s:
    c = multi_index(s,str(i))[0]
    for j in range(10):
      if str(j) in s and i!=j and c<=len(s)-2:
        for q in range(c+1,len(s)-1):
          if str(j) == s[q]:
            d = q
            break
        else:
          d = -1
      elif str(j) in s and i==j and len(multi_index(s,str(i)))>=2:
        d = multi_index(s,str(i))[1]
      else:
        d = -1
      if d > c:
        for l in range(10):
          if str(l) in s and i!=j and j!=l and i!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i!=j and j==l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==j and j!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==j and j==l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==l and j!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
print(ans)