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

from bisect import bisect
A,B,Q=map(int, input().split())
s=[int(input()) for _ in range(A)] + [99**99]
t=[int(input()) for _ in range(B)] + [99**99]
snt=[0]*A + [99**99]
tns=[0]*B + [99**99]
for i in range(A):
	p = bisect(t, s[i])
	snt[i] = min(abs(s[i] - t[p-1]), abs(s[i] - t[p]))
for i in range(B):
	p = bisect(s, t[i])
	tns[i] = min(abs(t[i] - s[p-1]), abs(t[i] - s[p]))
for _ in range(Q):
	x = int(input())
	ans = []
	p = bisect(s, x)
	ans.append(abs(s[p] - x) + snt[p])
	ans.append(abs(s[p-1] - x) + snt[p-1])
	p = bisect(t, x)
	ans.append(abs(t[p] - x) + tns[p])
	ans.append(abs(t[p-1] - x) + tns[p-1])
	print(min(ans))


### FIXED CODE ###

from bisect import bisect
A,B,Q=map(int, input().split())
s=[int(input()) for _ in range(A)] + [10**11]
t=[int(input()) for _ in range(B)] + [10**11]
for _ in range(Q):
	x = int(input())
	ans = []
	ps = bisect(s, x)
	pt = bisect(t, x)
	for vs in (s[ps], s[ps-1]):
		for vt in (t[pt], t[pt-1]):
			ans.append(abs(x - vs) + abs(vs - vt))
			ans.append(abs(x - vt) + abs(vt - vs))
	print(min(ans))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    s = list(input())[:n]

    # memory = [[0 for j in range(n)] for i in range(n)]
    # for i in range(n):
    #     for j in range(i, n):
    #         memory[i][j] = s[i] == s[j]
    #         memory[j][i] = s[i] == s[j]
    # print(memory)

    result = 0
    for i in range(n):
        for j in range(i, n):
            for k in range(j, n):
                if s[i] == s[j] or s[j] == s[k] or s[k] == s[i]:
                    continue
                if j - i == k - j:
                    continue
                result += 1
    print(result)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    s = input()

    ans = s.count('R') * s.count('G') * s.count('B')
    # print(ans)
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            k = (j - i) + j
            if k >= n:
                # print(i, j, k)
                break

            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                ans -= 1

    print(ans)


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

n = int(input())
a = list(map(int,input().split()))
if 0 in a:
    ans = 0
else:
    ans = 1
    for i in a:
        if ans * i > 10**18:
            ans = -1
        else:
            ans = ans * i
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if 0 in a:
    ans = 0
else:
    ans = 1
    for i in a:
        if ans * i > 10**18:
            ans = -1
            break
        else:
            ans = ans * i
print(ans)
### BUGGY CODE ###

k=int(input())
sev=0
for i in range(1,k+1):
  sev = sev*10+7
  if sev % k==0:
    print(i)
    break
else:
  print(-1)

### FIXED CODE ###

k=int(input())
s=0
for i in range(1,10**6):
  s=(s*10+7)%k
  if s==0:
    print(i)
    break
else:
  print(-1)
### BUGGY CODE ###

N, W = map(int, input().split())
ITEM = []
vmax, wmax = 0,0
for _ in range(N):
  w,v = map(int, input().split())
  ITEM.append((v,w))
  vmax = max(vmax,v)
  wmax = max(wmax,w)

INF = 10**18
    
def solve2():
  #dp[i][w] i個目までを選んで、重さW以下で実現できる最大の価値
  # TLEしたらiを消す。
  dp = [0] * (wmax*N+1)
  dp[0] = 0
  for i in range(1,N+1):
    v1,w1 = ITEM[i-1]
    # dp[i]消すなら、wは大きい方から探索する
    for w in range(wmax*i,-1,-1):
      if w-w1>=0:
        dp[w] = max(dp[w], dp[w-w1]+v1)
  ret = max(dp[:W+1])
  
  #for d in dp:
    #print(dp[0:20])
  return ret

ans = solve2()
  
print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
ITEM = []
vmax, wmax = 0,0
for _ in range(N):
  w,v = map(int, input().split())
  ITEM.append((v,w))
  vmax = max(vmax,v)
  wmax = max(wmax,w)

INF = 10**18
    
def solve2():
  #dp[i][w] i個目までを選んで、重さW以下で実現できる最大の価値
  # TLEしたらiを消す。
  dp = [0] * (wmax*N+1)
  dp[0] = 0
  for i in range(1,N+1):
    v1,w1 = ITEM[i-1]
    # dp[i]消すなら、wは大きい方から探索する
    for w in range(wmax*i,-1,-1):
      if w-w1>=0:
        dp[w] = max(dp[w], dp[w-w1]+v1)
  ret = max(dp[:W+1])
  
  #for d in dp:
    #print(dp[0:20])
  return ret

