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

ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

X,Y,Z,K=rl()
A=rl()
B=rl()
C=rl()
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
X=[]
for a,b,c in zip(A,B,C):
    X.append([a,0])
    X.append([b,1])
    X.append([c,2])
X.sort(reverse=True)

ca=0
cb=0
cc=0
xl = 0
for i in range(len(X)):
    _,a = X[i]
    if a == 0:
        ca += 1
    elif a == 1:
        cb += 1
    else:
        cc += 1 
    if ca*cb*cc>=K:
        xl=i
Ax=[]
Bx=[]
Cx=[]
for x,a in X[:(xl+1)]:
    if a == 0:
        Ax.append(x)
    elif a == 1:
        Bx.append(x)
    else:
        Cx.append(x)

ans = []
import itertools
for a,b,c in itertools.product(Ax,Bx,Cx):
    ans.append(a+b+c)
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

### FIXED CODE ###

ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

X,Y,Z,K=rl()
A=rl()
B=rl()
C=rl()
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
ans = []
for a in range(1,X+1):
    for b in range(1,Y+1):
        for c in range(1,Z+1):
            if a*b*c<=K:
                ans.append(A[a-1]+B[b-1]+C[c-1])
            else:
                break
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

import copy

def nC2(n):
    if n < 2:
        return 0
    else:
        return n*(n-1)//2

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

count = 0
B = copy.copy(A)
Num = list(set(B))
for num in Num:
    count += nC2(B.count(num))
#print(count)

for k in range(n):
    B = copy.copy(A)
    num = B.pop(k)
#    print()
#    print(k, num, B)
    print(count - B.count(num))

### FIXED CODE ###

import copy
from collections import Counter

l = ['a', 'a', 'a', 'a', 'b', 'c', 'c']
c = Counter

def nC2(n):
    if n < 2:
        return 0
    else:
        return n*(n-1)//2

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

count = 0
C = Counter(A)
for num in C.values():
    count += num*(num-1)//2
#print(count)

for a in A:
    print(count - (C[a] - 1))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

def power(x, y):
   if y == 0:
       return 1
   elif y == 1:
       return x % mod
   elif y % 2 == 0:
       return power(x, y/2) ** 2 % mod
   else:
       return power(x, (y-1)/2) ** 2 * x % mod

N = INT()
a = [INT() for _ in range(N)]

sum_a = sum(a)
dp = [[0]*(sum_a+1) for _ in range(N+1)]
dp[0][0] = 1

dp2 = [[0]*(sum_a+1) for _ in range(N+1)]
dp2[0][0] = 1

for i, x in enumerate(a):
	for j in range(sum_a+1):
		if j+x >= sum_a+1:
			continue
		dp[i+1][j] = (dp[i+1][j] + dp[i][j]*2)%mod # 赤以外に塗り分ける
		dp[i+1][j+x] = (dp[i+1][j+x] + dp[i][j])%mod # 赤に塗り分ける
		dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j])%mod
		dp2[i+1][j+x] = (dp2[i+1][j+x] + dp2[i][j])%mod
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	print((power(3, N)-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2])+3*dp2[N][sum_a//2])%mod)
else:
	print((power(3, N)-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2+1]))%mod)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

def power(x, y):
   if y == 0:
       return 1
   elif y == 1:
       return x % mod
   elif y % 2 == 0:
       return power(x, y/2) ** 2 % mod
   else:
       return power(x, (y-1)/2) ** 2 * x % mod

N = INT()
a = np.array([INT() for _ in range(N)])

sum_a = np.sum(a)
dp = np.zeros((N+1, sum_a+1))
dp[0][0] = 1

dp2 = np.zeros((N+1, sum_a//2+1))
dp2[0][0] = 1

for i, x in enumerate(a):
	dp[i+1, :] += dp[i, :]*2 % mod # 赤以外に塗り分ける
	dp[i+1, x:] += dp[i, :-x] % mod # 赤に塗り分ける
	dp2[i+1,:] += dp2[i, :] % mod
	dp2[i+1, x:] += dp2[i, :-x] % mod
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2:])+3*dp2[N,sum_a//2])%mod))
else:
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2+1:]))%mod))
### BUGGY CODE ###

s=input()
ans1=len(s)
for i in range(10**5):
	s1=s.replace('01', '').replace('10', '')
	if s==s1:
		break
	s=s1
ans2=len(s)
print(ans1-ans2)

### FIXED CODE ###

S = input()

