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

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    print(0)
    g = {'Vacant':0, 'Male':1, 'Female':2}
    sl = g[input()]
    if sl == 0:
        return
    print(N-1)
    sr = g[input()]
    if sr == 0:
        return
    l = 0
    r = N-1
    while True:

        m = (l+r)//2
        print(m)
        a = g[input()]
        if a == 0:
            return
        
        if (m-l) % 2 == 1 and sl == a:
            r = m
            sr = a
        else:
            l = m+1
            sl = a
        




if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    g = {'Vacant':0, 'Male':1, 'Female':2}



    print(0,flush=True)
    sl = g[input()]
    if sl == 0:
        return

    print(N-1,flush=True)
    sr = g[input()]
    if sr == 0:
        return
    
    l = 0
    r = N-1
    while r-l>1:

        m = (l+r)//2
        print(m,flush=True)
        a = g[input()]
        if a == 0:
            return
        
        if (m-l) % 2 == 1:
            if sl == a:
                r = m
                sr = a
            else:
                l = m
                sl = a

        else:
            if a != sl:
                r = m
                sr = a
            else:
                l = m
                sl = a
        

    print(-1)


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

import sys
import re
sys.setrecursionlimit(10 ** 7)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def SI(): return input()


def main():
    S = SI()
    ans = 0
    while(1):
        a = S.find("ABC")
        if a == -1:
            break
        ans += 1
        i = 1
        aa = 0
        while(S[a-i] == 'A' and a-i >= 0):
            ans += 1
            i += 1
            aa += 1
        S = S[a+3:]
        bc = 0
        while(S[:2] == "BC"):
            ans += 1
            S = S[2:]
            bc += 1
        ans += aa*bc
        S = "A"*(aa+1) + S
    print(ans)


main()


### FIXED CODE ###

import sys
import re
sys.setrecursionlimit(10 ** 7)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def SI(): return input()


def main():
    S = SI()
    ans = 0
    S = S.replace("A", "0")
    S = S.replace("BC", "1")
    a = 0
    b = 0
    for s in S:
        if s == "0":
            a += 1
        elif s == "1":
            ans += a
            b = 1
        else:
            a = 0
    print(ans)


main()
### BUGGY CODE ###

s = input()
K = int(input())
ans_lis = []
s_length = len(s)
lis = [[] for i in range(26)]

for i in range(s_length):
    lis[ord(s[i]) - ord('a')].append(i)


for i in range(26):
    for j in lis[i]:
        k = j
        while k <= s_length:
            ans_lis.append(s[j:k + 1])
            k += 1
    ans_lis = sorted(list(set(ans_lis)))
    if len(ans_lis) >= K:
        print(ans_lis[K - 1])
        exit()


### FIXED CODE ###

s = input()
K = int(input())
ans_lis = []
s_length = len(s)
lis = [[] for i in range(26)]

for i in range(s_length):
    lis[ord(s[i]) - ord('a')].append(i)


for i in range(26):
    k = 1
    while k <= K:
        for j in lis[i]:
            ans_lis.append(s[j:j + k])
        k += 1
        ans_lis = sorted(list(set(ans_lis)))
    if len(ans_lis) >= K:
        print(ans_lis[K - 1])
        exit()
### BUGGY CODE ###