ans = solve2()
  
print(ans)
### BUGGY CODE ###

import math

k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans+=math.gcd(math.gcd(i,j), l)
            #print(gcd(i,j,l))
print(ans)

### FIXED CODE ###

from math import gcd

k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans+=gcd(gcd(i,j), l)
            #print(gcd(i,j,l))
print(ans)
### BUGGY CODE ###

N = int(input())


for i in range(1, N+1):
    num = 0
    sqi = int(float(i)**0.5)
    for j in range(1,sqi+1):
        sqj = int(float(i-j**2)**0.5)
        for k in range(1, sqj+1):
            c = float(i-j**2-k**2-j*k)
            if c > 0:
                c *= -1.0
                b = float(j) + float(k)
                d = b**2-4*c
                if d >=0.0:
                    z = (-b + d**0.5)/2.0
                    if z.is_integer():
                        #print(j,k,z)
                        num +=1
                    else:
                        z = (-b - d**0.5)/2.0
                        if z.is_integer():
                            #print(j,k,z)
                            num +=1
    print(num)

### FIXED CODE ###

N = int(input())
ans = [0]*(10**4+10)

for i in range(1,10**2+10):
    for j in range(1, 10**2+10):
        for k in range(1, 10**2+10):
            v = i**2 + j**2 + k**2 + i*j + j*k + k*i
            if v < 10**4+10:
                ans[v]+=1

for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
S = input()
A = S[:n]
B = S[n:][::-1]
Da = defaultdict(int)
Db = defaultdict(int)
ans = 0
for i in range(2**n):
  a1, a2 = "", ""
  for j in range(n):
    if i>>j & 1:
      a1 += A[j]
    else:
      a2 += A[j]
  Da[(a1, a2)] += 1
for i in range(2**n):
  b1, b2 = "", ""
  for j in range(n):
    if i>>j & 1:
      b1 += B[j]
    else:
      b2 += B[j]
  Db[(b1, b2)] += 1

for k in Da:
  ans += Da[k] * Db[k]
print(ans)

### FIXED CODE ###

from collections import defaultdict

n = int(input())
S = input()
A = S[:n]
B = S[n:][::-1]
Da = defaultdict(int)
Db = defaultdict(int)
ans = 0
for i in range(2**n):
  a1, a2 = "", ""
  for j in range(n):
    if i>>j & 1:
      a1 += A[j]
    else:
      a2 += A[j]
  Da[(a1, a2)] += 1
for i in range(2**n):
  b1, b2 = "", ""
  for j in range(n):
    if i>>j & 1:
      b1 += B[j]
    else:
      b2 += B[j]
  Db[(b1, b2)] += 1

for k in Da:
  ans += Da[k] * Db[k]
print(ans)
### BUGGY CODE ###

l = input()
mod = 10**9+7
L = len(l)

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod) 
  
def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

def f(x):
  res = 0
  for i in range(x+1):
    res += pow(2,x-i,mod)*comb(x,i,mod)%mod
  return res
  
ans = f(L)
cnt = 0
for i,li in enumerate(l):
  if li == '0':
    ans -= f(L-1-i)*pow(2,cnt+1,mod)
  else:
    cnt += 1
    
print(ans%mod)

### FIXED CODE ###

l = input()
mod = 10**9+7
L = len(l)

ans = pow(3,L,mod)
cnt = 0
for i,li in enumerate(l):
  if li == '0':
    ans -= pow(3,L-1-i,mod)*pow(2,cnt+1,mod)
    ans %= mod
  else:
    cnt += 1
    
