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

N, K = [int(x) for x in input().split(" ")]

if K == 1:
  print(0)
else:
  while N>abs(N-K):
    N = abs(N%K-K)
  print(N)


### FIXED CODE ###

N, K = [int(x) for x in input().split(" ")]

if N ==0 or K==1 or N == K:
  print(0)
else:
  while N>abs(N-K):
    N = abs(N%K-K)
  print(N)
### BUGGY CODE ###

def calc_destination(start, edges, N):
    destination = [-1] * (N + 1)
    destination[start] = 0
    q = [start]
    while len(q) != 0:
        current = q.pop(0)
        for n in edges[current]:
            if destination[n] != -1:
                continue
            destination[n] = destination[current] + 1
            q.append(n)
    return destination

def main():
    N, u, v = map(int, input().split())

    if u == v:
        print(0)
        return

    edges = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        A, B = map(int, input().split())
        edges[A].append(B)
        edges[B].append(A)

    tak = calc_destination(u, edges, N)
    aok = calc_destination(v, edges, N)

    result = 0
    for i in range(1, N + 1):
        aoki = aok[i]
        if tak[i] >= aoki:
            continue
        if aoki > result:
            result = aoki
    print(result - 1)

main()


### FIXED CODE ###

def calc_destination(start, edges, N):
    destination = [-1] * (N + 1)
    destination[start] = 0
    q = [start]
    while len(q) != 0:
        current = q.pop()
        for n in edges[current]:
            if destination[n] != -1:
                continue
            destination[n] = destination[current] + 1
            q.append(n)
    return destination

def main():
    N, u, v = map(int, input().split())

    if u == v:
        print(0)
        return

    edges = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        A, B = map(int, input().split())
        edges[A].append(B)
        edges[B].append(A)

    tak = calc_destination(u, edges, N)
    aok = calc_destination(v, edges, N)

    result = 0
    for i in range(1, N + 1):
        aoki = aok[i]
        if tak[i] >= aoki:
            continue
        if aoki > result:
            result = aoki
    print(result - 1)

main()
### BUGGY CODE ###

