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

import sys

S=input()
if len(S)<2: print(0),sys.exit()
elif len(S)==3:
    print(1 if S=="ABC" else 0)
    sys.exit()

s=[]
a=[]
for i in range(len(S)):
    s.append(S[i])
    if s[i]=="A": a.append(i)

tmp=0
abc,bca=["A","B","C"],["B","C","A"]
ans=0
while True:
    if a==[] or a[0]>=len(s)-2: break
    tmp=a[0]
    if s[tmp:tmp+3]==abc:
        s[tmp:tmp+3]=bca
        a.insert(0,tmp+2)
        if tmp>0 and s[tmp-1]=="A": a.insert(0,tmp-1)
        ans+=1
    else: a.pop(0)

print(ans)

### FIXED CODE ###

import sys

S=input()
if len(S)<2: print(0),sys.exit()
elif len(S)==3:
    print(1 if S=="ABC" else 0)
    sys.exit()



s=[S[i] for i in range(len(S))]
tmp=0
abc,bca=["A","B","C"],["B","C","A"]
ans=0
a,bc=0,0
i=0
while i<len(s)-1:
    if s[i]=="A": a+=1
    elif s[i]=="B" and s[i+1]=="C":
        bc+=1
        i+=1
        ans+=a
    
    else:
        a,bc=0,0
    i+=1
print(ans)
### BUGGY CODE ###

# ABC 055: B – Training Camp
from math import factorial

n = int(input())
power = 1

for i in range(1, n + 1):
    power *= i

print(power % (10 ** 9 + 7))

### FIXED CODE ###

# ABC 055: B – Training Camp
from math import factorial

n = int(input())

print(factorial(n) % (10 ** 9 + 7))
### BUGGY CODE ###

from sys import exit
from collections import defaultdict
n,x = open(0).read().split()
n = int(n)
x = int(x, 2)
x = x^(2**(n-1))

d = defaultdict(int)
d[0] = 0
def calc(m):
    if m not in d:
        nxt = m % bin(m).count('1')
        d[m] = calc(nxt) + 1
    return d[m]

if n == 1:
    print(calc(x))
    exit()

mask = 3 << (n-2)

while 1:
    print(calc(x))
    x ^= mask
    if mask < 3:
        break
    mask //= 2

### FIXED CODE ###

from sys import exit
from collections import defaultdict
n,x = open(0).read().split()
n = int(n)
cnt = x.count('1') 
digits = list(map(int, list(x)))
x = int(x, 2)

d = defaultdict(int)
d[0] = 0
def calc(m):
    if m not in d:
        nxt = m % bin(m).count('1')
        d[m] = calc(nxt) + 1
    return d[m]

if n == 1:
    print(calc(x^1))
    exit()

mmod = cnt - 1
pmod = cnt + 1

if mmod > 0:
    mx = x % mmod
px = x % pmod

mbase = 1
pbase = 1

ans = []
while digits:
    digit = digits.pop()
    
    if digit and mmod <= 0:
        ans.append(0)
    else:
        if digit:
            nx = (mx - mbase)%mmod
        else:
            nx = (px + pbase)%pmod
        ans.append(calc(nx) + 1)

    if mmod > 0:
        mbase = (mbase * 2) % mmod
    pbase = (pbase * 2) % pmod

while ans:
    print(ans.pop())
### BUGGY CODE ###

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

cnt = 0
while all(map(lambda x: x%2 == 0, list_a)):
    list_a = list(map(lambda x: x%2, list_a))
    cnt +=1

print(cnt)

### FIXED CODE ###

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

cnt = 0
while all(map(lambda x: x%2 == 0, list_a)):
    list_a = list(map(lambda x: x/2, list_a))
    cnt +=1

print(cnt)
### BUGGY CODE ###

import bisect
a,b,q = map(int,input().split())
s = [-10**11]+[int(input()) for _ in range(a)]+[10**11]
t = [-10**11]+[int(input()) for _ in range(b)]+[10**11]
for i in range(q):
  ans = 10**11
  x = int(input())
  l = bisect.bisect(s,x)
  m = bisect.bisect(t,x)
  arr = [[s[l-1],s[l]],[t[m-1],t[m]]]
  for i in range(4):
    S = 0
    now = x
    for j in range(2):
      S += (now-arr[j][i >> j & 1])*(-1)**(((now-arr[j][i >> j & 1])<0))
      now = arr[j][i >> j & 1]
    if ans > S:
      ans = S
  for i in range(4):
    S = 0
    now = x
    for j in range(2):
      S += (now-arr[1-j][i >> j & 1])*((-1)**((now-arr[1-j][i >> j & 1])<0))
      now = arr[1-j][i >> j & 1]
    if ans > S:
      ans = S
  print(ans)