num_0 = S.count('0')
num_1 = S.count('1')

print(min(num_0, num_1)*2)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = str(input())
l = []
r = []
for i in range(Q):
    l,r = map(int,input().split())
    ans = S.count('AC',l-1,r)
    print(ans)


### FIXED CODE ###

N,Q = map(int,input().split())
S = str(input())
cumulative_sum = [0,0]
cont = 0
for i in range(1,N):
    if S[i-1] == 'A' and S[i] == 'C':
        cont += 1
    cumulative_sum.append(cont)
for i in range(Q):
    l,r = map(int,input().split())
    print(cumulative_sum[r]-cumulative_sum[l])
### BUGGY CODE ###

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

h = (n//2)-1
for i in range(n):
  x = s[:i]+s[i+1:]
  sx = sorted(x)
  print(sx[h])

### FIXED CODE ###

n = int(input())
s = list(map(int, input().split()))
sx = sorted(s)
a = sx[(n//2)-1]
b = sx[n//2]
for i in s:
  if i <= a:
    print(b)
  else:
    print(a)
### BUGGY CODE ###

from itertools import permutations
MAX = 10 ** 9
def warshall_floyd(n, dist):
    for k in range(n):
        for i in range(n-1):
            for j in range(i, n):
                dist[i][j] = dist[j][i] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
E = [[MAX] * N for _ in range(N)]
for i in range(N):
    E[i][i] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a][b] = c
    E[b][a] = c
E = warshall_floyd(N, E)
res = MAX
for p in permutations(r):
    tmp = 0
    for i in range(R-1):
        tmp += E[p[i]-1][p[i+1]-1]
    res = min(res, tmp)
print(res)

### FIXED CODE ###

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

def warshallFloyd():
    for k in range(N):
        for i in range(N-1):
            for j in range(i, N):
                tmp = min(E[i][j], E[i][k] + E[k][j])
                E[i][j] = E[j][i] = tmp

def dfs(c, p, d):
    if c == R:
        ans[0] = min(ans[0], d)
        return
    for i in range(R):
        if used[i]:
            continue
        used[i] = True
        if p == -1:
            dfs(c+1, i, 0)
        else:
            dfs(c+1, i, d + E[S[p]-1][S[i]-1])
        used[i] = False

N, M, R = map(int, input().split())
S = list(map(int, input().split()))
E = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    E[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a][b] = E[b][a] = c
warshallFloyd()
ans = [float('inf')]
used = [False] * R
dfs(0, -1, 0)
print(*ans)
### BUGGY CODE ###

s = input()
q = int(input())
tmp = s
for _ in range(q):
    _s = input()
    t = 0
    f = 0
    c = ""
    if _s == "1":
        tmp = tmp[::-1]
    else:
        t, f, c = _s.split(" ")
        if f == "1":
            tmp = c + tmp
        else:
            tmp = tmp + c
print(tmp)
        

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
tmp = deque()
for i in range(len(s)):
    tmp.append(s[i])
flag = 0
for _ in range(q):
    _s = input()
    if _s == "1":
        flag += 1
    else:
        t, f, c = _s.split(" ")
        r = flag % 2
        if f == "1" and r == 0:
            #tmp = c + tmp
            tmp.appendleft(c)
        elif f == "1" and r == 1:
            #tmp = tmp + c
            tmp.append(c)
        elif f == "2" and r == 0:
            #tmp = tmp + c
            tmp.append(c)
        elif f == "2" and r == 1:
            #tmp = c + tmp
            tmp.appendleft(c)
if flag % 2 == 0:
    for i in range(len(tmp)):
        print(tmp.popleft(), end="")
else:
    for i in range(len(tmp)):
        print(tmp.pop(), end="")
### BUGGY CODE ###

n,m = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(m)]
di = [[] for _ in range(n)]
for i in range(m):
    di[ls[i][0]-1].append(ls[i][1])
for j in range(n):
    di[j].sort()
for k in range(m):
    a = di[ls[k][0]-1].index(ls[k][1])
    print(str(ls[k][0]).rjust(6,"0")+str(a+1).rjust(6,"0"))
    


### FIXED CODE ###

n,m = map(int,input().split())
ls = [[] for _ in range(n+1)]
di = []
for i in range(m):
    a,b = map(int,input().split())
    ls[a].append([b,i+1])
for j in range(n+1):
    if ls[j] != []:
        ls[j].sort(key=lambda x :x[0])
        for k in range(len(ls[j])):
            di.append([ls[j][k][1],str(10**12+j*10**6+k+1)[1:]])
di.sort(key=lambda x :x[0])
for l in range(m):
    print(di[l][1])
### BUGGY CODE ###

from itertools import combinations
N = int(input())
S = list(input().strip())
d = {}
for c in S:
  if c in d.keys():
    d[c] += 1
  else:
    d[c] = 1
ans = 0
for i in range(1, len(d.keys())+1):
  for com in combinations(d.keys(),i):
    tmp = 1
    for c in com:
      tmp *= d[c]
    ans += tmp
    ans %= 10**9+7
print(ans) 



### FIXED CODE ###

from itertools import combinations
N = int(input())
S = list(input().strip())
d = {}
for c in S:
  if c in d.keys():
    d[c] += 1
  else:
    d[c] = 1
ans = 0
for n in d.values():
  ans = (ans+n+ans*n)%(10**9+7)
print(ans)
### BUGGY CODE ###

from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        prev = now
# print(edges)
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
for V in vs:
    if used[V]: continue
    used[V] = 1
    q = deque([V])
    while len(q) > 0:
        v = q.popleft()
        for u in edges[v]: 
            used[u] = max(used[u], used[v] + 1)
            q.append(u)
print(max(used))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(input())
X = 10000
INF = 1 << 50
edges = defaultdict(list)
edges_r = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in G.keys():
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print(-1)
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        edges_r[now].append(prev)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
# for V in vs:
#     if used[V]: continue
#     used[V] = 1
#     q = deque([V])
#     while len(q) > 0:
#         v = q.popleft()
#         for u in edges[v]: 
#             if used[u] <= used[v]:
#                 q.append(u)
#                 used[u] = max(used[u], used[v] + 1)

for V in vs:
    if used[V]:continue
    used[V] = 1
    mx = 1
    for b in edges_r[V]:
        mx = max(mx, used[b]+1)
    used[V] = mx
# print(used)
print(max(used))
### BUGGY CODE ###

N, W = map(int, input().split())

value = [[0 for i in range(W + 1)] for j in range(N + 1)]
for i in range(1, N + 1):
    w, v = map(int, input().split())

    for j in range(W + 1):
        if j - w >= 0:
            value[i][j] = max(value[i-1][j-w] + v, value[i-1][j])
        else:
            value[i][j] = value[i-1][j]

print(value[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
V = 10**5
weight = [[float("inf") for i in range(V + 1)] for j in range(N + 1)]
weight[0][0] = 0
for i in range(1, N + 1):
    w, v = map(int, input().split())

    for j in range(V + 1):
        if j - v >= 0:
            weight[i][j] = min(weight[i-1][j-v] + w, weight[i-1][j])
        else:
            weight[i][j] = weight[i-1][j]

ans = 0
for j in range(V + 1):
    if weight[N][j] <= W:
        ans = max(ans, j)

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

import numpy as np
n,mondaisuu=map(int,input().split())
s=input()
li=np.zeros(n)
for i in range(n-1):
  if s[i]=="A" and s[i+1]=="C":
    li[i]=1
for i in range(mondaisuu):
  l,r=map(int,input().split())
  print(int(np.sum(li[l-1:r-1])))

### FIXED CODE ###

n,mondaisuu=map(int,input().split())
s=input()
dp=[0]*n
for i in range(1,n):
  dp[i]=dp[i-1] + (1 if s[i]=="C" and s[i-1]=="A" else 0)
for i in range(mondaisuu):
  l,r=map(int,input().split())
  print(dp[r-1]-dp[l-1])
### BUGGY CODE ###

#!/usr/bin/env python3
#dp5 #Knapsack 2
#個数制限ありナップサック
#1≤W≤10**9

def e():
    n,W = map(int,input().split())
    wv = [list(map(int,input().split())) for _ in range(n)]
    #横:価値　縦:品物
    dp = [[float("inf") for _ in range(10**5+1)] for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(1,n+1):
        for j in range(10**5+1):
            #i番目の品物の価値より価値の制限が小さいとき(i番目の品物が使えないとき)
            if j < wv[i-1][1]:
                #i-1番目の品物の重さと同じ
                dp[i][j] = dp[i-1][j]
            else:
                #i番目の品物を使い、重さを追加する場合と使わない場合の重さを比較
                dp[i][j] = min(dp[i-1][j],dp[i-1][j - wv[i-1][1]] + wv[i-1][0])
    ans = 0
    #重さWまでの価値最大値
    for i in range(10**5+1):
        if dp[n][i] <= W:
            ans = i
    print(ans)
if __name__ == '__main__':
    e()


### FIXED CODE ###

#!/usr/bin/env python3
#dp5 #Knapsack 2
#個数制限ありナップサック
#1≤W≤10**9

def e():
    n,W = map(int,input().split())
    wv = [list(map(int,input().split())) for _ in range(n)]
    #横:価値　縦:品物
    dp = [[float("inf") for _ in range(10**5+1)] for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(1,n+1):
        for j in range(10**5+1):
            #i番目の品物の価値より価値の制限が小さいとき(i番目の品物が使えないとき)
            if j < wv[i-1][1]:
                #i-1番目の品物の重さと同じ
                dp[i][j] = dp[i-1][j]
            else:
                #i番目の品物を使い、重さを追加する場合と使わない場合の重さを比較
                dp[i][j] = min(dp[i-1][j],dp[i-1][j - wv[i-1][1]] + wv[i-1][0])
    ans = 0
    #重さWまでの価値最大値
    for i in range(10**5+1):
        if dp[n][i] <= W:
            ans = i
    print(ans)
if __name__ == '__main__':
    e()
### BUGGY CODE ###

a,b,x = list(map(int,input().split()))
i = a
count = 0
while i <= b:
	if i % x == 0 :
		count += 1
		i += 1
	else :
		i += 1
print(count)

### FIXED CODE ###

a,b,x = map(int,input().split())
print((b // x) - (a-1) // x)
### BUGGY CODE ###

from collections import deque
n =int(input())
a = []
takahashi = 0
aoki = 0
for i in range(n):
 tmp1,tmp2 = (int(i) for i in input().split())
 a.append([tmp1,tmp2])
a2 = sorted(a, key=lambda x: x[0])
a3 = sorted(a, key=lambda x: x[1])
d = deque(a2)
start = 0
for i in range(n):
 if start%2 == 0:
  d = sorted(d, key=lambda x: x[0])
  a,b =d.pop()
  takahashi += a
  #print(d)
 if start %2 == 1:
  d = sorted(d, key=lambda x: x[1])
  a,b = d.pop()
  aoki += b
  #print(d)
 start += 1
print(takahashi -aoki)

### FIXED CODE ###

from collections import deque
n =int(input())
takahashi = 0
aoki = 0
ab = []
a = []
for i in range(n):
 tmp1,tmp2 = (int(i) for i in input().split())
 a.append([tmp1,tmp2])
 ab.append(tmp1+tmp2)
 aoki += tmp2
#a2 = sorted(a, key=lambda x: x[0])
#a3 = sorted(a, key=lambda x: x[1])
ab = sorted(ab,reverse = True)
start = 0
for i in range(n):
  if i%2 == 0:
    takahashi += ab[i]
  else:
    continue


print(takahashi-aoki)
### BUGGY CODE ###

import numpy as np

def main():
	H,W = map(int,input().split())
	dis_list1 = []
	dis_list2 = []
	for i in range(H):
		st = input()
		dis_list1.append([0 if i == "#" else 1 for i in list(st)])
		dis_list2.append([0 if i == "#" else 1 for i in list(st)])
	w_list = dis_list1
	h_list = dis_list2
	for i in range(H):
		for j in range(W-1):
			if w_list[i][j+1] != 0:
				w_list[i][j+1] = w_list[i][j]+1
	for i in range(H):
		for j in range(W-1):
			if w_list[i][-j-2] != 0 and w_list[i][-j-1] != 0:
				w_list[i][-j-2] = w_list[i][-j-1]

	for i in range(W):
		for j in range(H-1):
			if h_list[j+1][i] != 0:
				h_list[j+1][i] = h_list[j][i]+1
	for i in range(W):
		for j in range(H-1):
			if h_list[-j-2][i] != 0 and h_list[-j-1][i] != 0:
				h_list[-j-2][i] = h_list[-j-1][i]

	w_list = np.array(w_list)
	h_list = np.array(h_list)

	sum_list = w_list+h_list

	print(sum_list.max()-1)		

if __name__ == "__main__":
	main()

### FIXED CODE ###

#import sys
#input = sys.stdin.buffer.readline
import numpy as np

def main():
    H,W = map(int,input().split())
    S = np.array([list(input()) for _ in range(H)]) == '.'

    up = np.zeros((H,W), dtype=int)
    down = np.zeros((H,W), dtype=int)
    left = np.zeros((H,W), dtype=int)
    right = np.zeros((H,W), dtype=int)
    
    for i in range(H-1):
        up[i+1,:] = (up[i,:] + 1) * S[i,:]
    for i in range(H-1):
        down[-i-2,:] = (down[-i-1,:] + 1) * S[-i-1,:]
    for i in range(W-1):
        left[:,i+1] = (left[:,i] + 1) * S[:,i]
    for i in range(W-1):
        right[:,-i-2] = (right[:,-i-1] + 1) * S[:,-i-1]
        
    print(((up+down+left+right)*S).max()+1)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
print(sum([A[i] * A[j] for i in range(N - 1) for j in range(i + 1, N)]) % (10 ** 9 + 7))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
T = sum(A)
ans = 0
for i in range(N):
  T -= A[i]
  ans += A[i] * T
  ans %= 10 ** 9 + 7
print(ans)
### BUGGY CODE ###

import sys





def main():
    def mkns(a,s,m):
        if a==0:
            return s
        else:
            return (((s+1)<<a)|s) & m
    def biser(lst,func):
            n=len(lst)
            nh=n//2
            if n==1:
                if func(lst[0]):
                    return lst[0]
                else:
                    return -1
            if func(lst[nh]):
                return biser(lst[nh:],func)
            else:
                return biser(lst[:nh],func)
    
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i): 
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    for i in range(N):
         if a[i]>=K:
             break
         ss[i+1]=mkns(a[i],ss[i],pm)
         if isunnec(i):
             nn+=1
    print(nn)

if __name__=='__main__':
    main()



### FIXED CODE ###

#4 9
#1 3 5 6
#の時に1（正解は0）と出力されるがACになる

N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)
### BUGGY CODE ###

def popcount(x):
    return bin(x).count("1")

N, X = open(0).read().split()
N = int(N)
XS = list(X)
X = int(X, 2)

p = popcount(X)
if p == 0:
    xi = xd = 0
elif p == 1:
    xi = X % 2
    xd = 0
else:
    xi = X % (p + 1)
    xd = X % (p - 1)

for i in range(0, N):
    if XS[i] == "1":
        if p == 1:
            print(0)
            continue
        else:
            k = 1 << (N - 1 - i)
            x = (xd - k) % (p - 1)
    else:
        k = 1 << (N - 1 - i)
        x = (xi + k) % (p + 1)
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)

### FIXED CODE ###

def popcount(x):
    return bin(x).count("1")

N, X = open(0).read().split()
N = int(N)
XS = list(X)
X = int(X, 2)

p = popcount(X)
xi = X % (p + 1)
if p == 1:
    xd = 0
else:
    xd = X % (p - 1)

for i in range(N):
    if XS[i] == "1":
        if p == 1:
            print(0)
            continue
        else:
            k = pow(2, N - 1 - i, p - 1)
            x = (xd - k) % (p - 1)
    else:
        k = pow(2, N - 1 - i, p + 1)
        x = (xi + k) % (p + 1)
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)
### BUGGY CODE ###

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

rl = []

for i in range(k-1,n):
  j = 0
  r = 1
  for j in range(k):
    r = r * a[i-j]
    j += 1
  rl.append(r)
  i += 1

for m in range(n-k):
  if rl[m+1] > rl[m]:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

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

for i in range(k,n):
  if a[i] > a[i-k]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,Q = inpl()

lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    a,b = a-1,b-1
    lines[a].add(b)
    lines[b].add(a)

adds = [0]*N
for _ in range(Q):
    p,x = inpl()
    adds[p-1] += x

visited = [False]*N
ans = [0]*N

def dfs(x,cnt):
    global visited
    global ans

    if visited[x]:
        return
    else:
        visited[x] = True
        cnt += adds[x]
        ans[x] = cnt
        for t in lines[x]:
            dfs(t,cnt)


dfs(0,0)

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


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,Q = inpl()

lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    a,b = a-1,b-1
    lines[a].add(b)
    lines[b].add(a)

adds = [0]*N
for _ in range(Q):
    p,x = inpl()
    adds[p-1] += x

visited = [False]*N
ans = [0]*N

q = queue.LifoQueue()
q.put([0,0])

while not q.empty():
    x,cnt = q.get()
    visited[x] = True
    cnt += adds[x]
    ans[x] += cnt
    for t in lines[x]:
        if not visited[t]:
            q.put([t,cnt])

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