Harryxun/stf_run huggingface dataset:
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(n)]
#wv[i][0]:i番目の品物の重さ
#wv[i][1]:i番目の品物の価値

dp = [0]*(w+1)#dp[i]:重さiにおける最大価値
for i in range(n):#あるi番目の品物について
    for j in range(w,wv[i][0]-1, -1):#ある重さjについて
        dp[j] = max( dp[j], dp[j-wv[i][0]]+wv[i][1] )#i番目の品物を使うほうが重さjでの価値が高い場合は値を更新

print(max(dp))

### FIXED CODE ###

n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for i in range(n)]
#wv[i][0]:i番目の品物の重さ
#wv[i][1]:i番目の品物の価値

dp = [0]+[float("inf")]*(10**5)#dp[k]:価値kにおける最小重さ
for i in range(n):#あるi番目の品物について
    for j in range(10**5,wv[i][1]-1, -1):#ある価値jについて
        dp[j] = min( dp[j], dp[j-wv[i][1]]+wv[i][0] )
        #重さwv[i][0]であるi番目の品物を使うほうが価値jでの最小重さdp[j]が小さい場合は値を更新

res = 0
for v,e in enumerate(dp):#インデックスv(=ある価値j)における最小重さeについて
    if e <= w:
        res = v#最小重さが重さ制限を超えないならres更新
print(res)
from itertools import permutations
n=int(input())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
l=list(itertools.permutations([i for i in range(1,n+1)]))
a=0
b=0
for i in range(len(l)):
  if l[i]==p:
    a=i
  if l[i]==q:
    b=i
print(abs(a-b))

### FIXED CODE ###

import itertools as it
s = list(range(1,int(input())+1))
a = list(it.permutations(s))
p,q = [tuple(map(int,input().split())) for i in range(2)]
print(abs(a.index(p)-a.index(q)))
n,k = map(int,input().split())
s = input()
#入力
cnt = 0
if s[0] == '0':
    cnt += 1
for i in range(1,n):
    if s[i-1] == '1' and s[i] == '0':
        cnt += 1
##切り替わるところで＋1
if cnt <= k:
    print(n)
    #切り替わるところが動かす回数より少ない場合n(自明)
else:
    one_left,one_right = [0],[]
    #
    for i in range(1,n):
        if s[i-1] == '0' and s[i] == '1':
            one_left.append(i)
        if s[i-1] == '1' and s[i] == '0':
            one_right.append(i)
    #01 の時右に加える10の時左に加える
    #切り替えの時の配列の番号を加える
    one_right.append(n)
    #nはとりあえず右
    if s[0] == '1':
        one_right.pop(0)
    if s[-1] == '1':
        one_left.pop(-1)
    #最初の人が逆立ちしているなら右の切り替えの最初はなし
    #最後の人が逆立ちしているなら左の切り替えの最後はなし
    #print(one_right,'r')
    #print(one_left,'l')

    ans = 0
    #ans 01,10の切り替えの少ないほうでloopを回す
    for i in range(min(len(one_left),len(one_right)-k+1)):
        ans = max(ans,one_right[i+k-1]-one_left[i])
        #ans は　ある点までの個数-フラグの開始点までの個数の最大値
print(ans)



### FIXED CODE ###

#looked ans

n,k = map(int,input().split())
s = input()
#入力
cnt = 0
if s[0] == '0':
    cnt += 1
for i in range(1,n):
    if s[i-1] == '1' and s[i] == '0':
        cnt += 1
##切り替わるところで＋1
if cnt <= k:
    print(n)
    #切り替わるところが動かす回数より少ない場合n(自明)
else:
    one_left,one_right = [0],[]
    #
    for i in range(1,n):
        if s[i-1] == '0' and s[i] == '1':
            one_left.append(i)
        if s[i-1] == '1' and s[i] == '0':
            one_right.append(i)
    #01 の時右に加える10の時左に加える
    #切り替えの時の配列の番号を加える
    one_right.append(n)
    #nはとりあえず右
    if s[0] == '1':
        one_right.pop(0)
    if s[-1] == '1':
        one_left.pop(-1)
    #最初の人が逆立ちしているなら右の切り替えの最初はなし
    #最後の人が逆立ちしているなら左の切り替えの最後はなし
    #print(one_right,'r')
    #print(one_left,'l')

    ans = 0
    #ans 01,10の切り替えの少ないほうでloopを回す
    for i in range(min(len(one_left),len(one_right)-k+1)):
        ans = max(ans,one_right[i+k-1]-one_left[i])
        #ans は　ある点までの個数-フラグの開始点までの個数の最大値
    print(ans)