### FIXED CODE ###

import bisect
a,b,q = map(int,input().split())
s = [-10**11]+[int(input()) for _ in range(a)]+[10**11]
t = [-10**11]+[int(input()) for _ in range(b)]+[10**11]
for i in range(q):
  ans = 10**11
  x = int(input())
  l = bisect.bisect(s,x)
  m = bisect.bisect(t,x)
  arr = [[s[l-1],s[l]],[t[m-1],t[m]]]
  for i in range(4):
    S = 0
    now = x
    for j in range(2):
      t0 = now-arr[j][i >> j & 1]
      S += t0*((-1)**(t0<0))
      now -= t0
    if ans > S:
      ans = S
  for i in range(4):
    S = 0
    now = x
    for j in range(2):
      t0 = now-arr[1-j][i >> j & 1]
      S += t0*((-1)**(t0<0))
      now -= t0
    if ans > S:
      ans = S
  print(ans)
### BUGGY CODE ###

from numpy import array
N, K = list(map(int, input().split()))
A = array(list(map(int, input().split())))
div = 1000000007
s = 0
s2 = 0
for i, n in enumerate(A):
    tmp = A < n
    s += int(sum(tmp[i+1:]))
    s2 += int(sum(tmp))

print(((s * K) + (s2 * (K-1) * K // 2)) % div)


### FIXED CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
div = 1000000007
s = 0
ss = 0

for i, a in enumerate(A):
    for j in range(i+1, N):
        if a > A[j]:
            s += 1

for i in A:
    for j in A:
        if i > j:
            ss += 1

print(((s * K) + (ss * K * (K-1) // 2)) % div)
### BUGGY CODE ###

import heapq
from sys import stdin
h,w = map(int,input().split())
si,sj = map(int,input().split())
gi,gj = map(int,input().split())
si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
grid = []
for _ in range(h):
    grid.append(stdin.readline()[:-1])
dist = {(i,j):float("inf") for i in range(h) for j in range(w)}
dist[si,sj] = 0
heap = [(0,si,sj)]
while heap:
    mindist,i,j = heapq.heappop(heap)
    if (i,j) == (gi,gj):
        print(mindist)
        break
    if mindist > dist[i,j]: continue
    for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
        if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
            if dist[ni,nj] > dist[i,j]:
                dist[ni,nj] = dist[i,j]
                heapq.heappush(heap,(dist[ni,nj],ni,nj))
    for ni in range(i-2,i+3):
        if not (0 <= ni and ni < h): continue
        for nj in range(j-2,j+3):
            if not (0 <= nj and nj < w): continue
            if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                if dist[ni,nj] > dist[i,j] + 1:
                    dist[ni,nj] = dist[i,j] + 1
                    heapq.heappush(heap,(dist[ni,nj],ni,nj))
 
else:
    print(-1)

### FIXED CODE ###

from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())
### BUGGY CODE ###

L, R = map(int, input().split())
min_s = 2019
for i in range(L, R):
    for j in range(i + 1, R+1):
        ij = i * j
        m = ij % 2019
        if min_s > m:
            min_s = m
print("{}".format(min_s))

### FIXED CODE ###

L, R = map(int, input().split())
min_s = 2019
if (R - L) > 2019:
    min_s = 0
for i in range(L, R):
    for j in range(i + 1, R+1):
        ij = i * j
        m = ij % 2019
        if min_s > m:
            min_s = m
        if min_s == 0:
            break
    if min_s == 0:
        break
print("{}".format(min_s))
### BUGGY CODE ###

import sys
import copy
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n,k = LI()
a = LI()

preval = 1
val = 1
for i in range(n):
    val = val * a[i]
    if(i >= k):
        val = val // a[i-k]
        if(preval < val):
            print('Yes')
        else:
            print('No')
    preval = val

### FIXED CODE ###

import sys
import copy
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n,k = LI()
a = LI()

for i in range(n):
    if(i >= k):
        if(a[i] > a[i-k]):
            print('Yes')
        else:
            print('No')
### BUGGY CODE ###

from functools import lru_cache
import sys

S = input().strip()

MOD = 10 ** 9 + 7

lens = len(S)

sys.setrecursionlimit(10 ** 8)


@lru_cache(maxsize=None)
def solve(amari, keta):
    if keta == lens - 1:
        if S[keta] == "?":
            cnt = 0
            for i in range(9, -1, -1):
                if (amari + i) % 13 == 5:
                    cnt += 1
            return cnt
        else:
            if (amari + int(S[keta])) % 13 == 5:
                return 1
            else:
                return 0
    else:
        if S[keta] == "?":
            x = 0
            for i in range(9, -1, -1):
                x += solve((amari + (i * 10 ** (lens - 1 - keta)) % 13) % 13, keta + 1)
                x %= MOD
            return x
        else:
            return solve((amari + (int(S[keta]) * 10 ** (lens - 1 - keta)) % 13) % 13, keta + 1) % MOD


print(solve(0, 0) % MOD)


### FIXED CODE ###


S = input()

MOD = 10 ** 9 + 7
count = 0
S_len = len(S)

dp = [[0 for i in range(13)] for j in range(100006)]
c = -1
if S[0] != '?':
    c = int(S[0])
for j in range(10):
    if c == -1:
        dp[1][j] = 1
    else:
        dp[1][c] = 1

for i in range(2, S_len + 1):
    c = -1
    if S[i - 1] != '?':
        c = ord(S[i - 1]) - ord('0')

    for j in range(10):
        if c != -1 and c != j:
            continue
        for k in range(13):
            dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD


print(dp[S_len][5] % MOD)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
s = str(input())
q = int(input())
l = []
for i in range(q):
  qy = input().split()
  l.append(qy)
  
st = s
count = 0
for i in range(q):
  k = l[i][0]
  if(k == '1'):
    count += 1
  elif(k == '2'):
    c = count
    d = int(l[i][1])
    if((c + d) % 2 == 1):
      e = l[i][2]
      st = e + st
    elif((c + d) % 2 == 0):
      e = l[i][2]
      st = st + e

if(count % 2 == 1):
  st = st[::-1]
      
print(st)

### FIXED CODE ###

# -*- coding: utf-8 -*-
s = str(input())
q = int(input())  
st = s
sth = s
sth2 = ""
stm = ""
stm2 = ""
count = 0
flagh = 0
flagm = 0
for i in range(q):
  k = input().split()
  if(k[0] == '1'):
    count = (count + 1) % 2
  else:
    c = count - 2
    d = int(k[1]) 
    e = k[2]
    if(c + d != 0):
      sth = e + sth
      if(len(sth) > 5000 and flagh == 0):
        flagh = 1
        sth2 = sth
        sth = ""
    else:
      stm = stm + e
      if(len(stm) > 5000 and flagm == 0):
        flagm = 1
        stm2 = stm
        stm = ""
      

st = sth + sth2 + stm2 + stm
if(count == 1):
  st = st[::-1]
  
print(st)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    F.sort(reverse=True)
    A.sort()
    l = -1
    r = 0
    for i in range(N):
        if A[i]*F[i] > r:
            r = A[i]*F[i]
    r += 1
    while r-l > 1:
        m = (r+l)//2
        q = []
        cost = 0
        for i in range(N):
            if F[i]*A[i] > m:
                cost += (F[i]*A[i]-m)//F[i]
                if (F[i]*A[i]-m)%F[i] != 0:
                    cost += 1
        if cost <= K:
            r = m
        else:
            l = m

    print(r)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    F.sort(reverse=True)
    A.sort()
    l = -1
    r = 0
    for i in range(N):
        if A[i]*F[i] > r:
            r = A[i]*F[i]
    r += 1
    while r-l > 1:
        m = (r+l)//2
        q = []
        cost = 0
        for i in range(N):
            if F[i]*A[i] > m:
                cost += (F[i]*A[i]-m)//F[i]
                if (F[i]*A[i]-m)%F[i] != 0:
                    cost += 1
        if cost <= K:
            r = m
        else:
            l = m

    print(r)


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

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

check = [0]*(max(A)+1)
for a in A:
    i = 1
    while a * i <= max(A):
        check[a*i] += 1
        i += 1
cnt = 0
for a in A:
    if check[a] == 1: cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = [0] * (10**6+1)
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for i in range(10**6+1)[a::a]:
        cnt[i] += 1
ans = 0
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

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

def factorize(x):
    """xの素因数分解を表す辞書 {素因数: 指数}"""
    f = {}
    d = 2
    while x > 1:
        while x % d == 0:
            if d not in f:
                f[d] = 0
            f[d] += 1
            x //= d
        if d * d > x > d:
            f[x] = 1
            break
        d += 1
    return f

def dropmin(ls):
    """[min(ls[:i] + ls[i + 1:]) for i in range(len(ls))]"""
    # l = [min(ls[:i]) for i in range(len(ls))]
    l = [float('inf')] * len(ls)
    for i in range(1, len(ls)):
        l[i] = min(l[i - 1], ls[i - 1])
    # r = [min(ls[i + 1:]) for i in range(len(ls))]
    r = [float('inf')] * len(ls)
    for i in range(len(ls) - 2, -1, -1):
        r[i] = min(r[i + 1], ls[i + 1])
    return [min(a, b) for a, b in zip(l, r)]

def prod(ls):
    p = 1
    for x in ls:
        p *= x
    return p

# 各A_iの素因数
F = [factorize(a) for a in A]

# 素因数の集合 (2要素に出現しない素因数は無視)
D =  set(F[0].keys())
D.update(F[1].keys())

# Dの要素 d → dが各A_iに含まれる個数のリスト
X = {d: [f[d] if d in f else 0 for f in F] for d in D}

# Dの要素 d → A_iを削除したときのdの個数の最小値のリスト
X = {d: dropmin(X[d]) for d in D}

S = [prod(d ** X[d][i] for d in D if X[d][i] > 0) for i in range(N)]
print(max(S))


### FIXED CODE ###

# math.gcd is introduced in python 3.5
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

N = int(input())
A = [int(a) for a in input().split()]

# L[i] = gcd(A[:i + 1])
# R[i] = gcd(A[i:])
L = [0] * N
L[0] = A[0]
for i in range(1, N):
    L[i] = gcd(L[i-1], A[i])
R = [0] * N
R[-1] = A[-1]
for i in range(N - 2, -1, -1):
    R[i] = gcd(R[i+1], A[i])

G = [0] * N
G[0]  = R[1]
G[-1] = L[-2]
for i in range(1, N - 1):
    G[i] = gcd(L[i-1], R[i+1])

print(max(G))
### BUGGY CODE ###

n=int(input())

for i in range(1000):
  for j in range(1000-i):
    for k in range(1000-i-j):
      for l in range(1000-i-j-k):
        for m in range(1000-i-j-k-l):
          for n in range(1000-i-j-k-l-m):
            price = i*100+j*101+k*102+l*103+m*104+n*105
            if price == n:
              print(1)

print(0)


### FIXED CODE ###

import sys
import math

n=int(input())
a=n%100
b=math.floor(n/100)+1
f=True
while b != 0:
  for i in range(b):
    for j in range(b-i):
      for k in range(b-i-j):
        for l in range(b-i-j-k):
          for m in range(b-i-j-k-l):
            if i+2*j+3*k+4*l+5*m == a:
              print(1)
              sys.exit()
  a+=100
  b-=1
print(0)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B, C = [], []
for _ in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

ans = sum(A)
d = dict()
for i, a in enumerate(A):
    if a not in d:
        d[a] = ()
    d[a] += (i,)

for b, c in zip(B, C):
    if b not in d:
        print(ans)
        continue
    ans += len(d[b]) * (c-b)
    if c not in d:
        d[c] = ()
    d[c] = d[c] + d[b]
    d[b] = ()
    print(ans)

### FIXED CODE ###

def main():
    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] = map(int, input().split())

    ans = sum(A)
    d = dict()
    for i, a in enumerate(A):
        d[a] = d.get(a, 0) + 1

    for b, c in zip(B, C):
        if b not in d:
            print(ans)
            continue
        ans += d[b] * (c-b)
        if c not in d:
            d[c] = 0
        d[c] = d[c] + d[b]
        d[b] = 0
        print(ans)

main()
### BUGGY CODE ###

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

a = [0]
b = [0]
T = 0
ans = 0

for i in range(N):
  a.append(a[i] + A[i])

for i in range(M):
  b.append(b[i] + B[i])

for i in range(N+1):
  for j in range(M+1):
    T = a[i] + b[j]
    if T <= K:
      ans = max(ans, (i + j))
    else:
      pass


print(ans)

### FIXED CODE ###

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

a = [0]
b = [0]
T = 0
ans = 0

for i in range(N):
  a.append(a[i] + A[i])

for i in range(M):
  b.append(b[i] + B[i])

j = M

for i in range(N+1):
  if a[i] > K:
    break
  while a[i] + b[j] > K:
    j -= 1
  ans = max(ans, i + j)


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

from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

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

# -*- coding: utf-8 -*-
"""
http://tenka1-2017-beginner.contest.atcoder.jp/tasks/tenka1_2017_c

"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    N = int(input())

    found = False
    for h in range(1, 3500+1):
        if found:
            break
        for n in range(1, 3500+1):
            try:
                w = h*n / (4*h*n/N - n - h)
            except ZeroDivisionError:
                continue
            if w > 0 and w == int(w):
                print(h, n, int(w))
                found = True
                break


if __name__ == '__main__':
    main(sys.argv[1:])
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://tenka1-2017-beginner.contest.atcoder.jp/tasks/tenka1_2017_c

"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    N = int(input())

    found = False
    for h in range(1, 3500+1):
        if found:
            break
        for n in range(1, h+1):
            try:
                w = h*n / (4*h*n/N - n - h)
            except ZeroDivisionError:
                continue
            if w > 0 and w == int(w):
                print(h, n, int(w))
                found = True
                break


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

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

var = N % K
if var == 0:
        print(0)
elif var == K-1 or var == 1:
        print(1)
else:
        while True:
                prev = N
                N = abs(N-K)
                if prev < N:
                        break
        print(prev)

### FIXED CODE ###

import math
N, K = map(int, input().split())

var = N % K
if var == 0:
        print(0)
elif var == K-1 or var == 1:
        print(1)
else:
        while N >= math.ceil(K / 2):
                N = abs(N-K*(N//K+1))
        print(N)
### BUGGY CODE ###

import copy
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
S=[list(str(input())) for i in range(H)]

field2=copy.deepcopy(S)
move=[[1,0],[-1,0],[0,1],[0,-1]]
ans=0
temp=[]

def dfs2(x,y):
    field2[x][y]='#'
    temp.append([x,y])
    for i in range(4):
        nx=x+move[i][0]
        ny=y+move[i][1]
        if 0<=nx and nx<H and 0<=ny and ny<W and field2[nx][ny]=='.':
            dfs2(nx,ny)
    return temp

start=dfs2(Ch-1,Cw-1)
while True:
    if field2[Dh-1][Dw-1]=='#':
        print(ans)
        exit()
    else:
        for i in range(len(start)):
            for hh in range(-2,3):
                for ww in range(-2,3):
                    nnx=start[0][0]+hh
                    nny=start[0][1]+ww
                    if 0<=nnx and nnx<H and 0<=nny and nny<W and field2[nnx][nny]=='.':
                        dfs2(nnx,nny)
            del(start[0])
        ans+=1
    if len(start)==0:
        print(-1)
        exit()

### FIXED CODE ###

from collections import deque
import copy
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
S=[list(str(input())) for i in range(H)]

field2=copy.deepcopy(S)
move=[[1,0],[-1,0],[0,1],[0,-1]]
ans=0
temp=deque()

def dfs2(x,y):
    field2[x][y]='#'
    temp.append([x,y])
    for i in range(4):
        nx=x+move[i][0]
        ny=y+move[i][1]
        if 0<=nx and nx<H and 0<=ny and ny<W and field2[nx][ny]=='.':
            dfs2(nx,ny)
    return temp

start=dfs2(Ch-1,Cw-1)

while True:
    if field2[Dh-1][Dw-1]=='#':
        print(ans)
        exit()
    else:
        for i in range(len(start)):
            ttemp=start.popleft()
            for hh in range(-2,3):
                for ww in range(-2,3):
                    nnx=ttemp[0]+hh
                    nny=ttemp[1]+ww
                    if 0<=nnx and nnx<H and 0<=nny and nny<W and field2[nnx][nny]=='.':
                        dfs2(nnx,nny)
        ans+=1
    if len(start)==0:
        print(-1)
        exit()
### BUGGY CODE ###

import sys
n = int(input())
an = list(map(int, sys.stdin.readline().rstrip().split()))
q = int(input())

import numpy as np

sum = np.sum(an)
ans=[]

for _ in range(q):
    b,c = map(int, input().split())
    for i in range(n):
        if b == an[i]:
            an[i]=c
            sum += c-b
    ans.append(sum)

for q in ans:
    print(q)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
li = [0]*100001
for a in A:
    li[a] += 1
ans = sum(A)
# print(dict_A)
for i in range(Q):
    b, c = map(int, input().split())
    ans += (c-b)*li[b]
    li[c] += li[b]
    li[b] = 0
    print(ans)