print(ans%mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque


def main():
    H, W = [int(x) for x in input().split()]
    A = [["" for i in range(W)] for j in range(H)]

    for j in range(H):
        S = input().strip()
        for i, s in enumerate(list(S)):
            A[j][i] = s


    ma = 0

    dj = [1, 0, -1, 0]
    di = [0, 1, 0, -1]

    for sj in range(H):
        for si in range(W):
            for gj in range(H):
                for gi in range(W):
                    d = [[-1] * W for i in range(H)]
                    q = deque([])
                    q.append((sj, si))
                    d[sj][si] = 0

                    while q:
                        p = q.popleft()
                        if p[0] == gj and p[1] == gi:
                            break
                        for i in range(4):
                            nj = p[0] + dj[i]
                            ni = p[1] + di[i]

                            if 0 <= nj < H and 0 <= ni < W and A[nj][ni] != "#" and d[nj][ni] == -1:
                                q.append((nj, ni))
                                d[nj][ni] = d[p[0]][p[1]] + 1

                    ma = max(ma, d[gj][gi])



    print(ma)





    


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque


def main():
    H, W = [int(x) for x in input().split()]
    A = [["" for i in range(W)] for j in range(H)]

    for j in range(H):
        S = input().strip()
        for i, s in enumerate(list(S)):
            A[j][i] = s

    ma = 0

    dj = [1, 0, -1, 0]
    di = [0, 1, 0, -1]

    for sj in range(H):
        for si in range(W):
            if A[sj][si] == "#":
                continue
            d = [[-1 for i in range(W)] for j in range(H)]
            q = deque([])
            q.append((sj, si))
            d[sj][si] = 0

            while q:
                p = q.popleft()
                for i in range(4):
                    nj = p[0] + dj[i]
                    ni = p[1] + di[i]

                    if 0 <= nj < H and 0 <= ni < W and A[nj][ni] != "#" and d[nj][ni] == -1:
                        q.append((nj, ni))
                        d[nj][ni] = d[p[0]][p[1]] + 1

            for gj in range(H):
                for gi in range(W):
                    ma = max(ma, d[gj][gi])

    print(ma)





    


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

N, M = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
B = [0] * M
C = [0] * M
for i in range(M):
    B[i], C[i] = [int(i) for i in input().strip().split()]

for i in range(M):
    A.sort()
    for j in range(B[i]-1, 0-1, -1):
        if A[j] < C[i]:
            for k in range(j+1):
                A[k] = C[i]
            break
print(sum(A))


### FIXED CODE ###

N, M = [int(i) for i in input().strip().split()]
A = [int(i) for i in input().strip().split()]
A.sort()

BC = [[0, 0] for _ in range(M)]
for j in range(M):
    BC[j][0], BC[j][1] = [int(i) for i in input().strip().split()]
BC.sort(key=lambda x: x[1])

res = 0
cnt = 0
i = N - 1
j = M - 1
while True:
    if cnt == N:
        break

    if j == -1:
        res += A[i]
        i -= 1
    elif A[i] > BC[j][1]:
        res += A[i]
        i -= 1
    elif A[i] <= BC[j][1]:
        res += BC[j][1]
        BC[j][0] -= 1
        if BC[j][0] == 0:
            j -= 1
    else:
        raise ValueError
    cnt += 1
print(res)
### BUGGY CODE ###

from collections import Counter
import math

def comb(n, r):
    if n <= 1:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# print('input >>')
N = int(input())
A = list(map(int,(input().split())))

Ac = Counter(A)

# for k in Ac:
    # print(Ac[k])

sumc = 0
for Ae in dict(Ac):
    sumc += comb(Ac[Ae], 2)

# print('-----output-----')

for k in A:
    print(sumc - comb(Ac[k], 2) + comb(Ac[k]-1, 2))

### FIXED CODE ###

from collections import Counter
import math

def comb(n):
    if n <= 1:
        return 0
    return n * (n-1) // 2

# print('input >>')
N = int(input())
A = list(map(int,(input().split())))

Ac = Counter(A)

sumc = 0

for Ae in dict(Ac):
    sumc += comb(Ac[Ae])

# print('-----output-----')

for k in A:
    print(sumc - comb(Ac[k]) + comb(Ac[k]-1))
### BUGGY CODE ###

N=int(input())
s=input()
l=len(s)
dp=[[0]*(N+2) for i in range(N)]
dp[0][1]=2
dp[0][0]=1
mod=10**9+7
for i in range(N-1):
    for j in range(i+2):
        if j==0:
            dp[i+1][j+1]+=2*dp[i][j]
            dp[i+1][j+1]%=mod
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod            
            continue
        dp[i+1][j+1]+=2*dp[i][j]
        dp[i+1][j+1]%=mod
        dp[i+1][j-1]+=dp[i][j]
        dp[i+1][j-1]%=mod  
t=pow(2,(mod-2),mod)
t=pow(t,l,mod)
print((dp[-1][l]*t)%mod)


### FIXED CODE ###

N=int(input())
s=input()
l=len(s)
dp=[[0]*(N+1) for i in range(N)]
dp[0][1]=2
dp[0][0]=1
mod=10**9+7
for i in range(N-1):
    for j in range(N):
        if j==0:
            dp[i+1][j+1]+=2*dp[i][j]
            dp[i+1][j+1]%=mod
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod            
            continue
        if j!=N:
            dp[i+1][j+1]+=2*dp[i][j]
            dp[i+1][j+1]%=mod
        dp[i+1][j-1]+=dp[i][j]
        dp[i+1][j-1]%=mod  
t=pow(2,(mod-2),mod)
t=pow(t,l,mod)
print((dp[-1][l]*t)%mod)
### BUGGY CODE ###

import math

def prime_numbers(x):
    i_a = list(range(2, x+1))
    p_a = list()
    e_a = math.sqrt(x)
    h = i_a[0]
    while h < e_a:
        h = i_a[0]
        p_a.append(h)
        for j in i_a:
            if j % h == 0:
                i_a.remove(j)
    p_a += i_a
    p_a.sort()
    return p_a

if __name__ == "__main__":
    n = int(input())
    n_s = list()
    for i in range(n):
        n_s.append(int(input()))

    pnums = prime_numbers(max(n_s))
    count = 0

    for i in n_s:
        if i in pnums:
            count += 1

    print(count)

### FIXED CODE ###

import math

def is_prime(x):
    if x == 2:
        return True

    if x % 2 == 0 or x < 2:
        return False

    i = 3
    x_sqrt = math.sqrt(x)
    while i <= x_sqrt:
        if x % i == 0:
            return False
        i += 2

    return True

if __name__ == "__main__":
    n = int(input())
    count = 0
    for i in range(n):
        if is_prime(int(input())):
            count += 1

    print(count)
### BUGGY CODE ###

n = int(input())

s = []
for i in range(n):
  a = input()
  if a not in s:
    s.append(a)

print(len(s))

### FIXED CODE ###

n = int(input())

s = []
for i in range(n):
  s.append(input())

print(len(set(s)))
### BUGGY CODE ###

import sys
N,M = map(int,sys.stdin.readline().split())
ab = []
start = []
goal = []
for i in range(M):
    ab.append(list(map(int,sys.stdin.readline().split())))
for i in ab:
    if i[0] == 1:
        start.append(i[1])
    if i[1] == N:
        goal.append(i[0])
ans = 'IMPOSSIBLE'
for i in range(1,N+1):
    if i in start and i in goal:
        ans = 'POSSIBLE'
        break
print(ans)

### FIXED CODE ###

import sys
N,M = map(int,sys.stdin.readline().split())
start = []
goal = []
for i in range(M):
    a,b = map(int,sys.stdin.readline().split())
    if a == 1:
        start.append(b)
    if b == N:
        goal.append(a)
ans = 'IMPOSSIBLE'
seta = set(start)
setg = set(goal)
for i in seta:
    if i in setg:
        ans = 'POSSIBLE'
        break
print(ans)
### BUGGY 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(min(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])

### 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(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 ###

import math
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}

    def make(self, x):
        self.p[x] = x

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if x >= y:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            return x