n, m = list(map(int, input().split()))
for x in range(m//n+1)[::-1]:
  if m%x==0:
    break
print(x)

### FIXED CODE ###

N, M = list(map(int, input().split(" ")))
def solv(N, M):
    d = M//N
    for i in range(d+1)[::-1]:
        if M%i == 0:
            return i
print(solv(N, M))
### BUGGY CODE ###

import math
N = int(input())
def f(n):
    count=0
    for x in range(1,int(math.sqrt(n))):
        for y in range(1,x+1):
            for z in range(1,y+1):
                if x*x+y*y+z*z+x*y+y*z+z*x==n:
                    if x==y and y==z:
                        count+=1
                    elif (x==y and x!=z) or (y==z and y!=x):
                        count+=3
                    else:
                        count+=6
    print(count)

for i in range(1,N+1):
    f(i)

### FIXED CODE ###

a=[0]*int(input())
r=range(1,99)
for x in r:
    for y in r:
        for z in r:
            n=x*(x+y+z)+y*(y+z)+z*z-1
            if n<len(a):
                a[n]+=1
print(*a)
### BUGGY CODE ###

N = int(input())
X = str(input())
X_list = list(X)
X_list = list(map(int, X_list))

X10 = int(X,2)
one_num = sum(X_list)
#%%
for i in range(N):
    target = X_list[i]
    if target == 0:
        plus = pow(2,N-i-1)
        ones = one_num + 1
    else:
        plus = -pow(2,N-i-1)
        ones = one_num-1
    
    Xnow = X10+plus
    count = 0
    if Xnow == 0:
        print(count)
        continue
    else:
        Xnow = Xnow%ones
        count+=1
        while Xnow > 0:
            Xnow2list = list(map(int,list(format(Xnow, 'b'))))
            ones = sum(Xnow2list)
            Xnow = Xnow%ones
            count+=1
        print(count)

### FIXED CODE ###

N = int(input())
x2 = input()
x10 = int(x2, 2)
popc =  x2.count("1")
#print("x10", x10)
#print("popc", popc)
#popc: Nを2進数で表したときの1の個数

#以下で1つフリップさせた時の入力に対する余りを事前に計算
if popc <= 1:
    xp = x10%(popc+1)
    xm = 0
else:
    xp = x10%(popc+1)
    xm = x10%(popc-1)
#print("xp", xp)
#print("xm", xm)

#以下でフリップさせた場所のみを計算
for i in range(N):
    if x2[i] == "1":
        if popc == 1:
            print(0)
            continue
        tmp = (xm - pow(2, N-i-1, popc-1))%(popc-1)
    else:
        tmp = (xp + pow(2, N-i-1, popc+1))%(popc+1)
        
    #print("tmp", tmp)
    ans = 1
    while tmp > 0:
        tmp %= bin(tmp).count("1")
        ans += 1
    print(ans)
### BUGGY CODE ###

K = int(input())

if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()
now = 0
count = 0
while True:
    now = now * 10 + 7
    count += 1
    if now % K == 0:
        print(count)
        exit()


### FIXED CODE ###

K = int(input())

if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()
now = 0
count = 0
while True:
    now = (now * 10 + 7) % K
    count += 1
    if now % K == 0:
        print(count)
        exit()
### BUGGY CODE ###

def main():
    s = list(reversed(input()))
    mod = 10**9+7
    memo = [0 for _ in [0]*13]
    m13 = [(10**i) % 13 for i in range(12)]
    memo[0] = 1
    for i in range(len(s)):
        memo2 = [0 for _ in [0]*13]
        a = m13[i % 12]
        if s[i] == "?":
            list_ = [(a*j) % 13 for j in range(10)]
            for l in list_:
                for j in range(13):
                    memo2[(l+j) % 13] += memo[j]
        else:
            l = a*int(s[i])
            for j in range(13):
                memo2[(l+j) % 13] += memo[j]
        memo = [j % mod for j in memo2]
    print(memo[5])


main()


### FIXED CODE ###

s=list(reversed(input()))
mod=10**9+7
memo=[0 for _ in [0]*13]
m13=[(10**i)%13 for i in range(12)]
memo[0]=1
for i in range(len(s)):
    memo2=[0 for _ in [0]*13]
    a=m13[i%12]
    if s[i]=="?":
        list_=[0,1,2,3,4,5,6,7,8,9]
    else:
        list_=[int(s[i])]
    list_=[(a*j)%13 for j in list_]
    for l in list_:
        for j in range(13):
            memo2[(l+j)%13]+=memo[j]
    memo=[j%mod for j in memo2]
print(memo[5])
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    query = [_ for _ in input().split()]
    if len(query) == 1:
        S = S[::-1]
    else:
        if query[1] == '1':
            S = query[2] + S
        else:
            S = S + query[2]
print(S)


### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
rev_cnt = 0
for i in range(Q):
    query = [_ for _ in input().split()]
    if len(query) == 1:
        rev_cnt += 1
    else:
        if query[1] == '1':
            if rev_cnt%2 == 0:
                S.appendleft(query[2])
            else:
                S.append(query[2])
        else:
            if rev_cnt%2 == 0:
                S.append(query[2])
            else:
                S.appendleft(query[2])
if rev_cnt % 2 == 0:
    print(''.join(S))
else:
    S.reverse()
    print(''.join(S))
### BUGGY CODE ###

n = int(input())
l = []
ans = 0

for i in range(n):
    s = input()
    l.append(sorted(s))
    
for i in range(n-1):
    for j in range(i+1,n):
        if l[i] == l[j]:
            ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
d = {}
ans = 0

for i in range(n):
    s = "".join(sorted(input()))
    if s not in d:
        d[s] = 1
    else:
        ans += d[s]
        d[s] += 1
    
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]

h.sort()

DEF_MIN = max(h)-min(h)

for i in range(n-k+1):
    tmp = max(h[i:i+k])-min(h[i:i+k])
    DEF_MIN = min(DEF_MIN, tmp)

print(DEF_MIN)

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]

h.sort()

DEF_MIN = max(h)-min(h)

for i in range(n-k+1):
    tmp = h[i+k-1]-h[i]
    DEF_MIN = min(DEF_MIN, tmp)

print(DEF_MIN)
### BUGGY CODE ###

import numpy as np

ABN=np.array(input().split(" "),dtype=np.int64)
A=ABN[0]
B=ABN[1]
N=ABN[2]

out=0
for x in range(1,N+1):
    calc=int(A*x/B)-A*int(x/B)
    if(calc>out):
        out=calc

