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

import sys
input=sys.stdin.readline
K = int(input())
def bunkai(N):
    k = 0
    while 10 ** k <= N:
        k += 1
    oldk = k
    order = [0] * k
    k -= 1
    while N > 0:
        a = N // (10**k)
        N = N % (10**k)
        order[oldk-k-1] = a
        k -= 1
    return order
c = 0
ans = []
for i in range(1,3234566668):
    arr = bunkai(i)
    n = len(arr)
    if n == 1:
        c += 1
        ans.append(arr)
    else:
        if arr[:n-1] in ans:
            if abs(arr[n-2] - arr[n-1]) <= 1:
                c += 1
                ans.append(arr)
    if c == K:
        print(i)
        break

### FIXED CODE ###

import sys
input=sys.stdin.readline
K = int(input())
LEN = 32345666
#S = input()[:-1]
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = list(map(int,input().split()))
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
def enqueue(Q,x,tail):#末尾にクラスPの要素xを加える。ぐるっと回った場合
    Q[tail] = x       #以前dequeueで取り出したものが書き換えられる。
    if tail+1 == LEN: #headは先頭のindex,tailは末尾のindex+1
        tail = 0
    else:
        tail += 1
    return tail
def dequeue(Q,head):
    x = Q[head]
    if head+1 == LEN:
        head = 0
    else:
        head += 1
    return x,head
Q = [1,2,3,4,5,6,7,8,9]+[0]*(LEN-9)
head = 0
tail = 9

i = 0
while i < K:
    x,head = dequeue(Q,head)
    if x % 10 == 0:
        tail = enqueue(Q,10*x,tail)
        tail = enqueue(Q,10*x+1,tail)
    elif x % 10 == 9:
        tail = enqueue(Q,10*x+8,tail)
        tail = enqueue(Q,10*x+9,tail)
    else:
        y = x%10
        tail = enqueue(Q,10*x+y-1,tail)
        tail = enqueue(Q,10*x+y,tail)
        tail = enqueue(Q,10*x+y+1,tail)
    i += 1
print(x)
### BUGGY CODE ###

import math

N = int(input())
for i in range(1,N+1):
  ans = 0
  for x in range(1,int(math.sqrt(i))):
    for y in range(x,int(math.sqrt(i))):
      for z in range(y,int(math.sqrt(i))):
        if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
          if x == y == z:
            ans += 1
          elif x == y | x == z | y == z:
            ans += 2
          else:
            ans += 3
  print(ans)


### FIXED CODE ###

import math

N = int(input())
ans = [0 for _ in range(10050)]

# for i in range(1,N+1):
for x in range(1,math.ceil(math.sqrt(N))):
  for y in range(1,math.ceil(math.sqrt(N))):
    for z in range(1,math.ceil(math.sqrt(N))):
      v = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if v < 10050:
        ans[v] += 1

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

s = input()
q = int(input())
cnt = 0
pre = ''
end = ''
for i in range(q):
    t, *fc = input().split()
    if t == '1':
        cnt^=1
    else:
        f, c = fc
        f = int(f)%2
        if f^cnt:
            pre+=c
        else:
            end+=c
ans = pre[::-1]+s+end
print
if cnt:
    ans = ans[::-1]
print(ans)



### FIXED CODE ###

s = list(input())
q = int(input())
cnt = 0
pre = []
end = []
for i in range(q):
    t, *fc = input().split()
    if t == '1':
        cnt^=1
    else:
        f, c = fc
        f = int(f)%2
        if f^cnt:
            pre.append(c)
        else:
            end.append(c)
ans = list(reversed(pre))+s+end
print
if cnt:
    ans = reversed(ans)
print(*ans, sep = '')
### BUGGY CODE ###

n=int(input())
mod=998244353

