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

import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
# import math
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(int(pow(10, 2)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]





# @lru_cache(None)


r,g,b,n=l()
ans=0
r,g,b=sorted([r,g,b])[::-1]
for i in range(n//r+1):
    for j in range(n//g+1):
        k=n-i*r-j*g
        if(k<0):
            break
        if(k>=0 and k%b==0):
            ans+=1
print(ans)

### FIXED CODE ###


r,g,b,n=map(int,input().split())
ans=0
r,g,b=sorted([r,g,b])[::-1]
for i in range(n//r+1):
    for j in range(n//g+1):
        k=n-i*r-j*g
        if(k<0):
            break
        if(k>=0 and k%b==0):
            ans+=1
print(ans)
### BUGGY CODE ###

import sys
from collections import deque


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] <= d:
                        break
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break
    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)


### FIXED CODE ###

from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    isAC = [False] * N
    for i in range(N-1):
        if S[i] == 'A' and S[i+1] == 'C':
            isAC[i] = True

    for i in range(Q):
        res = 0
        for j in range(l[i]-1,r[i]-1):
            if isAC[j]:
                res += 1
        print(res)


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]" 
    r = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from bisect import bisect_left
from bisect import bisect_right


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    aclist = [] 
    end = N - 1
    for i in range(end):
        if S[i] == 'A' and S[i+1] == 'C':
            aclist.append(i)

    len_ac = len(aclist)

    for i in range(Q):
        res = 0
        begin = l[i] - 1
        end   = r[i] - 2

        s_start = bisect_left(aclist,begin)
        s_end   = bisect_right(aclist,end)

        print(s_end-s_start)
            


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]" 
    r = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

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

n,k =map(int,input().split())
p = list(map(int,input().split()))
kitai = []
for i in range(1,n+1):
    sum_k = 0
    for j in range(1,p[i-1]+1):
        sum_k += j *(1/p[i-1])
    kitai.append(sum_k)
ans = []
sum_ans = 0
for i in range(k):
    sum_ans += kitai[i]
ans.append(sum_ans)
j = 0
cnt = 0
for i in range(k,len(kitai)):
    sum_ans = ans[cnt]
    sum_ans -=kitai[j] 
    sum_ans += kitai[i]
    j +=1
    cnt+=1
    ans.append(sum_ans)
print(max(ans))


### FIXED CODE ###

n,k =map(int,input().split())
p = list(map(int,input().split()))
kitai = []
for i in range(n):
    sum_k = 0
    sum_k = (1 + p[i])/2
    kitai.append(sum_k)
ans = []
sum_ans = 0
for i in range(k):
    sum_ans += kitai[i]
ans.append(sum_ans)
j = 0
cnt = 0
for i in range(k,len(kitai)):
    sum_ans = ans[cnt]
    sum_ans -=kitai[j] 
    sum_ans += kitai[i]
    j +=1
    cnt+=1
    ans.append(sum_ans)
print(max(ans))
### BUGGY CODE ###

import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))
L = [0] * Q
R = [0] * Q
for i in range(Q):
    l,r = map(int, input().split())
    L[i] = l
    R[i] = r
D = {}
E = [{0:0}] * N
for i in range(N):
    if D.get(C[i], -1) == -1:
        D[C[i]] = 1
        D_other = dict(D)
        E[i] = D_other
    else:
        D[C[i]] += 1
        D_other = dict(D)
        E[i] = D_other

for i in range(Q):
    if L[i] == 1:
        E_dif = E[R[i] - 1]
    else:
        E_dif = dict(E[R[i] - 1].items() - E[L[i] - 2].items())
    ans = len(E_dif.values())
    print(ans)


### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

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

import heapq