print(out)

### FIXED CODE ###

import numpy as np

ABN=np.array(input().split(" "),dtype=np.int64)
A=ABN[0]
B=ABN[1]
N=ABN[2]

x=min(B-1,N)
calc=int(A*x/B)-A*int(x/B)

print(calc)
### BUGGY CODE ###

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

c = []
for i in range(N - K + 1):
    p = x[i:i+K]
    lr = abs(p[0]) + abs(p[-1] - p[0])
    rl = abs(p[-1]) + abs(p[0] - p[-1])
    if lr < rl:
        c.append(lr)
    else:
        c.append(rl)
print(min(c))


### FIXED CODE ###

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

ans = 10**18
for i in range(N - K + 1):
    p1 = x[i]
    p2 = x[i+K-1]
    lr = abs(p1) + abs(p2 - p1)
    rl = abs(p2) + abs(p1 - p2)
    if lr < rl:
        ans = min(ans,lr)
    else:
        ans = min(ans,rl)
print(ans)
### BUGGY CODE ###

from scipy.special import comb

INF = 100100100

N = int(input())
A = list(map(int, input().split()))
sorted_A = sorted(A)
countNums = [0]*(N+1)

target = sorted_A[0]
for i in range(N):
    if target==sorted_A[i]:
        countNums[target] += 1
    else:
        target = sorted_A[i]
        countNums[target] += 1;


for i in range(N):
    a = A[i]
    countNums[a] -= 1
    ans = 0
    for c in countNums:
        ans += int(comb(c, 2))
    print(ans)
    countNums[a] += 1




### FIXED CODE ###

from copy import deepcopy