ans=pow(3,n,mod)
rmv=0
f = [1, 1]  
inv = [1, 1]  
finv=[1,1]
for i in range(2, n+1):
    f.append((f[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    finv.append(finv[-1]*inv[-1]%mod)

k=n//2
if k*2<=n:
    k+=1
tmp=pow(2,n-k+1,mod)
inv2=pow(2,mod-2,mod)
for i in range(k,n+1):
    ans -= f[n]*finv[n-i]*finv[i]*tmp
    tmp*=inv2
    tmp%=mod
print(ans%mod)
    



### FIXED CODE ###

n=int(input())
mod=998244353

ans=pow(3,n,mod)
rmv=0
f = [1, 1]  
inv = [1, 1]  
finv=[1,1]
for i in range(2, n+1):
    f.append((f[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    finv.append(finv[-1]*inv[-1]%mod)

k=n//2
if k*2<=n:
    k+=1
tmp=pow(2,n-k+1,mod)
inv2=pow(2,mod-2,mod)
for i in range(k,n+1):
    ans -= f[n]*finv[n-i]*finv[i]*tmp
    tmp*=inv2
    tmp%=mod
print(ans%mod)
### BUGGY CODE ###

import copy

N, K = map(int, input().split())
V = [int(i) for i in input().split()]

value = 0
# k+1個取って，ret-1個戻す
for k in reversed(range(K)):
    for ret in range(K-k): #戻す個数はret個
        if (ret < k+1) and ((k+1+ret)<=K):
            for i in range(k+1+1): # 左右の分け方
                tmp = []
                V_tmp = copy.copy(V)
                for sp in range(i): # 左端iつ取る
                    if V_tmp == []:
                        break
                    tmp.append(V_tmp.pop(0))
                for sp in range(k+1-i): # 右端k+1-iつ取る
                    if V_tmp == []:
                        break
                    tmp.append(V_tmp.pop(-1))
                tmp = list(filter(lambda x: x not in sorted(tmp)[:ret],tmp))
                value = max(value,sum(tmp))

print(value)

### FIXED CODE ###

import copy

N, K = map(int, input().split())
V = [int(i) for i in input().split()]

result = 0
# i個取る
for i in range(min(N,K)+1):
    #print('i:',i)
    for sp in range(i+1): # 左右の分け方
        #print('right',sp)
        #print('left',i-sp)
        tmp = []
        V_tmp = copy.copy(V)
        #print('元々：',V_tmp)
        tmp.extend(V_tmp[:sp]) # 左端追加
        #print('left',V_tmp[:sp])
        tmp.extend(V_tmp[N-(i-sp):]) #右端追加
        #print('right',V_tmp[N-(i-sp):])
        #print(tmp)
        tmp = sorted(tmp)
        value = sum(tmp)
        # ret個戻す
        for ret in range(0, min(K-i,i)): #残り操作回数か取った石の個数iの小さい方
            if ret < i:
                # マイナスの価値は戻す
                if tmp[ret] < 0:
                    value -= tmp[ret]
                    #print('捨てた宝石：',tmp[ret])
            else:
                break
        result = max(result,value)
            #print()

print(result)
### BUGGY CODE ###

from bisect import bisect_left
from bisect import bisect_right
N = int(input())
A = sorted(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()))
r = 0
for i in range(N):
  ai = bisect_left(A, B[i])
  ci = bisect_right(C, B[i])
  r += len(A[:ai]) * len(C[ci:])
print(r)

### FIXED CODE ###

from bisect import bisect_left
from bisect import bisect_right
N = int(input())
A = sorted(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()))
r = 0
for i in range(N):
  ai = bisect_left(A, B[i])
  ci = bisect_right(C, B[i])
  r += ai * (N - ci)
print(r)
### BUGGY CODE ###

N, Q = [int(i) for i in input().strip().split()]
S = input().strip()

pre = ''
hit = []
for i, s in enumerate(S):
  if pre=='A' and s=='C':
    hit.append(i)
  pre = s
  
for _ in range(Q):
  l, r = [int(i) for i in input().strip().split()]
  print(sum([1 for h in hit if l<=h<r]))
  


### FIXED CODE ###

N, Q = [int(i) for i in input().strip().split()]
S = input().strip()

hit = [0]*(N+1)
for i in range(N):
  hit[i+1] = hit[i] + (1 if S[i:i+2]=='AC' else 0)
  
for _ in range(Q):
  l, r = [int(i) for i in input().strip().split()]
  print(hit[r-1]-hit[l-1])
### BUGGY CODE ###

import math
H = int(input())

cnt = 0

ans = 1
while True:
    H = math.floor(H/2)
    cnt += 1
    ans *= 2
    if H ==1:
        break
cnt += 1
ans *= 2

print(ans-1)



### FIXED CODE ###


H = int(input())


def iterated_power(z: int, n: int, mod=None) -> int:
    """ 繰り返し二乗法でn**kを求める（再帰処理は使わない）
    >>> p = Prime()
    >>> p.iterated_power(3, 10)
    59049
    >>> p.iterated_power(3, 10, 10)
    9
    """
    beta = bin(n)[2:]

    Z, q, t = z, 0, len(beta)
    while beta[t - q - 1] == '0':
        Z = Z * Z
        if mod is not None:
            Z = Z % mod
        q += 1
    result = Z

    for k in range(q + 1, t):
        Z = Z * Z
        if mod is not None:
            Z = Z % mod
        if beta[t - k - 1] == '1':
            result = result * Z
            if mod is not None:
                result = result % mod

    if mod is not None:
        result = result % mod

    return result


ans = iterated_power(2, H.bit_length()) - 1
print(ans)
### BUGGY CODE ###

MOD = 10**9 + 7
MAX = 7 * 10**5
fact = [1 for _ in range(MAX)]
finv = [1 for _ in range(MAX)]
for i in range(2, MAX):
    fact[i] = fact[i - 1] * i % MOD
    finv[i] = pow(fact[i], MOD - 2, MOD)


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    print(a, b)
    ans = comb(a + b, a)

print(ans)


### FIXED CODE ###

MOD = 10**9 + 7


def comb(n, k):
    if k > n - k:
        k = n - k
    ans = 1
    for i in range(1, k + 1):
        ans *= n + 1 - i
        ans *= pow(i, MOD - 2, MOD)
        ans %= MOD
    return ans


x, y = map(int, input().split())
a = 2 * y - x
b = 2 * x - y

if a < 0 or b < 0:
    ans = 0
elif a % 3 != 0 or b % 3 != 0:
    ans = 0
else:
    a //= 3
    b //= 3
    # print(a, b)
    ans = comb(a + b, a)

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

N = int(input())
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

INF = float('inf')
dp = [0]
for i, (H, P) in enumerate(HPs, 1):
    if dp[-1] != INF:
        dp += [INF]

    for j in range(1, len(dp))[::-1]:
        hgt = dp[j - 1]
        if hgt <= H:
            dp[j] = min(dp[j], hgt + P)

dp += [INF]
print(dp.index(INF) - 1)


### FIXED CODE ###

N = int(input())
HPs = [tuple(map(int, input().split())) for i in range(N)]

HPs.sort(key=lambda x: x[0] + x[1])

INF = float('inf')
dp = [0]
for i, (H, P) in enumerate(HPs, 1):
    if dp[-1] != INF:
        dp += [INF]

    for j in range(1, len(dp))[::-1]:
        hgt = dp[j - 1]
        if hgt <= H:
            dp[j] = min(dp[j], hgt + P)

dp += [INF]
print(dp.index(INF) - 1)
### BUGGY CODE ###

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

parent = [None] * N
parent[0] = 0

import sys
sys.setrecursionlimit(200002)

def dfs(src):
    for dst in graph[src]:
        if parent[dst] != None: continue
        parent[dst] = src
        dfs(dst)

dfs(0)
# print("#", parent)

score = [0] * N
for pi, xi in px:
    score[pi - 1] += xi
        
memo = [None] * N
def dp(arg):
    if memo[arg] != None: return memo[arg]
    #
    ret = score[arg]
    if arg != parent[arg]: ret += dp(parent[arg])
    memo[arg] = ret
    return ret

ans = []
for i in range(N):
    ans.append(dp(i))

# print("#", memo)

print(' '.join(map(str, ans)))

### FIXED CODE ###

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

parent = [None] * N
parent[0] = 0

score = [0] * N
for pi, xi in px:
    score[pi - 1] += xi

ans = [None] * N

from collections import deque

q = deque([(0, 0)])
while len(q) > 0:
    src, score_tmp = q.popleft()
    score_tmp += score[src]
    ans[src] = score_tmp
    for dst in graph[src]:
        if ans[dst] != None: continue
        q.append((dst, score_tmp))

print(' '.join(map(str, ans)))
### BUGGY CODE ###

X,K,D=map(int,input().split())
now=X
for i in range(K):
    X_plus=now+D
    X_mi=now-D
    if abs(X_plus)<abs(X_mi):
        now=X_plus
    else :
        now=X_mi

print(abs(now))
    

### FIXED CODE ###

X,K,D=map(int,input().split())
X=abs(X)
y=X//D
if K<y:
    y=K
X=X-(D*y)
K=K-y

if K%2==1:
    X=abs(X-D)
    
print(X)
### BUGGY CODE ###

sn, tn, qn = map(int, input().split())

sa = []
ta = []
qa = []
for i in range(sn):
    sa.append(int(input()))
for i in range(tn):
    ta.append(int(input()))
for i in range(qn):
    qa.append(int(input()))


def move_cost(q, al, bl):
    md = abs(q - al[0])
    mx = al[0]
    for a in al:
        d = abs(q - a)
        if d < md:
            md = d
            mx = a
    x1 = min(q, mx)
    x2 = max(q, mx)

    md2 = abs(mx - bl[0])
    mx2 = bl[0]
    for b in bl:
        if b >= x1 and b <= x2:
            return abs(q - mx)
        d = abs(mx - b)
        if d < md2:
            md2 = d
            mx2 = b
    return abs(q - mx) + abs(mx2 - mx)

for q in qa:
    a1 = move_cost(q, sa, ta)
    a2 = move_cost(q, ta, sa)
    print(min(a1, a2))


### FIXED CODE ###

import bisect
sn, tn, qn = map(int, input().split())

LARGE = -100000000
sa = []
ta = []
qa = []
for i in range(sn):
    sa.append(int(input()))
for i in range(tn):
    ta.append(int(input()))
for i in range(qn):
    qa.append(int(input()))

def find_nearest(q, al, s, e):
    idx = bisect.bisect_right(al, q)
    if idx == 0:
        return [al[0], al[0]]
    if idx == len(al):
        return [al[idx - 1], al[idx - 1]]
    return [al[idx - 1], al[idx]]

def move_cost(q, al, bl):
    a1, a2 = find_nearest(q, al, 0, len(al) - 1)
    b1, b2 = find_nearest(q, bl, 0, len(bl) - 1)

    def calc(x1, x2, x3):
        y1 = min(x1, x2)
        y2 = max(x1, x2)
        if x3 >= y1 and x3 <= y2:
            return abs(x1 - x2)
        return abs(x1 - x2) + abs(x2 - x3)
    return min(
        calc(q, a1, b1),
        calc(q, a1, b2),
        calc(q, a2, b1),
        calc(q, a2, b2),
        calc(q, b1, a1),
        calc(q, b1, a2),
        calc(q, b2, a1),
        calc(q, b2, a2),
    )

for q in qa:
    print(move_cost(q, sa, ta))
### BUGGY CODE ###

n,m=map(int, input().split())
a=1
b=0
while b==0:
    for i in range(m,1,-1):
        if m%i==0 and m>=(i*n):
            a*=i
            m=m//i
            break
    else:b=1
print(a)

### FIXED CODE ###

n,m=map(int, input().split())
a=1
b=0
while b==0:
    for i in range(int(m**0.5)*10,1,-1):
        if m%i==0 and m>=(i*n):
            a*=i
            m=m//i
            break
    else:b=1
print(a)
### BUGGY CODE ###

#input
N, P = map(int, input().split())
S = list(map(int, input()))

# process
ans = 0
if P == 2 or P == 5:
    # 1桁目がPで割り切れる数をカウント
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1

else:
    cnt = [0]*P # S[i:N]%Pの結果をカウント
    num = 0
    tenPow = 1
    for i in range(N):
        num = (num + S[N-i-1]*tenPow)%P
        tenPow *= 10%P
        cnt[num] += 1

    ans += cnt[0]
    for c in cnt:
        ans += c*(c-1)//2 # c=0,1のときは0加算

# output
print(ans)


### FIXED CODE ###

#input
N, P = map(int, input().split())
S = input()

# process
ans = 0
if P == 2 or P == 5:
    # 1桁目がPで割り切れる数をカウント
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i+1

else:
    cnt = [0]*P # S[i:N]%Pの結果をカウント
    num = 0
    tenPow = 1
    for i in reversed(range(N)):
        num = (num + int(S[i])*tenPow)%P
        tenPow = tenPow*10%P
        cnt[num] += 1

    ans += cnt[0]
    for c in cnt:
        ans += c*(c-1)//2 # c=0,1のときは0加算

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

import itertools
import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    _ = int(input())
    hoge = tuple(map(int, input().split()))
    sumn = 0
    mod = 10 ** 9 + 7
    for pair in itertools.combinations(hoge, 2):
        sumn += (pair[0] * pair[1])
        sumn %= mod
    print(sumn)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    _ = int(input())
    nums = tuple(map(int, input().split()))
    mod = 10 ** 9 + 7

    num_sum = sum(nums)
    part_sum = sum(map(lambda x: x**2, nums)) # naname

    print((num_sum**2 - part_sum) // 2 % mod)


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

A, B = [int(x) for x in input().split(" ")]

out = "IMPOSSIBLE"

for k in range(0,10**9):
  if abs(A-k) == abs(B-k):
    out = k

print(out)


### FIXED CODE ###

A, B = [int(x) for x in input().split(" ")]

if (A+B)%2 == 0:
  print(int((A+B)/2))
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

S_list = list(input())
n = len(S_list)

result_list = []
total_sum = 0
for i in range(2 ** n):
    # pの位置を決める
    ans_str = ['g']*n
    result = 0
    for j in range(n):
        if ((i >> j) & 1 &(ans_str[:j].count('p')<ans_str[:j].count('g'))):
            ans_str[j]= 'p'
            if S_list[j] == 'g':
                result+=1
        else:
            if S_list[j] == 'p':
                result-=1
    result_list.append(result)

print(max(result_list))

### FIXED CODE ###

gp = input()
p = gp.count('p')
g = gp.count('g')

print((g-p)//2)
### BUGGY CODE ###

def main():
    # n:人数, a:身長リスト
    n = int(input())
    a = list(map(int, input().split()))
    # Li=i+Ai, Ri=i-Aiを満たすL,Rを作成
    L = [(i+a[i]) for i in range(n)]
    R = [(i-a[i]) for i in range(n)]
    # Li=X=Rj,i<jを満たす組が存在する時count+=1
    count = 0
    for i,Li in enumerate(L):
        if (Li in R):
            j_list = [idx for idx,x in enumerate(R) if x == Li]
            for j in j_list:
                 if i<j: count+=1
    print(count)

main()


### FIXED CODE ###

from collections import Counter

def main():
    # n:人数, a:身長リスト
    n = int(input())
    a = list(map(int, input().split()))
    # Li=i+Ai, Ri=i-Aiを満たすL,Rを作成
    L = [0]*n
    R = [0]*n
    for i,ai in enumerate(a):
        L[i] = i+ai
        R[i] = i-ai
    # Li=X=Rj,i<jを満たす組が存在する時count+=1
    count = 0
    c = Counter(R)
    for Li in L:
        count += c.get(Li,0)

    print(count)

main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
if len(set(a))==1:
  print(n//2)
else:
  x=[]
  y=[]
  cnt=0
  for i in a:
    if cnt%2==0:
      x.append(i)
      cnt+=1
    else:
      y.append(i)
      cnt+=1
  s=list(set(x))
  t=list(set(y))
  o=0
  p=0
  for i in s:
    o=max(o,x.count(i))
  for i in t:
    p=max(p,y.count(i))
  print(n-o-p)


### FIXED CODE ###

from collections import Counter

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

if a.count(a[0])==n:
    print(n//2)
    exit()


x=a[::2]
y=a[1::2]

xx=Counter(x)
yy=Counter(y)

xxx=xx.most_common()
yyy=yy.most_common()

if xxx[0][0]!=yyy[0][0]:
    print(n-xxx[0][1]-yyy[0][1])

else:
    print(min(n-xxx[1][1]-yyy[0][1],n-xxx[0][1]-yyy[1][1]))
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
A = list(map(int , input().split()))
B = list(map(int , input().split()))
C = list(map(int , input().split()))
A = sorted(A,reverse = True)
B = sorted(B,reverse = True)
C = sorted(C,reverse = True)
AB = []
ABC = []
for i in A:
        for j in B:
                AB.append(i+j)
AB.sort(reverse = True)
AB = AB[:k]
for i in AB:
        for j in C:
                ABC.append(i+j)
ABC.sort(reverse = True)
for i in range(k):
        print(ABC[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
for i in range(1,n+1):
    print(l.index(i)+1,end=' ')

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
t=[0]*n
i=1
for e in l:
    t[e-1]=str(i)
    i+=1
print(' '.join(t))
### BUGGY CODE ###

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

### FIXED CODE ###

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

def near(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x
    elif i == len(Y):
        return x-Y[i-1]
    else:
        return min(Y[i]-x, x-Y[i-1])

def near2(x, D):
    Y = [d for d ,_ in D]
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x + D[i][1]
    elif i == len(Y):
        return x-Y[i-1] + D[i-1][1]
    else:
        return min(Y[i]-x+D[i][1], x-Y[i-1]+D[i-1][1])

from bisect import *
A, B, Q = map(int, input().split())
S = []
T = []
for _ in range(A):
    S.append(int(input()))
for _ in range(B):
    T.append(int(input()))
D = []
for a in S:
    D.append((a, near(a, T)))
for b in T:
    D.append((b, near(b, S)))
D.sort(key=lambda x:x[0])
for _ in range(Q):
    x = int(input())
    print(near2(x,D))



### FIXED CODE ###

def near(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x
    elif i == len(Y):
        return x-Y[i-1]
    else:
        return min(Y[i]-x, x-Y[i-1])

def near2(x, Y):
    i = bisect_left(Y,x)
    if i == 0:
        return Y[i]-x + D[i][1]
    elif i == len(Y):
        return x-Y[i-1] + D[i-1][1]
    else:
        return min(Y[i]-x+D[i][1], x-Y[i-1]+D[i-1][1])

from bisect import *
A, B, Q = map(int, input().split())
S = []
T = []
for _ in range(A):
    S.append(int(input()))
for _ in range(B):
    T.append(int(input()))
D = []
for a in S:
    D.append((a, near(a, T)))
for b in T:
    D.append((b, near(b, S)))
D.sort(key=lambda x:x[0])
D2 = [d for d, _ in D]
for _ in range(Q):
    x = int(input())
    print(near2(x,D2))
### BUGGY CODE ###

import collections
n = int(input())
a = list(map(str,input().split()))

c = collections.Counter(a)

keys, values = zip(*c.most_common())

ans = 0
co = 0
for i in values:
  if i != 1:
  	ans += (i*(i-1)//2)

for i in a:
    for j in range(len(keys)-1,-1,-1):
      if i == keys[j]:
        co = values[j]
        break
    print(ans-(co*(co-1)//2)+((co-1)*(co-2)//2))

      

### FIXED CODE ###

import collections
n = int(input())
a = list(map(str,input().split()))
ls = [i for i in range(2*10**5)]
c = collections.Counter(a)
comon = c.most_common()
ans = 0

for i in comon:
    if i != 1:
      ls[int(i[0])] = i[1]
      ans += (i[1]*(i[1]-1)//2)

for i in a:
    co = ls[int(i)]
    print(ans-(co*(co-1)//2)+((co-1)*(co-2)//2))
### BUGGY CODE ###

import numpy as np

K = int(input())
result = 0

for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      result += np.gcd.reduce([a, b, c])

print(result)

### FIXED CODE ###

import math

K = int(input())
result = 0

for a in range(1, K+1):
  for b in range(1, K+1):
    temp = math.gcd(a, b)
    for c in range(1, K+1):
      result += math.gcd(temp, c)

print(result)
### BUGGY CODE ###

def gcd(a,b):
    if(a%b==0):
        return b
    else:
        return gcd(b,a%b)

sum = 0
k = int(input())
for i in range(1,k+1):
    for j in range(1,k+1):
        val = gcd(i,j)
        for l in range(1,k+1):
            sum = sum + gcd(val,l)

print(sum)

### FIXED CODE ###

def gcd(a,b):
    if(a%b==0):
        return b
    else:
        return gcd(b,a%b)
 
k = int(input())
val = [[0]*(k+1) for i in range(k+1)]
sum = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        if(val[i][j] == 0):
            val[i][j] = gcd(i,j)
        for l in range(1,k+1):
            if(val[val[i][j]][l] == 0):
                val[val[i][j]][l] = gcd(val[i][j],l)
            sum = sum + val[val[i][j]][l]
 
print(sum)