N=int(input())
C=[[float('inf') for x in range(N)] for y in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  C[a-1][b-1]=c
  C[b-1][a-1]=c
Q,K=map(int,input().split())
d=[float('inf') for j in range(N)]
d[K-1]=0
q=[]

heapq.heappush(q, (0, K-1))
while len(q) != 0:
  prov_cost, src = heapq.heappop(q)
  if d[src] < prov_cost:
    continue
  for dest in range(N):
    cost = C[src][dest]
    if cost != float('inf') and d[dest] > d[src] + cost:
      d[dest] = d[src] + cost
      heapq.heappush(q, (d[dest], dest))

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


### FIXED CODE ###

import heapq
from collections import defaultdict

N=int(input())
V=defaultdict(set)
for i in range(N-1):
  a,b,c=map(int,input().split())
  V[a-1].add((b-1,c))
  V[b-1].add((a-1,c))

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

def dijkstra(n,v):
  d=[float('inf')]*n
  d[v]=0
  
  hq=[(0,v)]
  
  while hq:
    u = heapq.heappop(hq)[1]
    for nv,c in V[u]:
      if d[nv]>d[u]+c:
        d[nv]=d[u]+c
        heapq.heappush(hq,(d[u]+c,nv))
        
  return d

ans=dijkstra(N,K-1)

for i in range(Q):
  a,b=map(int,input().split())
  print(ans[a-1]+ans[b-1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def calc():
  mod=10**9+7
  fact=[1]
  for i in range(1,5*10**5+1):
    fact.append((fact[-1]*i)%mod)
  revfact=[1]
  for i in range(1,5*10**5+1):
    revfact.append(pow(fact[i],mod-2,mod))
  n,m=map(int,input().split())
  patternA=(fact[m]*revfact[n]*revfact[m-n]*fact[n])%mod
  patternB=patternA
  for i in range(1,n+1):
    tmp=(fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i]
    if i%2==0:
      patternB+=tmp
      patternB%=mod
    else:
      patternB-=tmp
      patternB%=mod
  print((patternA*patternB)%mod)
calc()

### FIXED CODE ###

mod=10**9+7
fact=[1]
for i in range(1,5*10**5+1):
  fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,5*10**5+1):
  revfact.append(pow(fact[i],mod-2,mod))
n,m=map(int,input().split())
patternA=(fact[m]*revfact[n]*revfact[m-n]*fact[n])%mod
patternB=patternA
for i in range(1,n+1):
  tmp=(fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i]
  if i%2==0:
    patternB+=tmp
    patternB%=mod
  else:
    patternB-=tmp
    patternB%=mod
print((patternA*patternB)%mod)
### BUGGY CODE ###

import sys
import heapq
from decimal import Decimal

input = sys.stdin.readline

x = int(input())


for i in range(-1000,1000):
    for j in range(-1000,1000):
        if i**5 + j**5 == x:
            print(i,j)
            break


### FIXED CODE ###

import sys
import heapq
from decimal import Decimal

input = sys.stdin.readline

x = int(input())


for i in range(1,1000):
    for j in range(-1000,1000):
        if i**5 - j**5 == x:
            print(i,j)
            exit(0)
### BUGGY CODE ###

n = int(input())
suuretu = list(map(int,input().split()))
nn = frg = 0
for nn in range(0,n-1):
    for mm in range(nn+1,n):
        if suuretu[nn] == suuretu[mm]:
            frg = 1
if frg == 1:
    print('NO')
else:
    print('YES')

### FIXED CODE ###

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

if len(li) == len(set(li)):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

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


def dfs(v, p=-1):
  global ans

  res = 1
  ts = []
  for u in adj[v]:
    if (u==p): continue
    t = dfs(u,v)
    res += t
    ts.append(t)

  if p != -1:
    ts.append(N-res)

  # print(v, ts)

  now = pow(2, N-1, MOD)-1
  for t in ts:
    now -= pow(2, t, MOD)-1
  ans += now
  return res

ans = 0
MOD = 10**9+7
dfs(1)
print((ans * pow(pow(2, N, MOD), MOD-2, MOD)) % MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

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

def dfs(v, p=-1):
  global ans

  res = 1
  ts = []
  for u in adj[v]:
    if (u==p): continue
    t = dfs(u,v)
    res += t
    ts.append(t)

  if p != -1:
    ts.append(N-res)

  # print(v, ts)

  # now = pow(2, N-1, MOD)-1
  now = pows[N-1]-1
  for t in ts:
    # now -= pow(2, t, MOD)-1
    now -= pows[t] - 1
  ans += now
  return res

ans = 0
MOD = 10**9+7
# 高速化1
pows = [1] * (N+1)
for i in range(1, N+1):
  pows[i] = (pows[i - 1] * 2) % MOD

dfs(1)
print((ans * pow(pows[N], MOD-2, MOD)) % MOD)
### BUGGY CODE ###

from collections import deque
S=deque(input())
Q=int(input())
for i in range(Q):
  N=list(input().split())
  if N[0]=="1":
    S.reverse()
  elif N[1]=="1":#先頭にC1
    S.appendleft(N[2])
  else:#末尾にC1
    S.append(N[2])
S="".join(S)
print(S)

### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
F=0#フラグ
for i in range(Q):
  N=list(input().split())
  if F==0:#反転していない場合
    if N[0]=="1":#反転させる
      F=1
    elif N[1]=="1":#先頭に追加
      S.appendleft(N[2])
    else:#末尾に追加
      S.append(N[2])
  elif F==1:#反転している場合
    if N[0]=="1":#反転を戻す
      F=0
    elif N[1]=="1":#末尾に追加
      S.append(N[2])
    else:#先頭に追加
      S.appendleft(N[2])
if F==1:#反転するならsを反転させる
  S.reverse()
  print("".join(S))
else:#そうでないならそのまま
  print("".join(S))
### BUGGY CODE ###

N=int(input())
equal=0
ans=0
s=[list(input()) for _ in range(N)]
s10 = [i for i in range(10)]
i=0
t=['x' for i in range(N)]
for i in range(N):
    s10 = [x for x in range(10)]
    ti = [['xx',0] for x in range(10)]
    for j in range(10):
        if j in s10:
            ti[j][0]=s[i][j]
            ti[j][1]=1
            for k in range(j+1,10):
                if s[i][j]==s[i][k]:
                    ti[j][1]=ti[j][1]+1
                    s10.remove(k)
                else:
                    pass

        else:
            pass
        j=j+1
    ti = [[ti[a][0],ti[a][1]] for a in range(10) if not ti[a][1]==0]
    t[i] =ti
    i+=1
for i in range(N):
    for j in range(i+1,N):
        equal=0
        if len(t[i])==len(t[j]):
            for k1 in range(len(t[i])):
                if t[j][k1] in t[i]:
                    k1+=1
                    equal+=1
                else:
                    pass
            if equal == len(t[i]):
                 ans+=1
                 j+=1
        else:
            continue

print(ans)

### FIXED CODE ###

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N=int(input())
t=tuple([''.join(sorted(list(input()))) for _ in range(N)])
Dic = {}
ans = 0
for i in range(N):
    if t[i] in Dic:
        Dic[t[i]]+=1
    else:
        Dic[t[i]]=1
for k in tuple(Dic.keys()):
    if Dic[k]==1:
        pass
    else:
        ans+=cmb(Dic[k], 2)
print(int(ans))
### BUGGY CODE ###

n=int(input())
k=int(input())
def cal(n,k):
  if n<10:
    if k==0: return 1
    if k==1: return n
    return 0
  q,r=divmod(n,10)
  ret=0
  if k>=1:
    ret+=cal(q,k-1)*r
    ret+=cal(q-1,k-1)*(9-r)
  ret+=cal(q,k)
  return ret

print(cal(n,k))

### FIXED CODE ###

from functools import lru_cache
n=int(input())
k=int(input())
@lru_cache(None)
def cal(n,k):
  if n<10:
    if k==0: return 1
    if k==1: return n
    return 0
  q,r=divmod(n,10)
  ret=0
  if k>=1:
    ret+=cal(q,k-1)*r
    ret+=cal(q-1,k-1)*(9-r)
  ret+=cal(q,k)
  return ret

print(cal(n,k))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jul 21 12:22:32 2019

@author: ctiuser
"""
import sys
sys.setrecursionlimit(10**6)

N, M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(M)]

if M & 1:
    print(-1)
    sys.exit()    

T = [[] for _ in range(N+1)]
for a,b in AB:
    T[a].append(b)
    T[b].append(a)

visited = [False] * (N+1)
tree = [set([]) for _ in range(N+1)]
def dfs(x=1):
    for c in T[x]:
        if visited[c]:
            continue
        tree[x].add(c)
        tree[c].add(x)
        visited[c] = True
        dfs(c)
dfs()

counta = [0] * (N+1)
ans = []
for a,b in AB:
    if b in tree[a]:
        continue
    ans.append('{} {}'.format(a,b))
    counta[a] += 1

def dfs2(x=1, parent = None):
    for y in tree[x]:
        if y == parent:
            continue
#        print(x,y)
        dfs2(y,x)
        if counta[y]&1:
            ans.append('{} {}'.format(y,x))
            counta[y] += 1
        else:
            ans.append('{} {}'.format(x,y))
            counta[x] += 1
#        print(x,y,counta)
dfs2()
for i in range(M):
    print(ans[i])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Jul 18 12:05:59 2019

@author: ctiuser
"""
import sys
sys.setrecursionlimit(10**6)

N, M = map(int,input().split())
A = [list(map(int,input().split())) for i in range(M)]

if M % 2 == 1:
    print(-1)
    sys.exit()

class UnionFind():
    def __init__(self,size):
        self.table = [-1 for i in range(size+1)]
    def find(self,x):
        if self.table[x] < 0:
            return x
        else:
            return self.find(self.table[x])
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return False
        if self.table[s1] < self.table[s2]:
            self.table[s1] = self.table[s1] + self.table[s2]
            self.table[s2] = self.find(x)
        else:
            self.table[s2] = self.table[s1] + self.table[s2]
            self.table[s1] = self.find(y)
        return True

UF = UnionFind(N)
ans = []
T = [[-1] for i in range(N+1)]
color = [-1 for i in range(N+1)]
counta = [0 for i in range(N+1)]
B = []
C = [[] for i in range(N+1)]
for c in A:
    if UF.union(c[0],c[1]):
        B.append(c)
        C[c[0]].append(c[1])
        C[c[1]].append(c[0])
    else:
        ans.append(c)
        counta[c[0]] += 1

def b(x):
    color[x] = 1
    for c in C[x]:
        if color[c] == -1:
            T[c][0] = x
            T[x].append(c)
            b(c)
b(1)

edge_leaf = []
for i in range(1,N+1):
    if len(T[i]) == 1:
        edge_leaf.append(i)

def a(x):
    p = T[x][0]
    if p == -1:
        return 0
    if counta[x] % 2 == 0:
        ans.append([p,x])
        counta[p] += 1
    else:
        ans.append([x,p])
    return p

for c in edge_leaf:
    point = c
    while color[point] == len(T[point]):
        point = a(point)
        color[point] += 1


for c in ans:
    print(' '.join(map(str,c)))
### BUGGY CODE ###

def main():
  n = int(input())
  nums = list(map(int, input().split()))
  result = 1
  if 0 in nums:
    print(0)
    return
  else:
    for i in nums:
      result *= i
    if result > 1000000000000000000:
      print(-1)
      return
    else:
      print(result)
      return


if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  n = int(input())
  nums = list(map(int, input().split()))
  result = 1
  if 0 in nums:
    print(0)
    return
  else:
    for i in nums:
      result *= i
      if result > 1000000000000000000:
        print(-1)
        return
    print(result)
    return


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

import sys
input = sys.stdin.readline
r,c,K=map(int, input().split())
grid=[[0]*(c+1) for _ in range(r+1)]
for i in range(K):
    ri,ci,vi=map(int, input().split())
    grid[ri][ci]=vi

dp=[[[0]*4 for _ in range(c+1)] for _ in range(r+1)]

for i in range(1,r+1):
    for j in range(1,c+1):
        dp[i][j][0]=max(dp[i][j][0],max(dp[i-1][j]))
        v=grid[i][j]
        if v==0:
            for k in range(4):
                dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k])
        else:
            dp[i][j][0]=max(dp[i][j][0],dp[i][j-1][0])
            dp[i][j][1]=max(dp[i][j][1],max(dp[i-1][j])+v,dp[i][j-1][1])
            dp[i][j][2]=max(dp[i][j][2],dp[i][j-1][1]+v,dp[i][j-1][2])
            dp[i][j][3]=max(dp[i][j][3],dp[i][j-1][2]+v,dp[i][j-1][3])
print(max(dp[-1][-1]))

### FIXED CODE ###

R,C,K = map(int,input().split())

grid=[[0]*C for _ in range(R)]
for i in range(K):
    x,y,v = map(int,input().split())
    grid[x-1][y-1] = v
dp1 = [[0]*(C+1) for _ in range(R+1)]
dp2 = [[0]*(C+1) for _ in range(R+1)]
dp3 = [[0]*(C+1) for _ in range(R+1)]

for i in range(R):
    for j in range(C):
        dp1[i][j] = max(dp1[i][j-1],dp1[i-1][j]+grid[i][j],
                    dp2[i-1][j]+grid[i][j],dp3[i-1][j]+grid[i][j])
        dp2[i][j] = max(dp2[i][j-1],dp1[i][j-1]+grid[i][j])
        dp3[i][j] = max(dp3[i][j-1],dp2[i][j-1]+grid[i][j])
ans=0
for i in range(R):
    for j in range(C):
        ans=max(ans,dp1[i][j],dp2[i][j],dp3[i][j])
print(ans)
### BUGGY CODE ###

#dp[i][j]:S[i-x:i]==S[j-x:j]となる最大のx
import numpy as np
from numba import njit
N = int(input())
S = np.array([ord(_) for _ in input()])
dp = np.array([[0] * (N + 1) for _ in range(N + 1)])

@njit
def solve(N, S, dp):
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i][j] = min(j - i, dp[i - 1][j - 1] + 1) if S[i] == S[j] else 0
    print(dp.max())