import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.child = [set([i]) for i in range(n+1)]

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            y = self.find(self.root[x])
            self.root[x] = y
            self.child[y] |= self.child[x]
            return self.root[x]

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
            self.child[ry] |= self.child[rx]
        else:
            self.root[ry] = rx
            self.child[rx] |= self.child[ry]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.unite(p-1, q-1)

    for _ in range(L):
        r, s = map(int, input().split())
        rail.unite(r-1, s-1)

    ans = []
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)

        a = len(road.child[n] & rail.child[m])
        ans.append(a)

    return print(*ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            y = self.find(self.root[x])
            self.root[x] = y
            return self.root[x]

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
        else:
            self.root[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

def main():
    input = sys.stdin.readline
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    rail = UnionFind(N)

    for _ in range(K):
        p, q = map(int, input().split())
        road.unite(p-1, q-1)

    for _ in range(L):
        r, s = map(int, input().split())
        rail.unite(r-1, s-1)

    d = defaultdict(lambda: 0)
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)
        d[(n, m)] += 1

    ans = []
    for i in range(N):
        n = road.find(i)
        m = rail.find(i)
        ans.append(d[(n, m)])

    return print(*ans)


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

X, Y, Z, K = map(int, input().split())
X, Y, Z = sorted([X, Y, Z], reverse=True)
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A, B, C = sorted([A, B, C], reverse=True)
AB = []
for i in range(X):
    for j in range(Y):
        AB.append(A[i] + B[j])
AB = sorted(AB, reverse=True)

if len(AB) > K:
    AB = AB[:K + 1]
ABC = []
for i in range(len(AB)):
    for j in range(Z):
        ABC.append(AB[i] + C[j])
ABC = sorted(ABC, reverse=True)
print(*ABC[:K])

### 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 = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)

ABC = []
for i in range(X):
    if (i + 1) > K:
        break
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for l in range(Z):
            if (i + 1) * (j + 1) * (l + 1) > K:
                break
            ABC.append(A[i] + B[j] + C[l])
ABC = sorted(ABC, reverse=True)
print(*ABC[:K])
### BUGGY CODE ###

from itertools import accumulate


def main():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    accumulateA = list(accumulate(A))
    accumulateB = list(accumulate(B))
    accumulateA.insert(0, 0)
    accumulateB.insert(0, 0)
    count = 0
    for i in range(N+1):
        for j in range(M+1):
            if accumulateA[i] + accumulateB[j] <= K:
                count = max(count, i + j)
    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from itertools import accumulate
import bisect


def main():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    accumulateA = list(accumulate(A))
    accumulateB = list(accumulate(B))
    accumulateA.insert(0, 0)
    accumulateB.insert(0, 0)
    count = 0
    for i in range(N+1):
        j = bisect.bisect(accumulateB, K - accumulateA[i]) - 1
        if j >= 0:
            count = max(count, i + j)
    print(count)


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

N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))

MOD = 10**9+7

a = [[0 for j in range(M+1)] for i in range(N+1)]

for i in range(N+1) :
    for j in range(M+1) :
        if i == 0 or j == 0 :
            a[i][j] = 1
        else :
            a[i][j] = a[i-1][j] + a[i][j-1] - (a[i-1][j-1] if S[i-1] != T[j-1] else 0)
            a[i][j] %= MOD

print(a[N][M])


### FIXED CODE ###

N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))

MOD = 10**9+7

a = [[0 for j in range(M+1)] for i in range(N+1)]

for i in range(N+1) :
    for j in range(M+1) :
        if i == 0 or j == 0 :
            a[i][j] = 1
        else :
            a[i][j] = a[i-1][j] + a[i][j-1] - (a[i-1][j-1] if S[i-1] != T[j-1] else 0)
            a[i][j] %= MOD

print(a[N][M])
### BUGGY CODE ###

N=int(input())
temp=input().split()
d=[int(temp[i]) for i in range(N)]
dd=[]
for i in range(N):
  dd.append(min(d))
  d.remove(min(d))
  
a=dd[int(N/2-1)]
b=dd[int(N/2)]
print(int(b-a))

### FIXED CODE ###

N=int(input())
temp=input().split()
d=[int(temp[i]) for i in range(N)]
d.sort()
  
a=d[int(N/2-1)]
b=d[int(N/2)]
print(int(b-a))
### BUGGY CODE ###

def run():
  b = 10**9+7
  N = int(input())
  a_li = list(map(int, input().split()))
  ans = 0
  for i in range(N-1):
    for j in range(i+1, N):
      ans += a_li[i]^a_li[j]
  print(ans%b)

if __name__ == '__main__':
  run()

### FIXED CODE ###

def run():
  b = 10**9+7
  bit = 60
  N = int(input())
  a_li = list(map(int, input().split()))
  ans = 0
  dp = [[0]*bit for i in range(N)]
  for i in range(bit):
    dp[0][i] = (a_li[0] >> i) & 1
  for i in range(1, N):
    tem = 0
    for j in range(bit):
      a_j = (a_li[i] >> j) & 1
      dp[i][j] = dp[i-1][j] + a_j
      if a_j == 1:
        tem += (i-dp[i-1][j]) << j
      else:
        tem += dp[i-1][j] << j
    #print(ans, tem)
    ans += tem
  #print(dp)
  print(ans%b)

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