_ncr = {}


def ncr(n, r):
    if n < r:
        return 0
    k = "{}:{}".format(n, r)
    if k not in _ncr:
        _ncr[k] = math.factorial(n) // (math.factorial(n - r) *
                                        math.factorial(r))
    return _ncr[k]


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

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = []
total = ncr(N, 2)
now = 0
for i in range(M):
    ans.append(total)

    a, b = ab[i]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        n = h.get(x, 1) + h.get(y, 1)
        total += ncr(h.get(x, 1), 2) + ncr(h.get(y, 1), 2)
        total -= ncr(n, 2)

        if x in h:
            del h[x]
        if y in h:
            del h[y]
        h[a] = n

for v in reversed(ans):
    print(v)

### FIXED CODE ###

from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


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

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)
### BUGGY CODE ###

n = int(input())
S = [ input() for _ in range(n) ]

# print(S)

import collections

c = collections.Counter(S)

# print(c)
# print(c.most_common())
# print(c.most_common()[0][0])

ls_ans = []
ls_ans.append( c.most_common()[0][0] )

a = c.most_common()[0][1]
for i in range(1,len(c)):
    if c.most_common()[i][1]==a:
        ls_ans.append(c.most_common()[i][0])

ans = sorted(ls_ans)

print("\n".join(ans))

### FIXED CODE ###

n = int(input())
S = [ input() for _ in range(n) ]

import collections

c = collections.Counter(S)
b = c.most_common()

ls_ans = []
ls_ans.append( b[0][0] )

a = b[0][1]

for i in range(1,len(b)):
    if b[i][1]==a:
        ls_ans.append(b[i][0])
    else:
        break
ans = sorted(ls_ans)
print("\n".join(ans))
exit()
### BUGGY CODE ###