import math

try:
while True:
  a,b=map(int,input().split())
  print(math.gcd(a,b),a*b// math.gcd(a, b))
 except:
   pass
 

### FIXED CODE ###

def gcd(x,y):
    while y:
        x, y = y, x % y
    return x


def lcm(x,y):
    return x * y // gcd(x,y)


while True:
    try:
        a = list(map(int,input().split()))
        print(gcd(a[0],a[1]),lcm(a[0],a[1]))
    except:
        break
N, M = map(int, input().split())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
D = [[-1, -1, -1] for i in range(N)]
Q = [[-1, -1, -1] for i in range(M)]
if M:
  Q[0] = [S - 1, 0, RD[S - 1] % 3]
else:
  Q = [[-1, -1, -1]]
o = 0
i = 1
while Q:
  q, d, m = Q[o]
  Q[o] = [-1, -1, -1]
  o = (o + 1) % M
  if q == -1:
    break
  if RD[q] == -1:
    continue
  D[q][m] = d + RD[q]
  if m != 0:
    for adj in E[q]:
      _m = (d + 1 + RD[adj]) % 3
      if D[adj][_m] == -1:
        Q[i] = [adj, d + 1, _m]
        i = (i + 1) % M
P = [d[0] for d in D if d[0] != -1]
if P:
  print(min(P) // 3)
else:
  print(-1)

### FIXED CODE ###

N, M = map(int, input().split())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
D = [[-1, -1, -1] for i in range(N)]
Q = [[-1, -1, -1] for i in range(M)]
if M:
  Q[0] = [S - 1, 0, RD[S - 1] % 3]
o = 0
i = 1
while Q:
  q, d, m = Q[o]
  Q[o] = [-1, -1, -1]
  o = (o + 1) % M
  if q == -1:
    break
  if RD[q] == -1:
    continue
  D[q][m] = d + RD[q]
  if m != 0:
    for adj in E[q]:
      _m = (d + 1 + RD[adj]) % 3
      if D[adj][_m] == -1:
        Q[i] = [adj, d + 1, _m]
        i = (i + 1) % M
P = [d[0] for d in D if d[0] != -1]
if P:
  print(min(P) // 3)
else:
  print(-1)
import sys
read=sys.stdin.read
readline=sys.stdin.readline

def isinsums(x,lst):
  s=sum(lst)
  t=(s+x)//2
  if s==0 and x==0:
    return True
  if (s-x)%2 or t<0:
    return False
  t=(s+x)//2
  m1=1<<(t+1)-1
  m2=1<<t
  sums=0
  for e in lst:
    sms=(sums|(1+sums)<<e)&m1
  sms|=1
  if (sms)&m2>0:
    return True
  return False

s=readline().strip()
x,y=map(int,readline().split())

s=s.replace('TF','T F')
s=s.replace('FT','F T')
bs=s.split()
if bs[0][0]=='F':
  x-=len(bs[0])
  del bs[0]

xy=[[],[]]
f=0
for i,e in enumerate(bs):
  if not i%2:
    l=len(e)
  else:
    f^=l%2
    xy[f].append(len(e))
print(bs,xy,x,y)
if isinsums(x,xy[0]) and isinsums(y,xy[1]):
  print('Yes')
else:
  print('No')


### FIXED CODE ###

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

def isinsums(x,lst):
  s=sum(lst)
  t=(s+x)//2
  if s==0 and x==0:
    return True
  if (s-x)%2 or t<0:
    return False
  t=(s+x)//2
  m1=(1<<(t+1))-1
  m2=1<<t
  sums=0
  for e in lst:
    sums=(sums|(1+sums)<<e)&m1
  sums|=1
  if (sums)&m2>0:
    return True
  return False

s=readline().strip()
x,y=map(int,readline().split())

s=s.replace('TF','T F')
s=s.replace('FT','F T')
bs=s.split()
if bs[0][0]=='F':
  x-=len(bs[0])
  del bs[0]

xy=[[],[]]
f=0
for i,e in enumerate(bs):
  if not i%2:
    l=len(e)
  else:
    f^=l%2
    xy[f].append(len(e))
if isinsums(x,xy[0]) and isinsums(y,xy[1]):
  print('Yes')
else:
  print('No')
n=int(input())
s=input()
k=int(input())
num = 0
for i in s:
  if i == s[k]:
    num +=1
  else:
    s = s.replace(i,'*')
    num +=1

### FIXED CODE ###

n=int(input())
s=input()
k=int(input())
num = 0
for i in s:
  if i == s[k-1]:
    num +=1
  else:
    s = s.replace(s[num],'*')
    num +=1
print(s)
N, M = input().split()
X = list(map(int, input().split()))

if N >= M:
    print(0)
else:
    X.sort()
    L = []
    for i in range(M-1):
        L.append(X[i+1]-X[i])
    L.sort(reverse=True)
    print(X[M-1]-X[0]-sum(L[:N-1]))


### FIXED CODE ###

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

if N >= M:
    print(0)
else:
    X.sort()
    L = []
    for i in range(M-1):
        L.append(X[i+1]-X[i])
    L.sort(reverse=True)
    print(X[M-1]-X[0]-sum(L[:N-1]))
N, K = map(int, input().split())
A = list(map(int, input().split()))

NN = [-1] * N
NN[0] = 0

i = 0
num = 0

while True:
    num += 1
    i = A[i] - 1
    if NN[i] != -1:
        n1 = NN[i]
        break
    NN[i] = num

n_ = num - n1

if K > N:
    K -= n1
    t = NN.index(n1 + K % n_) + 1
    print(t)
else:
    t = NN.index(K)
    print(t) + 1


### FIXED CODE ###

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

NN = [-1] * N
NN[0] = 0

i = 0
num = 0

while True:
    num += 1
    i = A[i] - 1
    if NN[i] != -1:
        n1 = NN[i]
        break
    NN[i] = num

n_ = num - n1

if K > n1:
    K -= n1
    t = NN.index(n1 + K % n_) + 1
    print(t)
else:
    t = NN.index(K) + 1
    print(t)
from itertools import combinations_with_replacement as c
n, m, q = [int(i) for i in input().split()]
abc = [[int(i) for i in input().split()] for _ in range(q)]
aa = list(range(1,m+1))
ans = 0
for bb in c(aa,m):
    cc = 0
    for a, b, c, d in abc:
        if bb[b-1] - bb[a-1] == c:
            cc += d
    ans = max(ans, cc)
print(ans)

### FIXED CODE ###

from itertools import combinations_with_replacement as c
n, m, q = [int(i) for i in input().split()]
abc = [[int(i) for i in input().split()] for _ in range(q)]
aa = list(range(1,m+1))
ans = 0
for bb in c(aa, n):
    cc = 0
    for a, b, c, d in abc:
        if bb[b-1] - bb[a-1] == c:
            cc += d
    ans = max(ans, cc)
print(ans)
t = [0]
x = [0]
y = [0]
N = int(input())
for i in range(1,N+1):
  ti,xi,yi = map(int,input(),split())
  t.append(ti)
  x.append(xi)
  y.append(yi)
  
flg = True
 
for i in range(0,N):
  if t[i+1]-t[i] <　x[i+1]-x[i] + y[i+1]-y[i]:
    flg = False
  else (t[i+1]-t[i])%2 == (x[i+1]-x[i] + y[i+1]-y[i])%2:
    flg = False
if(flg):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

t = [0]
x = [0]
y = [0]
n = int(input())
for i in range(n):
    ti, xi, yi = map(int, input().split())
    t.append(ti)
    x.append(xi)
    y.append(yi)
    
flg=True
for i in range(1, n+1):
    if((x[i]-x[i-1])+(y[i]-y[i-1])>(t[i]-t[i-1])):
        flg=False
    elif(((x[i]-x[i-1])+(y[i]-y[i-1]))%2!=(t[i]-t[i-1])%2):
        flg=False
if(flg):
    print("Yes")
else:
    print("No")
s = list(input())
if s//1000==s//100-s//1000*10:
    print("good")
    if s//100-s//1000*10==s//10-s//100*10+s//1000*100:
        print("good")
        if s//10-s//100*10+s//1000*100==s-s//10*10+s//100*100-s//1000*1000:
print("bad")        

### FIXED CODE ###

s=input()
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
    print("Bad")
else:
    print("Good")
import math
from itertools import combinations, permutations

def dist(x1, y1, x2, y2):
    return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** .5


n = int(input())
xy = [[int(i) for i in input().split()] for _ in range(n)]
edges = list(range(n))
memo = {}
res = 0
for p in permutations(edges):
    for i, a in enumerate(p[1:], start=1):
        b = p[i - 1]
        if (a, b) in memo:
            res += memo[a, b]
        else:
            d = dist(*xy[a], *xy[b])
            memo[a, b] = d
            memo[b, a] = d
            res += d
print(res / math.factorial(n))

### FIXED CODE ###

import math
from itertools import combinations, permutations

def dist(x1, y1, x2, y2):
    return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** .5


n = int(input())
xy = [[int(i) for i in input().split()] for _ in range(n)]
edges = list(range(n))
memo = {}
res = 0
for p in permutations(edges):
    for i, a in enumerate(p[1:], start=1):
        b = p[i - 1]
        if (a, b) in memo:
            res += memo[a, b]
        else:
            d = dist(xy[a][0], xy[a][1], xy[b][0], xy[b][1])
            memo[a, b] = d
            memo[b, a] = d
            res += d
print(res / math.factorial(n))
N, M = map(int, input().split())

small=min(N,M)
big  =max(N,M)
if small==1:
    if big==1:
        print (1)
    elif big==2:
        print (0)
    else:
        print (big-2)

elif small==2:
    print (0)
    
else:
    print ((small-2)*(big-2))

### FIXED CODE ###

one = str(input())
two = str(input())
three = str(input())
print(one[0]+two[1]+three[2])
N,K = map(int,input().split())
S = []
d = {}
for i in range(K):
    d[i] = 0
d[0] = 1
A = list(map(int,input().split()))
s = 0
ans = 0
for i in range(1,N+1):
    s = (s+A[i-1])%K
    k = (s-i)%K
    if i >= K:
        x = S.pop(0)
        d[x] -= 1
    ans += d[k]
    d[k] += 1
    S.append(k)
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
S = []
d = {}
A = list(map(int,input().split()))
ans = 0
sum =0
for i in range(1,N+1):
    sum += A[i-1] % K
    s = (sum - i) % K
    if i > K:
        x = S.pop(0)
        d[x] -= 1
    elif i < K:
        if s == 0:
            ans += 1
    if s not in d:
        d[s] = 0
    ans += d[s]
    d[s] += 1
    S.append(s)
print(ans)
n, k = map(int, input().strip().split(" "))
h = list(map(int, input().split(" ")))

dp = [10**5] * (n+k+1)
dp[0] = 0

for i in range(n):
    for j in range(1, k+1):
        dp[i+j] = min(dp[i+j], abs(h[i]-h[i+j])+dp[i])

print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().strip().split(" "))
h = list(map(int, input().split(" ")))

dp = [0] * n
dp[1] = abs(h[0]-h[1])

for i in range(2, n):
    dp[i] = min([abs(h[i]-h[j])+dp[j] for j in range(max(0, i-k), i)])

print(dp[n-1])
print("Hello World" if input() == "1" int(input()) + int(input()))


### FIXED CODE ###

print("Hello World" if input() == "1" else int(input()) + int(input()))
import math

x, y = map(int, input().split())

if (x + y) % 3 != 0:
    ans = 0
else:

    b = (2*y - x) / 3 
    a = b + x -y

    a_b = math.factorial(a+b)
    ab = math.factorial(a)* math.factorial(b) % 1000000007
    

    ans = (a_b // ab) % 1000000007

    # answer = (a+b)! / a!b! mod 10^9+7

    
print(ans)

# 999999 999999

### FIXED CODE ###

from math import factorial
import sys

x, y = map(int, input().split())

maxim = 10**6+10
mod = 10**9 + 7

fac = [None] * maxim
finv = [None] * maxim
inv = [None] * maxim

def cominit():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1

    for i in range(2, maxim):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

def com(n, k):
    if (n < k):
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    if (x + y) % 3 != 0:
        return 0
    else:

        b = (2*y - x) // 3 
        a = b + x -y
        if a < 0 or b < 0:
            print(0)
            sys.exit()
        
        cominit()
        ans = com(a+b, b)
        return ans 
    # answer = (a+b)! / a!b! mod 10^9+7


    
print(main())

# 999999 999999
n,x = map(int,input().split())
if n != 1:
  l = list(map(int,input().split()))
  i = 0
  cnt = 0
  ans = 0
  while cnt <= x:
    ans += 1
    cnt += l[i]
    i += 1
  print(ans)
else:
  l = int(input())
  if l <= x:
    print(2)
  else:
    print(1)

### FIXED CODE ###

n,x = map(int,input().split())
if n != 1:
  l = list(map(int,input().split()))
  i = 0
  cnt = 0
  ans = 0
  while cnt <= x :
    if i == n:
      print(n+1)
      exit()
    ans += 1
    cnt += l[i]
    i += 1
  print(ans)
else:
  l = int(input())
  if l <= x:
    print(2)
  else:
    print(1)
import math

class Input():
	def readInt(self):
		return int(input())

	def readIntArray(self):
		return [int(x) for x in input().split(" ")]

	def readString(self):
		return input()

	def readStringArray(self):
		return input().split(" ")

	def readFloat(self):
		return float(input())

	def readFloatArray(self):
		return [float(x) for x in input().split(" ")]

def main():
	inp = Input()
	n, k = inp.readIntArray()
	height = inp.readIntArray()

	# cost = [1000000002 for i in range(n)]
	# cost[0] = 0

	# for i in range(n):
	# 	for j in range(1, k+1):
	# 		if (i + j) < n:
	# 			cost[i+j] = min(cost[i+j], cost[i] + abs(height[i+j] - height[i]))

	cost = [-1 for i in range(n)]

	def findAns(i):

		if i == 0:
			return 0

		if cost[i] != -1:
			return cost[i]

		start = max(0, i-k)
		ans = 1000000002
		for j in range(start, i):
			ans = min(ans, findAns(j)+abs(height[i] - height[j]))

		cost[i] = ans
		return ans


	print(findAns(n-1))


	# print(cost[n-1])

if __name__ == "__main__":
   main()


### FIXED CODE ###

from sys import stdin
n, k = [int(i) for i in stdin.readline().split(' ')]
h = [int(i) for i in stdin.readline().split(' ')]

minCosts = [0, abs(h[1]-h[0])]
for i in range(2, len(h)):
    minCosts.append(min([abs(h[i]-h[i-j])+minCosts[i-j] for j in range(1, min(i, k)+1)]))

print(minCosts[-1])
pay = input('')
yen1 = input('')
amari = pay % 500
if yen1 >= amari:
  print('YES')
else:
  print('NO')
  

### FIXED CODE ###

pay = int(input(''))
yen1 = int(input(''))
amari = pay % 500
if yen1 >= amari:
  print('Yes')
else:
  print('No')
MOD = 10**9 + 7

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

comb = [[1]]
for i in range(N + 1):
    comb.append([1])
    for j in range(i):
        comb[-1].append((comb[-2][j] + comb[-2][j + 1]))
    comb[-1].append(1)


for i in range(1,K+1):
	print(comb[N-i+1][k] * comb[K-1][i])



### FIXED CODE ###

MOD = 10**9 + 7
 
N,K = [int(s) for s in input().split()]
 
comb = [[1]]
for i in range(N + 1):
    comb.append([1])
    for j in range(i):
        comb[-1].append((comb[-2][j] + comb[-2][j + 1]) % MOD)
    comb[-1].append(1)
    
def combi(n,k):
  return comb[n][k] if n >= k else 1

for i in range(1,K+1):
  if i <= N-K+1:
    print((combi(N-K+1,i) * combi(K-1,i-1)) % MOD)
  else:
    print(0)
import sys
input = sys.stdin.readline


n,m = (int(x) for x in input().split())
visited = [False for _ in xrange(n)]

graph = dict(((i,[]) for i in xrange(n)))

def dfs(node):
    if visited[node]:
        return None
    visited[node] = True
    for next_node in graph[node]:
        dfs(next_node)
    return None

for _ in xrange(m):
    u,v = (int(x) - 1 for x in input().split())
    graph[u].append(v)
    graph[v].append(u)
ans = -1
for i in xrange(n):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)


### FIXED CODE ###

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

from collections import defaultdict

n,m=map(int,input().split())
visited=[0]*n
d=defaultdict(list)
def dfs(n):
    visited[n]=1
    #print(visited)
    for i in d[n]:
        if visited[i]==0:
            dfs(i)

for i in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    d[a].append(b)
    d[b].append(a)

r=-1
for i in range (n):
    if visited[i]==0:
        dfs(i)
        r+=1
print(r)
N, W = map(int, input().split())
Weight = [0]
Value = [0]

for i in range(N):
    w, v = map(int, input().split())
    Weight.append(w)
    Value.append(v)
if sum(Weight) <= W:
    print(sum(Value))
    exit()

DP = [[0] * (W + 1) for i in range(N + 1)]
for n in range(1, N + 1):
    for wei in range(W + 1):
        if Weight[n] > wei:
            DP[n][wei] = DP[n - 1][wei]
        else:
            DP[n][wei] = max(DP[n - 1][wei], DP[n - 1][wei - Weight[n]] + Value[n])
print(DP[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
Weight = [0]
Value = [0]
ans = 0
for i in range(N):
    w, v = map(int, input().split())
    Weight.append(w)
    Value.append(v)
VS = sum(Value)
DP = [[float('inf')] * (VS + 1) for i in range(N + 1)]

for n in range(N + 1):
    for val in range(VS + 1):
        if val == 0:
            DP[n][val] = 0
        elif Value[n] > val:
            DP[n][val] = DP[n - 1][val]
        else:
            DP[n][val] = min(DP[n - 1][val], DP[n - 1][val - Value[n]] + Weight[n])
            if (n == N) and (DP[n][val] <= W):
                ans = max(ans, val)

print(ans)
def SCC(G):
  D=[]
  C=[len(G)-1]
  U=[1]*len(G)
  def DFS(x):
    if U[x]:
      U[x]=0
      for i in range(len(G[x])):
        DFS(G[x][i])
      D.append(x)
  
  for i in range(len(G)):
    if U[i]:
      DFS(i)
  GR=[[] for i in range(len(G))]
  for i in range(N):
    for j in range(len(G[i])):
      GR[G[i][j]].append(i)
  R=[]
  U=[1]*len(G)
  def DFSR(x):
    if U[x]:
      R[-1].append(x)
      U[x]=0
      for i in range(len(GR[x])):
        DFSR(GR[x][i])
  
  for i in range(len(G)-1,-1,-1):
    if U[D[i]]:
      R.append([])
      DFSR(D[i])
  return R

import sys
S=sys.stdin.readlines()
N,M=map(int,S[0].split())
G=[[] for i in range(N)]
a,b=0,0
for i in range(M):
  a,b=map(int,S[i+1].split())
  G[a].append(b)
P=SCC(G)
print(len(P))
for i in range(len(P)):
  print(*([len(P[i])]+P[i]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
def SCC(G):
  D=[]
  C=[len(G)-1]
  U=[1]*len(G)
  def DFS(x):
    if U[x]:
      U[x]=0
      for i in range(len(G[x])):
        DFS(G[x][i])
      D.append(x)
  
  for i in range(len(G)):
    if U[i]:
      DFS(i)
  GR=[[] for i in range(len(G))]
  for i in range(N):
    for j in range(len(G[i])):
      GR[G[i][j]].append(i)
  R=[]
  U=[1]*len(G)
  def DFSR(x):
    if U[x]:
      R[-1].append(x)
      U[x]=0
      for i in range(len(GR[x])):
        DFSR(GR[x][i])
  
  for i in range(len(G)-1,-1,-1):
    if U[D[i]]:
      R.append([])
      DFSR(D[i])
  return R

S=sys.stdin.readlines()
N,M=map(int,S[0].split())
G=[[] for i in range(N)]
a,b=0,0
for i in range(M):
  a,b=map(int,S[i+1].split())
  G[a].append(b)
P=SCC(G)
print(len(P))
for i in range(len(P)):
  print(*([len(P[i])]+P[i]))
N,M = map(int,input().split())
A_i = list(map(int,input().solit()))
sum_A_i = sum(A_i)
X = 0

for i in A_i:
  if i > sum_A_i/(4*M):
    x += 1
    
  if x >=M:
    print("Yes")
  else:
    print("No")
  

### FIXED CODE ###

N, M = map(int,input().split())
l = list(map(int,input().split()))
 
T = sum(l)
V = 1/(4*M) * T
S = len(list(filter(lambda x: x>=V, l)) )
 
print( "Yes" if S >= M else "No" )
import math
from functools import reduce

n,x = map(int,input().split())
lst=list(map(int,input().split()))
new_lst=[abs(i-x) for i in lst]

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

print(gcd(*new_lst))

### FIXED CODE ###

import fractions
from functools import reduce

n,x = map(int,input().split())
lst=list(map(int,input().split()))
new_lst=[abs(i-x) for i in lst]

def gcd(*numbers):
  return reduce(fractions.gcd, numbers)
def gcd_list(numbers):
  return reduce(math.gcd, numbers)

print(gcd(*new_lst))
A=int(input())
if A > 999:
  print("ABC" + A)
else :
  print("ABD" + A)


### FIXED CODE ###

A=int(input())
if A > 999:
  print("ABD" )#+ str(A-1000))
else :
  print("ABC")# + str(A))
N = int(input())
x = 0
for _ in range(N):
    k, u = input().split()
    k += float(x)*(380000 if u == 'BTC' else 1)
print(k)

### FIXED CODE ###

N = int(input())
x = 0
for _ in range(N):
    k, u = input().split()
    x += float(k)*(380000 if u == 'BTC' else 1)
print(x)
def search(a, num, i):
  nxt = a[num]
  if(nxt == 1):
    return i
  elif(i >= len(a)):
    return -1
  else:
    return search(a, nxt, i+1)

n = int(input())
a = [ int(input()) - 1 for _ in range(n)]
print(search(a, 0, 1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
def search(arr, num, i):
  nxt = arr[num]
  if(nxt == 1):
    return i
  elif(i >= len(arr)):
    return -1
  else:
    return search(arr, nxt, i+1)

n = int(input())
a = [ int(input()) - 1 for _ in range(n)]
print(search(a, 0, 1))
print(['Yes','No'][len(set(input())<3])

### FIXED CODE ###

x=input()
print(['No','Yes'][len(set(x[1:]))==1 or len(set(x[:3]))==1])
A, B = map(int, raw_input().split())

print(str(w*h) + ' ' + str((w+h)*2)


### FIXED CODE ###

w,h = map(int, raw_input().split())

print(str(w*h) + ' ' + str((w+h)*2))
number = input()
answer = 0

for i in range(number):
  number = number+1
  answer = answer + number
  
print(answer)


### FIXED CODE ###

number = int(input())
answer = 0

for i in range(number+1):
  answer = answer + i
print(answer)
n=int(input())
a=list(map(int,input().split()))
ans=s[0]
for i in range(n):
  ans^=s[i]
if ans!=0:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
ans=s[0]
for i in range(1,n):
  ans^=s[i]
if ans!=0:
  print('No')
else:
  print('Yes')
n = int(input())
x = tuple(map(int, input().split(" ")))

for x_i in range(len(x)):
	x_dummy = :
	print(sorted(x_dummy.remove(x_i))[len(x)//2])

### FIXED CODE ###

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

x_sorted = sorted(x)
for x_i in x:
	print((x_sorted[n//2-1], x_sorted[n//2])[x_i < x_sorted[n//2]])