CodeEff/ECCO huggingface dataset:
# Original solution
def solve():
    from itertools import accumulate

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

    e = tuple([] for _ in range(4))
    w1, v1 = list(map(int, input().split()))
    e[0].append(v1)

    for _ in range(N - 1):
        _w, _v = list(map(int, input().split()))
        e[_w - w1].append(_v)

    g = [None for _ in range(4)]
    for j in range(4):
        e[j].sort(reverse=True)
        g[j] = (0,) + tuple(accumulate(e[j]))

    ret = 0
    for a in range(len(e[0]) + 1):
        for b in range(len(e[1]) + 1):
            for c in range(len(e[2]) + 1):
                diff = W - (w1 * a + (w1 + 1) * b + (w1 + 2) * c)
                if diff < 0:
                    break
                d = min(len(e[3]), diff // (w1 + 3))
                ret = max(ret, g[0][a] + g[1][b] + g[2][c] + g[3][d])
    return ret


print((solve()))

# https://atcoder.jp/contests/arc073/submissions/2794675
# https://atcoder.jp/contests/arc073/submissions/7328854


# Optimized solution
def main():
    N, W = list(map(int, input().split()))
    ctr = [0] * 4
    goods = [[] for _ in range(4)]

    w1, v1 = list(map(int, input().split()))
    ctr[0] += 1
    goods[0].append(v1)

    for _ in range(N - 1):
        wi, vi = list(map(int, input().split()))
        wi -= w1
        ctr[wi] += 1
        goods[wi].append(vi)

    for i in range(4):
        goods[i].sort(reverse=True)

    def accumulate(a):
        s = 0
        yield s
        for x in a:
            s += x
            yield s

    accs = [list(accumulate(goods_i)) for goods_i in goods]

    ans = -1
    for c0 in range(N + 1):
        if ctr[0] < c0: break
        if w1 * c0 > W: break

        v0 = accs[0][c0]
        for c1 in range(N - c0 + 1):
            if ctr[1] < c1: break
            if w1 * c0 + (w1 + 1) * c1 > W: break

            v1 = v0 + accs[1][c1]
            for c2 in range(N - c0 - c1 + 1):
                if ctr[2] < c2: break
                if w1 * c0 + (w1 + 1) * c1 + (w1 + 2) * c2 > W: break

                v2 = v1 + accs[2][c2]
                for c3 in range(N - c0 - c1 - c2 + 1):
                    if ctr[3] < c3: break
                    if w1 * c0 + (w1 + 1) * c1 + (w1 + 2) * c2 + (w1 + 3) * c3 > W: break
                    v3 = v2 + accs[3][c3]
                    ans = max(ans, v3)

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())
# Original solution
# -*- coding: utf-8 -*-
n,W = list(map(int, input().split()))
iw,v = list(map(int, input().split()))
d = {
    0: [v]
    ,1: []
    ,2: []
    ,3: []
}
for _ in range(1,n):
    w,v = list(map(int,input().split()))
    d[w-iw].append(v)

for i in range(4):
    d[i] = sorted(d[i], reverse=True)

ret = -1
for i in range(n+1):
    if i*iw>W:
        break
    for j in range(n-i+1):
        if i*iw+j*(iw+1)>W:
            break
        for k in range(n-(i+j)+1):
            if i*iw+j*(iw+1)+k*(iw+2)>W:
                break
            for l in range(n-(i+j+k)+1):
                if i*iw+j*(iw+1)+k*(iw+2)+l*(iw+3)>W:
                    continue
                V = sum(d[0][:i])+sum(d[1][:j])+sum(d[2][:k])+sum(d[3][:l])
                ret = max(ret, V)
print(ret)


# Optimized solution
# -*- coding: utf-8 -*-
n,W = list(map(int, input().split()))
iw,v = list(map(int, input().split()))
d = {
    0: [v]
    ,1: []
    ,2: []
    ,3: []
}
for _ in range(1,n):
    w,v = list(map(int,input().split()))
    d[w-iw].append(v)

for i in range(4):
    d[i] = sorted(d[i], reverse=True)