def main():
	n,m = map(int,input().split())
	a = list(map(int,input().split()))
	# print(a)
	maxl = [sum(a[0:m])]
	# print("maxl = {}".format(maxl))
	i = 1
	while i + m <= len(a):
		maxl.append(max(sum(a[i:i+m]),maxl[-1]))
		# print("sum = {}".format(sum(a[i:i+m])))
		# print("maxl = {}".format(maxl))
		i += 1
		# print(i)
	# print(maxl)
	ans = 0
	# print("a max is {}".format(a[maxl.index(max(maxl))]))
	for i in range(0,m):
		# print("i is {}".format(i))
		n = a[maxl.index(max(maxl)) + i]
		# print("n is {}".format(n))
		ans += (1/2 * n * (n+1))/a[maxl.index(max(maxl)) + i]
	print(ans)
	
 
if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	n,m = map(int,input().split())
	a = list(map(int,input().split()))
	wa = [0,(1/2 * a[0] * (a[0] +1))/a[0]]
	for i in range(1,n):
		wa.append(wa[i] + (1/2 * a[i] * (a[i]+1))/a[i])
	ans = wa[m-1]
	for i in range(m,len(wa)):
		ans = max(wa[i]-wa[i-m],ans)
	print(ans)
	
 
if __name__ == '__main__':
	main()
### BUGGY CODE ###

s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7
n = len(s)
count = 0
for i in range(n):
    #dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    # if s[i] == '?':
    #     dp2['A'] = dp1['A']*3 + (3**count)
    # elif s[i] == 'A':
    #     dp2['A'] = dp1['A'] + (3**count)
    # else:
    #     dp2['A'] = dp1['A']
    #
    # if s[i] == '?':
    #     dp2['AB'] = dp1['AB']*3 + dp1['A']
    # elif s[i] == 'B':
    #     dp2['AB'] = dp1['AB'] + dp1['A']
    # else:
    #     dp2['AB'] = dp1['AB']
    #
    # if s[i] == '?':
    #     dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    # elif s[i] == 'C':
    #     dp2['ABC'] = dp1['ABC'] + dp1['AB']
    # else:
    #     dp2['ABC'] = dp1['ABC']
    #
    # if s[i] == '?':
    #     count += 1

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + (3**count)
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + (3**count)
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    # for j in dp2.keys():
    #     dp2[j] = dp2[j] % c\
    # dp1 = dp2

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    #print(i, dp1)

print(dp1['ABC'])


### FIXED CODE ###

s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7
n = len(s)
tmp = [1]*n
for i in range(1, n):
    tmp[i] = (tmp[i-1] * 3)%c
#print(tmp)

count = 0
for i in range(n):
    #dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

    # if s[i] == '?':
    #     dp2['A'] = dp1['A']*3 + (3**count)
    # elif s[i] == 'A':
    #     dp2['A'] = dp1['A'] + (3**count)
    # else:
    #     dp2['A'] = dp1['A']
    #
    # if s[i] == '?':
    #     dp2['AB'] = dp1['AB']*3 + dp1['A']
    # elif s[i] == 'B':
    #     dp2['AB'] = dp1['AB'] + dp1['A']
    # else:
    #     dp2['AB'] = dp1['AB']
    #
    # if s[i] == '?':
    #     dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
    # elif s[i] == 'C':
    #     dp2['ABC'] = dp1['ABC'] + dp1['AB']
    # else:
    #     dp2['ABC'] = dp1['ABC']
    #
    # if s[i] == '?':
    #     count += 1

    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + tmp[count]
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + tmp[count]
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    # for j in dp2.keys():
    #     dp2[j] = dp2[j] % c\
    # dp1 = dp2

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    #print(i, dp1)

print(dp1['ABC'])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A = [0] + A  + [0]
cost = [abs(A[i+1] - A[i]) for i in range(N+1)]
for i in range(N):
  ans = sum(cost) - cost[i] - cost[i+1]
  ans += abs(A[i]-A[i+2])
  print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A = [0] + A  + [0]
cost = [abs(A[i+1] - A[i]) for i in range(N+1)]
cost_sum = sum(cost)
for i in range(N):
  ans = cost_sum - cost[i] - cost[i+1]
  ans += abs(A[i]-A[i+2])
  print(ans)
### BUGGY CODE ###

X = list(map(int, input().split()))
N = X[0]
K = X[1]
if N % K == 0:
  print(0)
else:
  while True:
    A = abs(N - K)
    if N > A:
      N = A
    else:
      break
  print(N)

### FIXED CODE ###

X = list(map(int, input().split()))
N = X[0]
K = X[1]
t = N % K
s = K - t
if t <= s:
  print(t)
else:
  print(s)