solve(N, S, dp)


### FIXED CODE ###

import itertools
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, j in itertools.combinations(range(N), 2):
    if S[i] == S[j]:
        dp[i][j] = dp[i - 1][j - 1] + 1
    else:
        dp[i][j] = 0
    ans = max(ans, min(j - i, dp[i][j]))
print(ans)
### BUGGY CODE ###

from bisect import bisect_right as br
from array import array
n = input()
a = array('l', sorted([int(x) for x in raw_input().split()]))
b = array('l', sorted([int(x) for x in raw_input().split()]))
c = array('l', sorted([int(x) for x in raw_input().split()]))
ans = 0
for ai in a:
	index = br(b, ai)
	for bi in b[index:]:
		ans += (n - br(c, bi))
print ans


### FIXED CODE ###

from bisect import bisect_left, bisect_right
br, bl = bisect_right, bisect_left
n = input()
a = sorted([int(x) for x in raw_input().split()])
b = sorted([int(x) for x in raw_input().split()])
c = sorted([int(x) for x in raw_input().split()])
ans = 0
for bi in b:
	ans += (bl(a, bi) * (n - br(c, bi)))
print ans
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc=[]
for i in range(q):
  b,c=map(int,input().split())
  bc.append([b,c])
for i in range(q):
  if bc[i][0] in a:
    for k in range(len(a)):
      if a[k]==bc[i][0]:
        a[k]=bc[i][1]
  print(sum(a))
      
   



### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
from collections import Counter
a_count=Counter(a)
sum=sum(a)
for i in range(q):
  b,c=map(int,input().split())
  if b in a_count:
    sum+=(c-b)*a_count[b]
    a_count[c]+=a_count[b]
    a_count.pop(b)
  print(sum)