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

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

saisyou = N

for i in range(1,N):
    west = S[0:i-1]
    east = S[i:N]
    tmp = west.count("W") + east.count("E")
    if saisyou > tmp:
        saisyou = tmp
print(saisyou)

### FIXED CODE ###

N = int(input())
S = input()
    
total = []
_sum1 = []
_sum2 = []
if S[0] == "W":
    _sum1.append(1)
else:
    _sum1.append(0)
if S[-1] == "E":
    _sum2.append(1)
else:
    _sum2.append(0)

for i in range(1,N):
    if S[i] == "W":
        _sum1.append(_sum1[i-1]+1)
    else:
        _sum1.append(_sum1[i-1])
    if S[-(i+1)] == "E":
        _sum2.append(_sum2[i-1]+1)
    else:
        _sum2.append(_sum2[i-1])

j = 0
for k in _sum2[::-1]:
    total.append(_sum1[j] + k)
    j += 1

print(min(total)-1)
### BUGGY CODE ###

N = int(input())
a = [i+1 for i in range(N-1)]
print(sum(a))

### FIXED CODE ###

N = int(input())
if N%2==0:
    print(N//2+N*((N-1)//2))
elif N%2!=0:
    print(N*(N//2))
### BUGGY CODE ###

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9 + 7
comb = Combination(sum([r1, c1, r2, c2]) + 10)

ans = 0

for c in range(c1, c2 + 1):
    ans = (ans + comb.ncr(r2 + c + 1, c + 1) - comb.ncr(r1 + c, c + 1)) % MOD

print(ans)

### FIXED CODE ###

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9 + 7
comb = Combination(r2 + c2 + 10)

ans = 0

for c in range(c1, c2 + 1):
    ans = (ans + comb.ncr(r2 + c + 1, c + 1) - comb.ncr(r1 + c, c + 1)) % MOD

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

s=input()
MOD=10**9+7
dp=[[0 for i in range(13)] for j in range(2)]

if s[0]=='?':
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(s[0])]=1

i=1
for c in s[1:]:
  c = -1 if c=='?' else int(c)
  for k in range(13):
    dp[i%2][k]=0

  if c==-1:
    for j in range(10):
      for k in range(13):
        dp[i%2][(k*10+j)%13]+=dp[(i-1)%2][k]
  else:
    for k in range(13):
      dp[i%2][(k*10+c)%13]+=dp[(i-1)%2][k]

  for j in range(13):
    dp[i%2][j]%=MOD
  i += 1

print(dp[(i-1)%2][5])


### FIXED CODE ###

S=input()
a=[0]*13
a[0]= 1

for c in S:
  dp=[0]*13
  for i in range(13):
    dp[(i*10)%13]=a[i]%(10**9+7)
  dp+=dp

  if c=='?':
    for i in range(13):
      a[i]=sum(dp[i+4:i+14])
  else:
    for i in range(13):
      a[i]=dp[i+13-int(c)]

print(a[5]%(10**9+7))
### BUGGY CODE ###

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

ans = N
for i in range(N + 1):
    left_num = S[:i].count('#')
    right_num = S[i:].count('.')

    if right_num == N - i:
        right_num = 0
    ans = min(ans, (left_num + right_num))
    if right_num in [0, N - i] or left_num > right_num:
        break
print(ans)

### FIXED CODE ###

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

all_black_num = S.count('#')
all_white_num = N - all_black_num

if all_black_num == 0 or all_white_num == 0:
    ans = 0
else:
    left_black_num = 0
    left_white_num = 0
    right_white_num = all_white_num - left_white_num
    right_black_num = all_black_num - left_black_num
    ans = left_black_num + right_white_num
    for i, c in enumerate(S):
        if c == '#':
            left_black_num += 1
        elif c == '.':
            left_white_num += 1
        right_white_num = all_white_num - left_white_num
        right_black_num = all_black_num - left_black_num
        ans = min(ans, left_black_num + right_white_num)
        if right_black_num == N - i - 1:
            break
print(ans)
### BUGGY CODE ###

import sys 
from collections import deque
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def R(x):
    r = round(x)
    if r+0.5 <= x:
        r += 1
    return r

def main():
    tmp = deque(LI())
    n,k = tmp.popleft(),tmp.popleft()
    a = LI()
    for _ in range(k):
        table = [0]*n
        for j in range(n):
            left = R(max(0,j-a[j]-0.5))
            right = int(min(n-1,j+a[j]+0.5))
            for u in range(left,right+1):
                table[u] += 1
        a = table[:]
    for i in range(n):
        print(str(a[i])+' ',end='')
    return

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
from itertools import accumulate

def solve(n,k,a):
    for _ in range(k):
        if a==[n]*n:    return a
        t = [0]*(n+1)
        for i,x in enumerate(a):
            t[max(0,i-x)] += 1
            t[min(n,i+x+1)] -=1
        a = list(accumulate(t))[:-1]
    return a

n,k = map(int,sys.stdin.readline().rstrip().split())
a = list(map(int,sys.stdin.readline().rstrip().split()))

print(*solve(n,k,a))
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z == s:
        ans += 1
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ct = 0
for x in range(0, k + 1):
    for y in range(0, k + 1):
        z = s - x - y 
        if z >= 0 and z <= k:
            ct += 1
print(ct)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def solve():
    N,M = map(int,input().strip().split())
    ans = [0]*(N+1)
    g = dict()
    for i in range(M):
      ai,bi = map(int,input().strip().split())
      if ai in g:
        g[ai].append(bi)
      else:
        g[ai] = [bi]
      if bi in g:
        g[bi].append(ai)
      else:
        g[bi] = [ai]

    Q = int(input())
    for i in range(Q):
      v,d,c = map(int,input().strip().split())
      ans[v]=c
      queue = set(g.get(v,list()))
      for j in range(d):
        n_queue = set()
        done = set()
        for idx in queue:
          ans[idx]=c
          if idx not in done:
            n_queue.update(set(g.get(idx,list())))
            done.add(idx)
        queue = n_queue
    for i in range(N):
      print(ans[i+1])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
input = sys.stdin.readline

INF = 10**14

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

maxd = 0
Q = int(input())
Query = []
Color = []
for _ in range(Q):
    v, d, c = map(int, input().split())
    if d > maxd:
        maxd = d
    Query.append((v-1, d))
    Color.append(c)

Query = Query[::-1]
Color = Color[::-1]

dp = [[INF]*(maxd+1) for _ in range(N)]
for i, (v, d) in enumerate(Query):
    if i < dp[v][d]:
        dp[v][d] = i

for d in reversed(range(maxd)):
    for v in range(N):
        if dp[v][d+1] < dp[v][d]:
            dp[v][d] = dp[v][d+1]
        for nv in graph[v]:
            if dp[v][d+1] < dp[nv][d]:
                dp[nv][d] = dp[v][d+1]

for v in range(N):
    seq = dp[v][0]
    if seq == INF:
        print(0)
    else:
        print(Color[seq])
### BUGGY CODE ###

import itertools
mod = 10 ** 9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = 0
for i in itertools.combinations(a, k):
    ans += (max(i) - min(i)) % mod

print(ans % mod)

### FIXED CODE ###

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


N, K = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
p = 10 ** 9 + 7
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

i = 0
f_max = 0
f_min = 0
while N - 1 - i >= K - 1:
    r = cmb(N - 1 - i, K - 1, p)
    f_max += a[i] * r
    f_min += a[N - i - 1] * r
    i += 1

print((f_max - f_min) % p)
### BUGGY CODE ###

N=int(input())
H=list(map(int,input().split()))
L=[0 for _ in range(N)]
for t in range(N):
    for i in range(t,N):
        if t==i:
            continue
        if H[t]>=H[i]:
            L[t]+=1
            H[t]=H[i]
        else:
            break
print(sorted(L,reverse=True)[0])

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
min=H[0]
count=[0 for _ in range(N)]
cnt=0
t=0
for i in range(1,N):
    if H[i]<=min:
        min=H[i]
        cnt+=1
    else:
        count[t]=cnt
        cnt=0
        t+=1
        min=H[i]
count[t]=cnt
print(max(count))
### BUGGY CODE ###

s = input()[::-1]
n = len(s)
amari = [0]*2019
amari[0] = 1

temp = 0
d = 1
for char in s:
    temp += int(char)*d
    index = temp%2019
    amari[index] += 1
    d *= 10

ans = 0
for i in amari:
    ans += i*(i-1)/2

print(int(ans))



### FIXED CODE ###

s = input()[::-1]
n = len(s)
amari = [0]*2019
amari[0] = 1

temp = 0
d = 1
for char in s:
    temp += int(char)*d
    temp %= 2019
    d *= 10
    d %= 2019  
    amari[temp] += 1

ans = 0
for i in amari:
    ans += i*(i-1)/2

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

N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
LR.sort()
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    f = 0
    p = ma[i]
    if p != 0:
        for l,r in LR:
            for j in range(l,r+1):
                if i+j < N:
                    ma[i+j] += p
                else:
                    f = 1
                    break
            if f:
                break
print(ma[N-1]%mod)

### FIXED CODE ###

N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
LR.sort()
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if i >1:
        ma[i] += ma[i-1]
    p = ma[i]%mod
    if p != 0:
        for l,r in LR:
            if i+l <N:
                ma[i+l] += p
            else:
                break
            if i+r+1<N:
                ma[i+r+1] -= p
print(ma[N-1]%mod)
### BUGGY CODE ###

import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
L = [list(input().strip())  for _ in range(N)]
# S = input().strip

al = [[False for _ in range(M)] for _ in range(N)]
d = set()
for i in range(N):
    for j in range(M):
        if L[i][j] == "#":
            al[i][j] = True
            d.add((i, j))
            pass

c = 0
for i in range(10000):
    if len(d) == 0:
        print(i - 1)
        exit()
    else:
        d2 = set()
        for x, y in d:
            c += 1
            if x - 1 >= 0 and al[x - 1][y] == False:
                al[x - 1][y] = True
                d2.add((x - 1, y))

            if x + 1 < N and al[x + 1][y] == False:
                al[x + 1][y] = True
                d2.add((x + 1, y))

            if y - 1 >= 0 and al[x][y - 1] == False:
                al[x][y - 1] = True
                d2.add((x, y - 1))

            if y + 1 < M and al[x][y + 1] == False:
                al[x][y + 1] = True
                d2.add((x, y + 1))

        d = d2


### FIXED CODE ###

import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
L = [list(input().strip())  for _ in range(N)]
# S = input().strip

al = [[False for _ in range(M)] for _ in range(N)]
d = []
for i in range(N):
    for j in range(M):
        if L[i][j] == "#":
            al[i][j] = True
            d.append((i, j))
            pass

for i in range(10000):
    if len(d) == 0:
        print(i - 1)
        exit()
    else:
        d2 = list()
        for x, y in d:
            if x - 1 >= 0 and al[x - 1][y] == False:
                al[x - 1][y] = True
                d2.append((x - 1, y))

            if x + 1 < N and al[x + 1][y] == False:
                al[x + 1][y] = True
                d2.append((x + 1, y))

            if y - 1 >= 0 and al[x][y - 1] == False:
                al[x][y - 1] = True
                d2.append((x, y - 1))

            if y + 1 < M and al[x][y + 1] == False:
                al[x][y + 1] = True
                d2.append((x, y + 1))

        d = d2
### BUGGY CODE ###

x, y = map(int,input().split())

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            choice = 0
            for j in cf:
                if i % j == 0:
                    choice = 1
            if choice == 0:
                cf.append(i)
            elif choice == 1:
                continue
    return cf

cf_li = cf(x,y)

print(len(cf_li) + 1)

### FIXED CODE ###

import math
import fractions

x, y = map(int,input().split())

gcd = fractions.gcd(x,y)

size = int(math.sqrt(gcd)) + 1

def calc_div(num):
    table =  []
    for i in range(2,int(math.sqrt(num))+1):
        if num % i == 0:
            table.append(i)    
            while num % i == 0:
                num //= i
    if num > int(math.sqrt(num)):
        table.append(num)
    return table 

ans = calc_div(gcd)

print(len(ans) + 1)
### BUGGY CODE ###

N=int(input())
s=["".join(sorted(list(input()))) for i in range(N)]
ss = set(s)
cnt = 0
for i in ss:
  B = s.count(i)
  cnt += int(B * (B-1) /2)
print(cnt)


### FIXED CODE ###

N=int(input())
d={}
for i in range(N):
  a = "".join(sorted(list(input())))
  if a not in d:
    d[a] = 1
  else:
    d[a]=d[a]+1
cnt = 0
for B in d.values():
  cnt += int(B * (B-1) /2)
print(cnt)
### BUGGY CODE ###

import bisect

ans = 0
N = int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
B.sort()
C.sort()
length = len(A)
#A<B<Cの組み合わせの数が答え
for i in range(length):
    #Aを1つ決めた時、BがA以下の値
    A_miman = bisect.bisect_right(B,A[i])
    for j in range(A_miman,N):
        #Bを1つ決めた時、CがBより大きい値の数をansに足す
        ans += N - bisect.bisect_right(C, B[j])
        


print(ans)

### FIXED CODE ###

import bisect

ans = 0
N = int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
B.sort()
C.sort()


#A<B<Cの組み合わせの数が答え
for i in range(N):
    #Bを1つ決めた時、AがB未満の場合の総数
    B_miman = bisect.bisect_left(A,B[i])
    #Bを1つ決めた時、CがB以上の場合の総数
    B_ijou = N - bisect.bisect_right(C, B[i])

    ans+= B_miman*B_ijou

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

N=int(input())
a_list = []
b_list = []
c_list = []
d_list = []
e_list = []
f_list = []
g_list = []
h_list = []
i_list = []
j_list = []
k_list = []
l_list = []
m_list = []
n_list = []
o_list = []
p_list = []
q_list = []
r_list = []
s_list = []
t_list = []
u_list = []
v_list = []
w_list = []
x_list = []
y_list = []
z_list = []
for i in range(N):
  s = input()
  if s[0] == "a":
    if not s in a_list:
      a_list.append(s)
  if s[0] == "b":
    if not s in b_list:
      b_list.append(s)
  if s[0] == "c":
    if not s in c_list:
      c_list.append(s)
  if s[0] == "d":
    if not s in d_list:
      d_list.append(s)
  if s[0] == "e":
    if not s in e_list:
      e_list.append(s)
  if s[0] == "f":
    if not s in f_list:
      f_list.append(s)
  if s[0] == "g":
    if not s in g_list:
      g_list.append(s)
  if s[0] == "h":
    if not s in h_list:
      h_list.append(s)
  if s[0] == "i":
    if not s in i_list:
      i_list.append(s)
  if s[0] == "j":
    if not s in j_list:
      j_list.append(s)
  if s[0] == "k":
    if not s in k_list:
      k_list.append(s)
  if s[0] == "l":
    if not s in l_list:
      l_list.append(s)
  if s[0] == "m":
    if not s in m_list:
      m_list.append(s)
  if s[0] == "n":
    if not s in n_list:
      n_list.append(s)
  if s[0] == "o":
    if not s in o_list:
      o_list.append(s)
  if s[0] == "p":
    if not s in p_list:
      p_list.append(s)
  if s[0] == "q":
    if not s in q_list:
      q_list.append(s)
  if s[0] == "r":
    if not s in r_list:
      r_list.append(s)
  if s[0] == "s":
    if not s in s_list:
      s_list.append(s)
  if s[0] == "t":
    if not s in t_list:
      t_list.append(s)
  if s[0] == "u":
    if not s in u_list:
      u_list.append(s)
  if s[0] == "v":
    if not s in v_list:
      v_list.append(s)
  if s[0] == "w":
    if not s in w_list:
      w_list.append(s)
  if s[0] == "x":
    if not s in x_list:
      x_list.append(s)
  if s[0] == "y":
    if not s in y_list:
      y_list.append(s)
  if s[0] == "z":
    if not s in z_list:
      z_list.append(s)
count = len(a_list)
count = count + len(b_list)
count = count + len(c_list)
count = count + len(d_list)
count = count + len(e_list)
count = count + len(f_list)
count = count + len(g_list)
count = count + len(h_list)
count = count + len(i_list)
count = count + len(j_list)
count = count + len(k_list)
count = count + len(l_list)
count = count + len(m_list)
count = count + len(n_list)
count = count + len(o_list)
count = count + len(p_list)
count = count + len(q_list)
count = count + len(r_list)
count = count + len(s_list)
count = count + len(t_list)
count = count + len(u_list)
count = count + len(v_list)
count = count + len(w_list)
count = count + len(x_list)
count = count + len(y_list)
count = count + len(z_list)
print(count)

### FIXED CODE ###

import numpy as np
N=int(input())
S_list = np.zeros(N)
#S_list = np.zeros(N,dtype=str)
e_list = "abcdefghijklmnopqrstuvwxyz"

for i in range(N):
  s = input()
  n = 0
  for k in range(len(s)):
    n = n + (e_list.index(s[k])+1)*(100**k)
  S_list[i] = n
print(len(np.unique(S_list)))
### BUGGY CODE ###

from inspect import currentframe

def chkprint(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

from functools import reduce
from math import floor, ceil

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

left = 1
center = 2
right = 3

res = 10**16



p = sum(A[0:left])
q = sum(A[left:center])
r = sum(A[center:right])
s = sum(A[right:])

# print(A)

while center <= N - 2:
  while True:
    p = sum(A[0:left])
    q = sum(A[left:center])

    if abs(p-q) < abs(p-q+2*A[left]):
      break

    if left == center-1:
      break

    left += 1

  while True:
    r = sum(A[center:right])
    s = sum(A[right:])

    if abs(r-s) < abs(r-s+2*A[right]):
      break

    if right == N-1:
      break

    right += 1

  res = min(max(p,q,r,s)-min(p,q,r,s),res)

  # print(A[0:left], A[left:center], A[center:right], A[right:], res)
  center += 1

print(res)


### FIXED CODE ###

from inspect import currentframe

def chkprint(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

from functools import reduce
from math import floor, ceil

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

left = 1
center = 2
right = 3

res = 10**16



p = sum(A[0:left])
q = sum(A[left:center])
r = sum(A[center:right])
s = sum(A[right:])

# print(A)

while center <= N - 2:
  while True:
    if abs(p-q) < abs(p-q+2*A[left]):
      break

    if left == center-1:
      break

    p += A[left]
    q -= A[left]
    left += 1

  while True:
    if abs(r-s) < abs(r-s+2*A[right]):
      break

    if right == N-1:
      break

    r += A[right]
    s -= A[right]
    right += 1

  res = min(max(p,q,r,s)-min(p,q,r,s),res)

  # print(A[0:left], A[left:center], A[center:right], A[right:], res)
  q += A[center]
  r -= A[center]
  center += 1

print(res)
### BUGGY CODE ###

N = int(input())

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

Q = int(input())

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

list = [0] * 100001
sum = 0
for i in range(100001):
    list[i] = A.count(i)

for j in range(N):
    sum += A[j] 

for k in range(Q):
    sum += list[B[k]] * (C[k] -B[k])
    list[C[k]] += list[B[k]]
    list[B[k]] = 0
    print(sum)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B=[]
C=[]

for _ in range(Q):
    bi, ci = list(map(int, input().split()))
    B.append(bi)
    C.append(ci)

dic = {}
for i in A:
    dic[i] = dic.get(i,0) + 1

sum = sum(A)

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

import sys

sys.setrecursionlimit(10 ** 6)


def bw(i, p):
    if dp[i] != [0, 0]:
        return dp[i]
    b = w = 1
    for ii in h[i]:
        if ii in p: continue
        bwi = bw(ii, p + [ii])
        w *= (bwi[0] + bwi[1])
        b *= bwi[1]
        w %= md
        b %= md
    dp[i] = [b, w]
    return [b, w]


md = 10 ** 9 + 7
n = int(input())
if n == 1:
    print(2)
    exit()
h = {}
for _ in range(n - 1):
    a, b = map(int, input().split())
    h.setdefault(a, [])
    h.setdefault(b, [])
    h[a] += [b]
    h[b] += [a]
dp = [[0, 0] for _ in range(n + 1)]
b, w = bw(1, [1])
print((b + w) % md)


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def bw(i, p):
    if dp[i] != [0, 0]:
        return dp[i]
    b = w = 1
    for ii in h[i]:
        if ii == p: continue
        bwi = bw(ii,i)
        w *= (bwi[0] + bwi[1])
        b *= bwi[1]
        w %= md
        b %= md
    dp[i] = [b, w]
    return [b, w]


md = 10 ** 9 + 7
n = int(input())
if n == 1:
    print(2)
    exit()
h = {}
for _ in range(n - 1):
    a, b = map(int, input().split())
    h.setdefault(a, [])
    h.setdefault(b, [])
    h[a] += [b]
    h[b] += [a]
dp = [[0, 0] for _ in range(n + 1)]
b, w = bw(1, 1)
print((b + w) % md)
### BUGGY CODE ###

def main():
    # ABC117c
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    n, m = map(int, input().split())
    x = list(map(int, input().split()))
    if(m == 1):
        print(0)
        exit(0)
    if(n >= m):
        print(0)
        exit(0)
    x.sort()
    sa = [0]
    for i in range(1, m):
        sa.append(x[i]-x[i-1])
    # print(x)
    # print(sa)
    # print('aa')
    sa.sort()
    for _ in range(min(n-1, len(sa)-1)):
        sa = sa[:-1]
    # print(sa)
    print(sum(sa))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    # ABC117c
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    n, m = map(int, input().split())
    x = list(map(int, input().split()))
    if(m == 1):
        print(0)
        exit(0)
    if(n >= m):
        print(0)
        exit(0)
    x.sort()
    sa = [0]
    for i in range(1, m):
        sa.append(x[i]-x[i-1])
    # print(x)
    # print(sa)
    # print('aa')
    sa.sort()
    # or _ in range(min(n-1, len(sa)-1)):
    #    sa = sa[:-1]
    # print(sa)
    print(sum(sa[:len(sa)-min(n-1, len(sa)-1)]))


if __name__ == '__main__':
    main()