ret = -1
for i in range(min(n,len(d[0]))+1):
    if i*iw>W:
        break
    for j in range(min(n-i,len(d[1]))+1):
        if i*iw+j*(iw+1)>W:
            break
        for k in range(min(n-(i+j),len(d[2]))+1):
            if i*iw+j*(iw+1)+k*(iw+2)>W:
                break
            for l in range(min(n-(i+j+k),len(d[3]))+1):
                if i*iw+j*(iw+1)+k*(iw+2)+l*(iw+3)>W:
                    continue
                V = sum(d[0][:i])+sum(d[1][:j])+sum(d[2][:k])+sum(d[3][:l])
                ret = max(ret, V)
print(ret)
# Original solution
INFTY = 10**10
N,W = list(map(int,input().split()))
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(3*(N-1)+1)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*(N-1)+1):
            dp[i][j][k] = dp[i-1][j][k]
            if k>=X[i-1][0]-X[0][0]:
                dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
cmax = 0
for j in range(1,N+1):
    for k in range(3*(N-1)+1):
        if j*X[0][0]+k<=W:
            cmax = max(cmax,dp[N][j][k])
print(cmax)

# Optimized solution
N,W = list(map(int,input().split()))
A = [list(map(int,input().split())) for _ in range(N)]
w1 = A[0][0]
C = {0:[],1:[],2:[],3:[]}
for i in range(N):
    w,v = A[i]
    C[w-w1].append(v)
C[0] = sorted(C[0],reverse=True)
C[1] = sorted(C[1],reverse=True)
C[2] = sorted(C[2],reverse=True)
C[3] = sorted(C[3],reverse=True)
n0 = len(C[0])
n1 = len(C[1])
n2 = len(C[2])
n3 = len(C[3])
vmax = 0
for a0 in range(n0+1):
    for a1 in range(n1+1):
        for a2 in range(n2+1):
            for a3 in range(n3+1):
                if a0*w1+a1*(w1+1)+a2*(w1+2)+a3*(w1+3)<=W:
                    v = sum(C[0][:a0])+sum(C[1][:a1])+sum(C[2][:a2])+sum(C[3][:a3])
                    vmax = max(vmax,v)
print(vmax)
# Original solution
from itertools import accumulate
n,W,*L=list(map(int,open(0).read().split()))
l=[[] for _ in range(4)]
lim=[1]*4
m=min(L[::2])
for w,v in zip(*[iter(L)]*2):
	l[w-m].append(v)
	lim[w-m]+=1
ll=[]
for x in l:
	ll.append([0]+list(accumulate(sorted(x)[::-1])))
ans=0
for i in range(lim[0]):
	for j in range(lim[1]):
		for k in range(lim[2]):
			for l in range(lim[3]):
				if m*i+(m+1)*j+(m+2)*k+(m+3)*l>W:
					continue
				ans=max(ans,ll[0][i]+ll[1][j]+ll[2][k]+ll[3][l])
print(ans)

# Optimized solution
from itertools import accumulate
n,W,*L=list(map(int,open(0).read().split()))
l=[[] for _ in range(4)]
lim=[1]*4
m=min(L[::2])
for w,v in zip(*[iter(L)]*2):
	l[w-m].append(v)
	lim[w-m]+=1
ll=[]
for x in l:
	ll.append([0]+list(accumulate(sorted(x)[::-1])))
ans=0
for i in range(lim[0]):
	if m*i>W:
		continue
	for j in range(lim[1]):
		if m*i+(m+1)*j>W:
			continue
		for k in range(lim[2]):
			if m*i+(m+1)*j+(m+2)*k>W:
				continue
			for l in range(lim[3]):
				if m*i+(m+1)*j+(m+2)*k+(m+3)*l>W:
					continue
				ans=max(ans,ll[0][i]+ll[1][j]+ll[2][k]+ll[3][l])
print(ans)
# Original solution
N, constW = list(map(int, input().split()))
WV = [list(map(int, input().split())) for _ in range(N)]
W0 = WV[0][0]
L = [[] for _ in range(4)]
for w, v in WV:
  w -= W0
  L[w].append(v)