n = int(input())
c = []
for i in range(n):
  C = input()
  if c.count(C) == 0:
    c.append(C)
print(len(c))

### FIXED CODE ###

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

print(len(list(set(c))))
### BUGGY CODE ###

s = input()
K = int(input())

cnt = 0
uni = set()
for i in range(1, len(s)+1):
    for j in range(len(s)):
        if len(s) - (j+i) < 0: break
        uni.add(s[j:j + i])

print(sorted(list(uni))[K-1])

### FIXED CODE ###

s = input()
K = int(input())

cnt = 0
uni = set()
for i in range(1, K+1):
    for j in range(len(s)):
        if len(s) - (j+i) < 0: break
        uni.add(s[j:j + i])

print(sorted(list(uni))[K-1])
### BUGGY CODE ###

import numpy as np
import itertools
def p(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
n=int(input())
p=p(n)
if len(p)==1:
    print(p[0]-1)
    exit()
a=10**12
b=1
for i in p:
    b*=i
for k in range(int(len(p)**0.5),len(p)):    
    for i in itertools.combinations(p, k):
        c=np.prod(i)
        a=min(a,c+b//c)
print(a-2)

### FIXED CODE ###

n=int(input())
a=10**12
for i in range(1,int(n**0.5)+2):
    if n%i==0:
        a=min(a,i+n//i-2)
print(a)
### BUGGY CODE ###

e,a = map(int,input().split())
cnt =0
while True:
    if e==0 and a==0:
        break
    else:
        for i in range(1,e+1):
            for j in range(i+1,e+1):
                for k in range(j+1,e+1):
                    if i+j+k ==9:
                        cnt +=1
print(cnt)


### FIXED CODE ###

while True:
    e,a = map(int,input().split())
    if e ==0 and a ==0:
        break
    cnt = 0
    for i in range(1,e+1):
        for j in range(1,e+1):
            if j<=i:
                continue
            X = a - (i + j)
            if X > j and X <=e:
                cnt +=1
    print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X = MAP()
A = LIST()

dp = list2d(N, N, INF)
for i in range(N):
    k = 0
    for j in range(i, i-N, -1):
        j %= N
        dp[i][k] = min(dp[i][(k-1)%N], A[j])
        k += 1

ans = [0] * N
for i in range(N):
    for j in range(N):
        ans[j] += dp[i][j]
    ans[i] += i * X
print(min(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X = MAP()
A = LIST()

dp = list2d(N, N, INF)
for i in range(N):
    k = 0
    for j in range(i, i-N, -1):
        j %= N
        dp[i][k] = min(dp[i][(k-1)%N], A[j])
        k += 1

ans = [0] * N
for i in range(N):
    for j in range(N):
        ans[j] += dp[i][j]
    ans[i] += i * X
print(min(ans))
### BUGGY CODE ###

a=list(map(int,input().split()))
b=0
c=1
while(c*a[0]<(a[2]+0.5)):
  b=b+a[1]
  
print(b)

### FIXED CODE ###

a=list(map(int,input().split()))
b=0
c=1
while(c*a[0]<(a[2]+0.5)):
  b=b+a[1]
  c=c+1
  
print(b)
### BUGGY CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=10**9+7
if len(set(a))!=len(a) or len(set(b))!=len(b):
  print(0)
else:
  a.sort()
  b.sort()
  L=[]
  for i in range(n):
    l=[]
    for j in range(m):
      l.append(0)
    L.append(l)
  if m*n in a and m*n in b:
    L[a.index(m*n)][b.index(m*n)]=m*n
    ct=1
    ctn=1
    ctm=1
    for k in range(m*n-1,0,-1):
      if k in a and k in b:
        L[bisect.bisect_left(a,k)][bisect.bisect_left(b,k)]=k
        ct*=1
        ctn+=1
        ctm+=1
      elif k in a or k in b:
        if k in a:
          ct*=ctm
          ctn+=1
        if k in b:
          ct*=ctn
          ctm+=1
      else:
        ct*=(ctm*ctn-m*n+k)
      if ct==0:
        break
      ct=ct%x
    print(ct)
  else:
    print(0)

### FIXED CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=10**9+7
if len(set(a))!=len(a) or len(set(b))!=len(b):
  print(0)
else:
  a.sort()
  b.sort()
  L=[]
  for i in range(n):
    l=[]
    for j in range(m):
      l.append(0)
    L.append(l)
  if m*n in a and m*n in b:
    L[a.index(m*n)][b.index(m*n)]=m*n
    ct=1
    ctn=1
    ctm=1
    A=set(a)
    B=set(b)
    for k in range(m*n-1,0,-1):
      if k in A and k in B:
        L[bisect.bisect_left(a,k)][bisect.bisect_left(b,k)]=k
        ct*=1
        ctn+=1
        ctm+=1
      elif k in A:
          ct*=ctm
          ctn+=1
      elif k in B:
          ct*=ctn
          ctm+=1
      else:
        ct*=(ctm*ctn-m*n+k)
      if ct==0:
        break
      ct=ct%x
    print(ct)
  else:
    print(0)
### BUGGY CODE ###

#ABC072-C
import collections
import itertools

n = int(input())
a = list(map(int,input().split()))
 
cnt = [0] * 100000000


for i in a:
    cnt[i] += 1
    cnt[i+1] += 1
    cnt[i+2] += 1
    
    

    
        
print(max(cnt))


### FIXED CODE ###

#ABC072-C
n = int(input())
a = list(map(int,input().split()))
 
cnt = [0] * 100002


for i in a:
    cnt[i] += 1
    cnt[i+1] += 1
    cnt[i+2] += 1
    
    

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

n = int(input())
counter = 0
s = "TEMP"
list = []

while n > 0:
  s = input()
  list.append(s)
  counter = 0
  for item in list:
    if item == s:
      counter = counter - 1
    counter = counter + 1
  counter += 1
  n = n - 1

print(counter)

### FIXED CODE ###

n = int(input())
counter = 0
s = "TEMP"
list = []
temp = ''

while n > 0:
  s = input()
  list.append(s)
  n = n - 1

list.sort()
for item in list:
  if item == temp:
    counter = counter - 1
  counter = counter + 1
  temp = item

print(counter)
### BUGGY CODE ###

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

d=1

for b in a:
  
  d=d*b
if d>10**18:
  print("-1")
else:
  print(d) 

### FIXED CODE ###

def main():

	n=input()
	a=list(map(int,input().split()))
	
	
	if 0 in a:
		print(0)
		return

	d=1
    
	

	for b in a:
		d=d*b
		if d>10**18:
			print("-1")
			return
	print(d)

main()
### BUGGY CODE ###

import numpy as np
N ,K = list(map(int, input().split()))
p = list(map(int, input().split()))
pline=[]
for i in range(N-K+1):
  p[i] = sum(np.array(list(map(lambda x: (x+1)/2, p[i:i+K]))))
  
print(max(p))

### FIXED CODE ###

N ,K = list(map(int, input().split()))
p = list(map(lambda x: (1+int(x))/2, input().split()))
s = [0]*N
s[0]=p[0]
for i in range(1,N):
  s[i] = s[i-1]+p[i]

l = [s[K-1]]
for i in range(N-K):
  l.append(s[i+K]-s[i])

print(max(l))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

for i in range(Q):
    l, r = map(int, input().split())
    s = S[l-1:r]
    count = 0
    for j in range(r-l):
        if(s[j:j+2] == 'AC'):
            count += 1
    print(count)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

C = [0]*N
for i in range(1, N):
    C[i] += C[i-1]
    if(S[i-1:i+1] == 'AC'):
        C[i] += 1

for i in range(Q):
    l, r = map(int, input().split())
    print(C[r-1]-C[l-1])
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
s=set(a)
h=[]
ans=0
for i in s:
  l=a.count(i)
  h.append(l)
if len(s)-k>0:
  for i in range(len(s)-k):
    ans+=min(h)
    h.remove(min(h))
  print(ans)
else:
  print(0)

### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(Counter(a).values(), reverse=True)
print(sum(a[k:]))
### BUGGY CODE ###

import heapq
import itertools
n, m, r = map(int, input().split())
r = list(map(lambda x:int(x)-1, input().split()))
d = [[float('inf')]*n for _ in range(n)]
for _ in range(m):
  a, b, t = map(int, input().split())
  a -= 1
  b -= 1
  d[a][b] = t
  d[b][a] = t
for i in range(n):
  d[i][i] = 0


def warshall_floyd(d):
  #d[i][j]: iからjへの最短距離
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j],d[i][k] + d[k][j])
  return d  

d = warshall_floyd(d)

ans = float('inf')
for v in itertools.permutations(r):
  tmp = 0
  for i in range(len(v)-1):
    tmp += d[v[i]][v[i+1]]
  ans = min(ans, tmp)

print(ans)


### FIXED CODE ###

import itertools
n, m, r = map(int, input().split())
d = [[float('inf')]*n for _ in range(n)]
rs = list(map(int, input().split()))
for _ in range(m):
  a, b, t = map(int, input().split())
  a -= 1
  b -= 1
  d[a][b] = t
  d[b][a] = t
for i in range(n):
  d[i][i] = 0

def warshall_floyd(d):
  #d[i][j]: iからjへの最短距離
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j],d[i][k] + d[k][j])
  return d 

d = warshall_floyd(d)
ans = float('inf')
for p in itertools.permutations(rs):
  tmp = 0
  for i in range(len(p)-1):
    tmp += d[p[i]-1][p[i+1]-1]
  ans = min(ans, tmp)

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

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

def main():
    a,b,c,k = map(int,input().split())
    high=a
    middle=b
    low=c
    count=0

    while count<k:
        if a == b == c:
            print(0)
            exit()
        high = b+c
        middle = a+c
        low = a+b
        a=high
        b=middle
        c=low
        count+=1
    if abs(high-middle) >10**18:
        print("Unfair")
        exit()
    else:
        print(high-middle) 
    

if __name__=="__main__":
    main()

### FIXED CODE ###

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

def main():
    a,b,c,k = map(int,input().split())

    if abs(a-b)>10**18:
        print("Unfair")
    elif k % 2==0:
        print(a-b)
    else:
        print(b-a) 

if __name__=="__main__":
    main()
### 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.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)


"""
愚直解
X*Y*Z全部作って上から順にK個書き出す。普通に間に合わない
愚直解のいけてない部分として、X*Yを作った段階で、他のX*Yよりずっと小さいときに、Zとの積を見るまでもなくK番目までに入らないケースがある。
なんというか、　X*Y*Z　を　W*Z (W=X*Y)と置き換えたときに、Wの中で順位が低いものとZとの積を計算して他と比較する意味がない。
W = [9,8,7,6,5,4,3]
Z = [6,4,3,2,1]
K = 5
とかで考えると、Wが3や4のものは見る必要がない。
というのも、それより大きいWがK個以上あることが分かっているので、W*ZもK個以上大きいものが存在するといえるので。

なので、先にX*Yを計算して、その中で上位K個とZの積をとってさらにK個選べばいけそう


"""
W = []
for a in A:
    for b in B:
        W.append(a+b)

W.sort(reverse=True)
if len(W) > K:
    W = W[:K]
ans = []
for w in W:
    for c in C:
        ans.append(w+c)

ans.sort(reverse=True)
print(*ans[:K], sep="\n")

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

abc = []

for i in range (x):
      for j in range(y):
            for(k) in range(z):
                  if (i+1)*(j+1)*(k+1) <= K:
                        abc.append(a[i]+b[j]+c[k])
                  else:
                        break

abc.sort(reverse=True)
for i in abc[:K]:
      print(i)
### BUGGY CODE ###

import bisect
#import sys
#input = sys.stdin.readline
 
n = int(input())
l = list(map(int, input().split()))
l.sort()

cnt = 0
for i in range(n):
  for j in range(n-i-1):
    cnt += bisect.bisect_left(l[j+i+2:], l[i] + l[j+i+1])
    
print(cnt)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
 
n = int(input())
l = [int(li) for li in input().split(' ')]
l.sort()

cnt = 0
for i in range(n):
  for j in range(i+1, n):
    cnt += bisect.bisect_left(l, l[i]+l[j])-j-1
    
print(cnt)