def count(A):
    cnt = 0
    for a in A:
        cnt += (a*(a-1))//2
    return cnt


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    max_A = max(A)

    count_A = [0]*(max_A+1)

    for a in A:
        count_A[a]+= 1

    combi_A = 0

    for c in count_A:
        combi_A += (c*(c-1))//2
    for a in A:
        print(combi_A-(count_A[a]*(count_A[a]-1)-(count_A[a]-1)*(count_A[a]-2))//2)
### BUGGY CODE ###

L = input()
length = len(L)
ans = 3 ** (length - 1)
a = 3 ** (length-1)
for q in range(1,length):
	if L[q]  == '1':
		a = a // 3 *2
		ans += a%1000000007
	else:
		a //= 3
print((ans + a * 2)%1000000007)

### FIXED CODE ###

L = input()
length = len(L)
a = 2
b = 1
c = 4
for l in L[1:]:
	if l  == '1':
		a = (a * 3) % 1000000007
		b = (b * 3) % 1000000007
		c = (c * 2) % 1000000007
	else:
		a = (a * 3 - c) % 1000000007
		b = (b * 3) % 1000000007
print((a + b)%1000000007)
### 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()))

from itertools import product
D=sorted([a+b for a,b in product(A,B)],reverse=True)
D=D[:K]
E=sorted([d+c for d,c in product(D,C)],reverse=True)
E=E[:K]
for i in range(K):
    print(E[i])


### FIXED 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.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
C=C[:K]

from itertools import product
D=sorted([a+b for a,b in product(A,B)],reverse=True)
D=D[:K]
E=sorted([d+c for d,c in product(D,C)],reverse=True)
E=E[:K]
for i in range(K):
    print(E[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())

d = [[float('inf')]*n for i in range(n)]

for i in range(n):
    d[i] = list( map(int, input().split()))

for i in range(n):
    if d[i][i] != 0:
        print(-1)
        exit()

for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                print(-1)
                exit()

ans = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if i==k or k==j :continue
            if d[i][j] == d[i][k] + d[k][j]:
                break
        else:
            ans += d[i][j]

print(ans//2)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())

d = [[float('inf')]*n for i in range(n)]

for i in range(n):
    d[i] = list( map(int, input().split()))

for i in range(n):
    if d[i][i] != 0:
        print(-1)
        exit()

for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                print(-1)
                exit()

ans = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if i==k or k==j :continue
            if d[i][j] == d[i][k] + d[k][j]:
                break
        else:
            ans += d[i][j]

print(ans//2)
### BUGGY CODE ###

def binary(l,c):
    fst = 0
    last = len(l)
    mid = int(last/2)
    while fst < last:
        mid = int((fst+last) / 2)
        if last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if l[mid] < c:
        mid+=1
    l.insert(mid,c)

q = int(input())
S = []
a = []
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(q):
    if a[i][0] == 0:
        if not a[i][1] in S:
            if not S:
                S.append(a[i][1])
            else:
                binary(S,a[i][1])
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
    else:
        for b in range(len(S)):
            if S[b] >= a[i][1] and S[b] <= a[i][2]:
                print(S[b])



### FIXED CODE ###

from bisect import bisect_left, bisect_right, insort_left

q = int(input())
S = []
D = {}
a = []
c = 0
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(q):
    if a[i][0] == 0:
        if not a[i][1] in D:
            insort_left(S,a[i][1])
            D[a[i][1]] = 1
            c += 1
        else:
            if not D[a[i][1]] == 1:
                D[a[i][1]] = 1
                c += 1
        print(c)
    elif a[i][0] == 1:
        if a[i][1] in D:
            if D[a[i][1]] == 1:
                print(1)
            else:
                print(0)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in D:
            if D[a[i][1]] == 1:
                D[a[i][1]] = 0
                c -= 1
    else:
        L = bisect_left(S,a[i][1])
        R = bisect_right(S,a[i][2])
        for j in range(L,R):
            if D[S[j]] == 1:
                print(S[j])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
N = int(input())
data = sorted([''.join(sorted(input().rstrip())) for n in range(N)])
count = 0
while data:
    number = data.count(data[0])
    if number > 1:
        count += number - 1
    del data[0]
    
print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N = int(input())
words = {}
while N > 0:
    word = ''.join(sorted(input().rstrip()))
    if word in words:
        words[word] += 1
    else:
        words[word] = 1
    N -= 1

count = 0
for n in words.values():
    if n > 1:
        count += n*(n-1) // 2

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

def dfs(n):
    global b,check,d
    #ttfは235、chaはabc
    #2,3,5の場合それぞれ
    for ttf,cha in zip([2,3,5],b):
        #-1ずつしていく場合
        if check[0]>check[n]+n*d:
            check[0]=check[n]+n*d

        #最寄りまで-してく場合
        x1,x2=n//ttf,n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

        #最寄りまで+1してく場合
        x1,x2=n//ttf+1,ttf-n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])


### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

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


for i in range(n):
    xi = x[:i]+x[i+1:]
    xi.sort()
    print(xi[n//2-1])


### FIXED CODE ###

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

sort_x = sorted(x)

for i in range(n):
    if x[i]<=sort_x[n//2-1]:
        print(sort_x[n//2])
    else:
        print(sort_x[n//2-1])
### BUGGY CODE ###

n, K = map(int, input().split())
f = list(map(int, input().split()))
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
    ways = []
    for k in range(1,K+1):
        if i - k >= 0:
            ways.append(dp[i - k] + abs(f[i] - f[i - k]))
    dp[i] = min(ways)
print(dp[n - 1])


### FIXED CODE ###

n, K = map(int, input().split())
f = list(map(int, input().split()))
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
    ways = []
    for k in range(1,K+1):
        if i - k >= 0:
            ways.append(dp[i - k] + abs(f[i] - f[i - k]))
    dp[i] = min(ways)
print(dp[n - 1])
### BUGGY CODE ###

N = int(input())
la = list(map(int, input().split()))
la.sort()
la.append(N+1)

for i in range(1, N+1):
    k = 0
    while la[k] == i and la[k] != N+1:
        k += 1
    print(k)
    del la[:k]


### FIXED CODE ###

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

la.append(N+1)

lb = [0] * N
for i in range(N-1):
    lb[la[i]-1] += 1

for j in range(N):
    print(lb[j])
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    a = [int(input()) for i in range(m)]

    mod = 1000000007
    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 in a:
        d[1] = 0
    else:
        d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
        else:
            d[i] = d[i-1] + d[i-2]
    # print(d)  
    ans = d[n] % mod        
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def main():
    # n, m = map(int, input().split())
    # a = [int(input()) for i in range(m)]
    n, m = map(int, readline().split())
    a = set(map(int, read().split()))
    mod = 1000000007

    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # 2回0が続く状況aに連番があったら即座に終了する
    cnt = 0 
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)

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

import random

D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for i in range(D)]


def calc(T):
  L = [0 for i in range(26)]
  score=0
  for d in range(D):
    score += S[d][T[d]-1]

    L[T[d]-1] = d+1
    down = 0
    for i in range(26):
      down+=C[i] * ((d+1) - L[i])

    score -=down
  return score

max_score=0
bestT=[]

for i in range(10000):
  T = [random.randrange(1,26) for i in range(D)] 
  score = calc(T)

  if score > max_score:
    bestT = T
    max_score = score

for t in T:
  print(t)

### FIXED CODE ###

import random

D = int(input())
C = list(map(int, input().split()))
S = [list(map(int, input().split())) for i in range(D)]


def calc(T):
  L = [0 for i in range(26)]
  score=0
  for d in range(D):
    score += S[d][T[d]-1]

    L[T[d]-1] = d+1
    down = 0
    for i in range(26):
      down+=C[i] * ((d+1) - L[i])

    score -=down
  return score

max_score=0
bestT=[]

for i in range(10):
  T = [random.randrange(1,26) for i in range(D)] 
  score = calc(T)

  if score > max_score:
    bestT = T
    max_score = score

for t in T:
  print(t)
### BUGGY CODE ###

import numpy as np
X, Y, Z, K, *L = map(int, open(0).read().split())
A = L[:X]
B = L[X:X+Y]
C = L[X+Y:]
ab = []
for i in range(X):
  for j in range(Y):
    ab += [A[i]+B[j]]
ab.sort()
ab = np.array(ab)
c = np.array(C)
l = -1
r = 3*10**10+1
M = X*Y*Z
for k in range(K):
  l = -1
  M = X*Y*Z
  while l+1<r:
    n = (l+r)//2
    d = n-c
    m = np.searchsorted(ab,d).sum()
    if M-m>k:
      l = n
    else:
      r = n
  print(l)
  r = l+1


### FIXED CODE ###

inf = input().split()
X = int(inf[0])
Y = int(inf[1])
Z = int(inf[2])
K = int(inf[3])

A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
ab = []
for a in A:
  for b in B:
    ab +=[a+b]
ab.sort(reverse=True)
C.sort(reverse=True)
state = [[ab[0]+C[i],0,i] for i in range(len(C))]
count  = 0
while count<K:
  s = max(state)
  print(s[0])
  count +=1
  x = s[1]
  i = s[2]
  if x<X*Y-1:
    state[i][0] = C[i]+ab[x+1]
    state[i][1] = x+1
  else:
    state[i][0] = -1
### BUGGY CODE ###

from collections import deque

s = deque(input())

ans = 0
while len(s) > 1:
    if s[0] == s[-1]:
        s.pop()
        s.popleft()
    elif s[0] == 'x':
        s.popleft()
        ans += 1
    elif s[-1] == 'x':
        s.pop()
        ans += 1
    elif s[0] != s[1]:
        print(-1)
        break
else:
    print(ans)


### FIXED CODE ###

from collections import deque

s = deque(input())

ans = 0
while len(s) > 1:
    if s[0] == s[-1]:
        s.pop()
        s.popleft()
    elif s[0] == 'x':
        s.popleft()
        ans += 1
    elif s[-1] == 'x':
        s.pop()
        ans += 1
    else:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

n,m,k = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]

f1 = [set() for _ in range(0, n+1)]
b1 = [set() for _ in range(0, n+1)]
fb1 = [set() for _ in range(0, n+1)]
ans = [0]*(n+1)

for x,y in ab:
    f1[x].add(y)
    f1[y].add(x)
    fb1[x].add(y)
    fb1[y].add(x)

for x,y in cd:
    b1[x].add(y)
    b1[y].add(x)
    fb1[x].add(y)
    fb1[y].add(x)

v0 = []
all_v = []
for h in range(1, n+1):
    if h in all_v:
        continue
    st1 = [h]
    v1 = set()
    while st1:
        take1 = st1.pop()
        v1.add(take1)
        for i in f1[take1]:
            if i in v1:
                continue
            if i in st1:
                continue
            st1.append(i)
    v0.append(v1)
    all_v += v1

for i in v0:
    leni = len(i)
    for j in i:
        ans[j] = leni - len(i & fb1[j]) - 1

print(*ans[1:])

### FIXED CODE ###

from collections import deque

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

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
ans = [0]*(N+1)
visited = [0]*(N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])