L[0].sort(reverse=True)
L[1].sort(reverse=True)
L[2].sort(reverse=True)
L[3].sort(reverse=True)
ans = 0
for i in range(1, constW//W0 + 1):
  rest = constW - i*W0
  for j in range(min(rest//3, i) + 1):
    rest1 = rest - 3*j
    for k in range(min(rest1//2, i-j) + 1):
      rest2 = rest1 - 2*k
      for l in range(min(rest2, i-j-k) + 1):
        temp = sum(L[3][:j]) + sum(L[2][:k]) + sum(L[1][:l]) + sum(L[0][:i-j-k-l])
        ans = max(ans, temp)
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline

def main():
  N, constW = list(map(int, input().split()))
  WV = [list(map(int, input().split())) for _ in range(N)]
  W0 = WV[0][0]
  L = [[] for _ in range(4)]
  for w, v in WV:
    w -= W0
    L[w].append(v)
  L[0].sort(reverse=True)
  L[1].sort(reverse=True)
  L[2].sort(reverse=True)
  L[3].sort(reverse=True)
  ans = 0
  for i in range(1, constW//W0 + 1):
    rest = constW - i*W0
    for j in range(min(rest//3, i) + 1):
      rest1 = rest - 3*j
      for k in range(min(rest1//2, i-j) + 1):
        rest2 = rest1 - 2*k
        for l in range(min(rest2, i-j-k) + 1):
          temp = sum(L[3][:j]) + sum(L[2][:k]) + sum(L[1][:l]) + sum(L[0][:i-j-k-l])
          ans = max(ans, temp)
  print(ans)

if __name__ == "__main__":
  main()
# Original solution
# -*- coding: utf-8 -*-
from itertools import accumulate, product
from operator import itemgetter

def inpl(): return tuple(map(int, input().split()))
N, W = inpl()
I = [inpl() for _ in range(N)]
w1 = I[0][0]
A = {w1 + x: [] for x in range(4)}

for w, v in I:
    A[w].append(v)

for k, v in list(A.items()):
    A[k] = [0] + list(accumulate(sorted(v, reverse=True)))

res = 0
g0 = itemgetter(0)
g1 = itemgetter(1)

for L in product(enumerate(A[w1]),
                 enumerate(A[w1+1]),
                 enumerate(A[w1+2]),
                 enumerate(A[w1+3])):
    if sum([(w1+i)*l for i, l in enumerate(map(g0, L))]) <= W:
        res = max(res, sum(map(g1, L)))

print(res)

# Optimized solution
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from itertools import accumulate, product
 
N, W = inpl()
A = []
for _ in range(N):
    A.append(inpl())
B = [[] for _ in range(4)]
w1 = A[0][0]
 
for w, v in A:
    B[w-w1].append(v)
 
B = [sorted(b, reverse=True) for b in B]
C = [[0] + list(accumulate(b)) for b in B]
 
res = 0

for L in product(enumerate(C[0]),
                 enumerate(C[1]),
                 enumerate(C[2]),
                 enumerate(C[3])):
    if sum([(w1+i)*l[0] for i, l in enumerate(L)]) <= W:
        res = max(res, sum([l[1] for l in L]))

print(res)
# Original solution
n, w = list(map(int, input().split()))

dp = [[[-1]*4*n for j in range(n+1)] for i in range(n+1)]
dp[0][0][0] = 0
w1 = None
for i in range(n):
    ws, vs = list(map(int, input().split()))
    if i == 0:
        w1 = ws
    ws -= w1
    for j in range(i+2):
        for k in range(4*n):
            if j-1 >= 0 and k-ws >= 0 and dp[i][j-1][k-ws] >= 0:
                dp[i+1][j][k] = max(dp[i][j][k], dp[i][j-1][k-ws]+vs)
            else:
                dp[i+1][j][k] = dp[i][j][k]

ans = 0
for j in range(n+1):
    for k in range(4*n):
        if w1*j + k <= w:
            ans = max(ans, dp[-1][j][k])
print(ans)


# Optimized solution
n,w = list(map(int, input().split()))
w4 = [[] for i in range(4)]
w1 = None
for i in range(n):
    ws, vs = list(map(int,input().split()))
    if i == 0:
        w1 = ws
    ws -= w1
    w4[ws].append(vs)

for i in range(4):
    w4[i].sort(reverse=True)
    tmp = [0]
    for j in w4[i]:
        tmp.append(tmp[-1]+j)
    w4[i] = tmp
ans = 0
for i in range(len(w4[0])):
    for j in range(len(w4[1])):
        for k in range(len(w4[2])):
            for l in range(len(w4[3])):
                if w >= w1*(i+j+k+l) + j + 2*k + 3*l:
                    ans = max(ans, w4[0][i]+w4[1][j]+w4[2][k]+w4[3][l])
print(ans)
# Original solution
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import defaultdict
import sys
N_MAX = 100
W_MAX = 10**9
V_MAX = 10**7
INF = 10**10
def main(N, W, items):
    dp = defaultdict(lambda: INF)
    dp[0] = 0
    for i in range(N):
        iw, iv = items[i]
        for v, w in list(dp.items()):
            if w + iw <= W:
                dp[v + iv] = min(dp[v + iv], w + iw)
    print((max(dp.keys())))

if __name__ == '__main__':
    input = sys.stdin.readline
    N, W = list(map(int, input().split()))
    items = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, items)


# Optimized solution
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, W, items):
    w1 = items[0][0]
    dp = [[[0] * (3 * N + 1) for _ in range(N + 1)] for __ in range(N + 1)]
    dp[0][0][0] = 0
    for i in range(N):
        iw, iv = items[i]
        iw -= w1
        for j in range(N + 1):
            for w in range(3 * N + 1):
                if j * w1 + w > W: break
                if w >= iw and j >= 1:
                    dp[i + 1][j][w] = max(dp[i][j][w], dp[i][j - 1][w - iw] + iv)
                else:
                    dp[i + 1][j][w] = dp[i][j][w]
    ans = 0
    for j in range(N + 1):
        for w in range(3 * N + 1):
            ans = max(ans, dp[N][j][w])
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, W = list(map(int, input().split()))
    items = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, items)
# Original solution
from collections import defaultdict

n, wmax = list(map(int, input().split()))
dp = [defaultdict(int) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    w, v = list(map(int, input().split()))
    if i == 0:
        w0 = w
    for j in range(n+1):
        for k in range(300):
            weight = j*w0+k
            if weight <= wmax:
                if weight - w >= 0:
                    dp[i+1][weight] = max(dp[i+1][weight], dp[i][weight - w] + v)
                dp[i+1][weight] = max(dp[i+1][weight], dp[i][weight])

print((max(list(dp[-1].values()))))


# Optimized solution
from collections import defaultdict

n, wmax = list(map(int, input().split()))
dp = [defaultdict(int) for _ in range(2)]
dp[0][0] = 0
for i in range(n):
    w, v = list(map(int, input().split()))
    if i == 0:
        w0 = w
    dp[(i+1)%2] = defaultdict(int)
    for j in range(n+1):
        for k in range(300):
            weight = j*w0+k
            if weight <= wmax:
                if weight - w >= 0:
                    dp[(i+1)%2][weight] = max(dp[(i+1)%2][weight], dp[i%2][weight - w] + v)
                dp[(i+1)%2][weight] = max(dp[(i+1)%2][weight], dp[i%2][weight])

print((max(list(dp[n%2].values()))))
# Original solution
from sys import stdin,setrecursionlimit

n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値(ときどき逆になることがあるので注意)
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])
print((knapsack(n,w,li)))

# Optimized solution
from sys import stdin,setrecursionlimit

n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]

jw = li[0][0]
omosa = [[] for _ in range(4)]

for i in li:
    omosa[i[0]-jw].append(i[1])

for i in range(len(omosa)):
    omosa[i].sort(reverse = True)

saidai = n
ma = 0

for i in range(len(omosa[0])+1):
    for j in range(len(omosa[1])+1):
        for k in range(len(omosa[2])+1):
            for l in range(len(omosa[3])+1):
                to_ka = omosa[0][:i]+omosa[1][:j]+omosa[2][:k]+omosa[3][:l]
                if i*jw+j*(jw+1)+k*(jw+2)+l*(jw+3) > w:
                    continue
                ma = max(ma,sum(to_ka))

print(ma)
# Original solution
def String2List(s):
    L = []
    flag = True
    l = len(s)
    for i in range(l):
        if s[i].isdigit() and flag:
            t = ""
            j = 0
            while s[i+j].isdigit():
                t += s[i+j]
                if i+j == l-1:
                    break
                j += 1
            L.append(t)
            flag = False
 
        elif not s[i].isdigit():
            L.append(s[i])
            flag = True
 
    return L
 

def RPN_list(L):
    S, L2 = [], []
    table = {"*": 1, "/": 1, "+": 0, "-": 0, "(": -1, ")": -1}
    for i in L:
        if i.isdigit():
            L2.append(i)
        elif i == "(":
            S.append(i)
        elif i == ")":
            while S[-1] != "(":
                L2.append(S.pop())
            S.pop()
        else:
            while len(S) != 0 and (table[S[-1]] >= table[i]):
                L2.append(S.pop())
            S.append(i)
 
    while len(S) != 0:
        L2.append(S.pop())
 
    return L2
 
 
def RPN_cal(L):
    St = []
 
    for i in L:
        if i == '+':
            St.append(int(St.pop()) + int(St.pop()))
        elif i == '-':
            St.append(-int(St.pop()) + int(St.pop()))
        elif i == '*':
            St.append(int(St.pop()) * int(St.pop()))
        elif i == '/':
            a = int(St.pop())
            b = float(St.pop())
            St.append(b/a)
        else:
            St.append(i)
 
    return St[0]
 
 
N = int(input())
 
for i in range(N):
    s = input()
    L = String2List(s[:-1])
    L = RPN_list(L)
    print(int(RPN_cal(L)))

# Optimized solution
def String2List(s):
    L = []
    flag = True
    l = len(s)
    for i in range(l):
        if s[i].isdigit() and flag:
            t = ""
            j = 0
            while s[i+j].isdigit():
                t += s[i+j]
                if i+j == l-1:
                    break
                j += 1
            L.append(t)
            flag = False

        elif not s[i].isdigit():
            L.append(s[i])
            flag = True

    return L


def Generate_RPN(L):
    S, L2 = [], []
    table = {"*": 1, "/": 1, "+": 0, "-": 0, "(": -1, ")": -1}
    for i in L:
        if i.isdigit():
            L2.append(i)
        elif i == "(":
            S.append(i)
        elif i == ")":
            while S[-1] != "(":
                L2.append(S.pop())
            S.pop()
        else:
            while len(S) != 0 and (table[S[-1]] >= table[i]):
                L2.append(S.pop())
            S.append(i)

    while len(S) != 0:
        L2.append(S.pop())

    return L2


def Calculate_RPN(L):
    St = []

    for i in L:
        if i == '+':
            St.append(int(St.pop()) + int(St.pop()))
        elif i == '-':
            St.append(-int(St.pop()) + int(St.pop()))
        elif i == '*':
            St.append(int(St.pop()) * int(St.pop()))
        elif i == '/':
            a = int(St.pop())
            b = float(St.pop())
            St.append(b/a)
        else:
            St.append(i)
 
    return St[0]


N = int(input())

for i in range(N):
    s = input()
    L = Generate_RPN(String2List(s[:-1]))
    print(int(Calculate_RPN(L)))
# Original solution
def divide(x, y):
    s = 1
    if(x < 0):s *= -1
    if(y < 0):s *= -1
    return abs(x) / abs(y) * s     

operator = {"+":(lambda x,y: x+y),
            "-":(lambda x,y: x-y),
            "*":(lambda x,y: x*y),
            "/":divide
            }

def ind(src, x):
    if x not in src:return 1<<30
    return src.index(x)
 
def _split(_src):
    c = 0
    l = len(_src)
    if l == 0:
        return []
    while c < l and ord('0') <= ord(_src[c]) <= ord('9'):
        c += 1

    if c == 0:
        return [_src[0]] + _split(_src[1:])
    else:
        return [int(_src[:c])] + _split(_src[c:])
         
 
def evaluate(src):
    if len(src) == 1:
        return src[0]
         
    if "(" in src:
        l = src.index("(")
        r = l
        st = 1
        while st:
            r += 1
            if src[r] == "(": st += 1
            if src[r] == ")": st -= 1
        
        mid = evaluate(src[l + 1:r])
        return evaluate( src[:l] + [mid] + src[r + 1:])
    
    if "*" in src or "/" in src:
        pos = min(ind(src, "*"), ind(src,"/"))
        op = src[pos]
        l, r = src[pos - 1], src[pos + 1]
        mid = operator[op](l, r)
        return evaluate(src[:pos - 1] + [mid] + src[pos + 2:])
    
    else:
        pos = min(ind(src, "+"), ind(src, "-"))
        op = src[pos]
        l, r = src[pos - 1], src[pos + 1]
        mid = operator[op](l, r)
        return evaluate(src[:pos - 1] + [mid] + src[pos + 2:])
     
for t in range(eval(input())):
    _src = input().strip("=")
    src = _split(_src)
    print(evaluate(src))

# Optimized solution
def divide(x, y):
    s = 1
    if(x < 0):s *= -1
    if(y < 0):s *= -1
    return abs(x) / abs(y) * s     

operator = {"+":(lambda x,y: x+y),
            "-":(lambda x,y: x-y),
            "*":(lambda x,y: x*y),
            "/":divide
            }

def ind(src, x):
    if x not in src:return 1<<30
    return src.index(x)
 
def _split(_src):
    c = 0
    l = len(_src)
    if l == 0:
        return []
    while c < l and ord('0') <= ord(_src[c]) <= ord('9'):
        c += 1

    if c == 0:
        return [_src[0]] + _split(_src[1:])
    else:
        return [int(_src[:c])] + _split(_src[c:])
         
 
def evaluate(src):
    if len(src) == 1:
        return src[0]
         
    if "(" in src:
        l = src.index("(")
        r = l
        st = 1
        while st:
            r += 1
            if src[r] == "(": st += 1
            if src[r] == ")": st -= 1
        
        mid = evaluate(src[l + 1:r])
        return evaluate( src[:l] + [mid] + src[r + 1:])
    
    pos = min(ind(src, "*"), ind(src,"/"))
    if(pos == 1<<30):
        pos = min(ind(src, "+"), ind(src, "-"))
    op = src[pos]
    l, r = src[pos - 1], src[pos + 1]
    mid = operator[op](l, r)
    return evaluate(src[:pos - 1] + [mid] + src[pos + 2:])

     
for t in range(eval(input())):
    _src = input().strip("=")
    src = _split(_src)
    print(evaluate(src))
# Original solution
base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl, with_array):
    dl = tl - pl
    tmp = []

    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.append(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.append(e)
    if with_array:
        return set(tmp), tmp
    else:
        return set(tmp)


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(eval(input()))
h = dict()
while q:
    p = [ord(c) for c in input().strip()]
    pl = len(p)
    if pl > tl:
        print((0))
        q -= 1
        continue
    if pl >= 10:
        keys_set, keys_array = calc_hash(p, 10, pl, with_array=True)
        keys0, keys1 = keys_array[0], keys_array[1:pl - 9]
        if pl not in h:
            hash_set, hash_array = h[10] = calc_hash(t, 10, tl, with_array=True)
        else:
            hash_set, hash_array = h[10]

        if keys_set.issubset(hash_set):
            for idx, hash in enumerate(hash_array):
                if keys0 == hash and hash_array[idx + 1:idx + pl - 9] == keys1:
                    print((1))
                    break
            else:
                print((0))
        else:
            print((0))
    else:
        key = calc_hash(p, pl, pl, with_array=False).pop() & mask
        if pl not in h:
            h[pl] = calc_hash(t, pl, tl, with_array=False)
        print((1 if key in h[pl] else 0))
    q -= 1

# Optimized solution
base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()

    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(eval(input()))
h = dict()
while q:
    p = [ord(c) for c in input().strip()]
    pl = len(p)
    if pl > tl:
        print((0))
        q -= 1
        continue
    bs = min(20, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    print((1 if keys.issubset(h[bs]) else 0))
    q -= 1
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
b=[];c=1;d=[]
for i in range(1,n):
  b.append(a[i]-a[i-1])
for j in range(1,n-1):
  if b[j]*b[j-1]<0 and j-1 not in d:
    c+=1
    d.append(j)
print(c)

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
b=[];c=1;d=-1
for i in range(1,n):
  if a[i]-a[i-1]<0:b.append(-1)
  elif a[i]-a[i-1]>0:b.append(1)
for j in range(1,len(b)):
  if b[j]*b[j-1]<0 and d!=j-1:
    c+=1
    d=j
print(c)
# Original solution
N = int(eval(input()))
sub = 0
count = 1
A = [int(i) for i in input().split()]
if N > 1:
	pre_num = A[1]
	pre_sub = A[1] - A[0]
for num in A[2:]:
    if not pre_num == num:
        if pre_sub * (num - pre_num) < 0:
            count += 1
            pre_sub = 0
        else:
          	pre_sub = num - pre_num
        pre_num = num
print(count)

# Optimized solution
_ = int(eval(input()))
A = [int(a) for a in input().split()]
selector = 0
count = 1
pre_a = A[0]
for a in A[1:]:
    if selector == 0:
        selector = a - pre_a
    elif selector * (a - pre_a) < 0:
        count += 1
        selector = 0
    pre_a = a
print(count)