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

import collections

N = input()
A = map(int, raw_input().split())
C = collections.Counter(A)
K = C.keys()
K.sort(reverse=1)
res = 0
for i in K:
    for j in xrange(60):
        p = 2 ** j
        if i > p:
            continue
        elif i == p:
            res += C[i] // 2
            C[i] = C[i] // 2 * 2
        else:
            num = min(C[i], C[p - i])
            res += num
            C[i] -= num
            C[p - i] -= num
print res


### FIXED CODE ###

import collections

N = input()
A = map(int, raw_input().split())
C = collections.Counter(A)
K = C.keys()
K.sort(reverse=1)
res = 0
for i in K:
    for j in xrange(60):
        p = 2 ** j
        if i <= p:
            break
    if i == p:
      res += C[i] // 2
      C[i] = C[i] // 2 * 2
    else:
      num = min(C[i], C[p - i])
      res += num
      C[i] -= num
      C[p - i] -= num
print res
### BUGGY CODE ###

from math import factorial
import itertools
N = int(input())
S = set([input() for i in range(N)])
march = set("MARCH")
S2 = [i for i in S if i[0] in march]

result = 0
for i in itertools.combinations(S2,3):
    if not (i[0][0]==i[1][0] or i[1][0]==i[2][0] or i[0][0]==i[2][0]):
        result += 1

print(result)



### FIXED CODE ###

from itertools import combinations
N = int(input())
S = set([input() for i8 in range(N)])
march = dict(zip("MARCH",[0,0,0,0,0]))

for i in S:
    if i[0] in march:
        march[i[0]] += 1

result = 0
for a,b,c in combinations(march.values(), 3):
    result += a*b*c
print(result)
### BUGGY CODE ###

h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=[input()for i in range(h)]
from heapq import heapify, heappop, heappush
from collections import defaultdict
seen=defaultdict(int)
gx-=1;gy-=1
hq=[(nx-1)*w+ny-1]
SIZE=h*w
while hq:
    d=heappop(hq)
    c,x,y=d//(h*w),d%(h*w)//w,d%(h*w)%w
    if seen[w*x +y]:continue
    seen[w*x +y]=1
    if x==gx and y==gy:print(c);exit()
    if x and seen[w*(x-1)+y]==0 and maze[x-1 ][y]!="#":
        heappush(hq,(c*SIZE+w*(x-1)+y))
    if y and  seen[w*x+y-1]==0 and maze[x][y-1]!="#":
        heappush(hq,(c*SIZE+w*x+y-1))
    if x+1<h  and  seen[w*(x+1)+y]==0 and maze[x+1][y]!="#":
        heappush(hq,(c*SIZE+w*(x+1)+y))
    if y+1<w  and seen[w*x+y+1 ]==0 and maze[x][y+1]!="#":
        heappush(hq,(c*SIZE+w*x+y+1))
    for i in range(max(0,x-2),min(h,x+3)):
        for j in range(max(0,y-2),min(w,y+3)):
            if i==x and j==y:continue
            if maze[i][j]=="."and  seen[w*i + j ]==0:
                heappush(hq,(c+1)*SIZE+w*i+j)

print(-1)

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=[input()for i in range(h)]
from heapq import heapify, heappop, heappush
seen=set()
gx-=1;gy-=1
SIZE=h*w
hq=[(nx-1)*w+ny-1]
while hq:
    d=heappop(hq)
    c,d=divmod(d,SIZE)
    x,y=divmod(d,w)
    if w*x +y in seen:continue
    seen.add(w*x +y)
    if x==gx and y==gy:print(c);exit()
    if x and w*(x-1)+y not in seen and maze[x-1 ][y]!=35:
        heappush(hq,(c*SIZE+w*(x-1)+y))
    if y and w*x+y-1 not in seen and maze[x][y-1]!=35:
        heappush(hq,(c*SIZE+w*x+y-1))
    if x+1<h  and w*(x+1)+y not in seen and maze[x+1][y]!=35:
        heappush(hq,(c*SIZE+w*(x+1)+y))
    if y+1<w  and w*x+y+1 not in seen and maze[x][y+1]!=35:
        heappush(hq,(c*SIZE+w*x+y+1))
    for i in range(max(0,x-2),min(h,x+3)):
        for j in range(max(0,y-2),min(w,y+3)):
            if i==x and j==y:continue
            if maze[i][j]==46 and w*i + j not in seen:
                heappush(hq,(c+1)*SIZE+w*i+j)

print(-1)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
A = np.array(A)
number = np.zeros(N, dtype = int)
for i in range(N):
  number[A[i]-1] += 1
total = 0
for k in range(N):
  total += number[k] * (number[k]-1) // 2
for j in range(N):
  print(total - number[A[j]-1] + 1)


### FIXED CODE ###

import numpy as np
from sys import stdin
input = stdin.readline
N = int(input())
A = list(map(int, input().split()))
number = np.zeros(N, dtype = int)
total = 0

dic = {}
a = sorted(A)
now_key = a[0]
value = 1
dic[now_key] = 1
for i in range(1,N):
  if a[i] == now_key:
    value += 1
  else:
    dic[now_key] = value
    if value >= 2:
      total += value * (value-1) // 2
    now_key = a[i]
    value = 1
dic[now_key] = value
if value >= 2:
  total += value * (value-1)//2
for j in A:
  print(total - dic[j] + 1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

n = int(input())
s = input()
s_set = set(s)
S = []
for i in s_set:
    S.append(s.count(i))

def cal(n, S):
    if n == 1:
        return sum(S)
    else:
        ans = 0
        for i in range(len(S) - n + 1):
            cross = cal(n-1, S[i+1:])
            ans += S[i] * cross
            ans %= 10 ** 9 + 7
        return ans % (10 ** 9 + 7)

ans = 0
for i in range(n):
    ans += cal(i+1, S)

ans %= 10 ** 9 + 7
print(ans)



### FIXED CODE ###

n = int(input())
s = input()
s_set = set(s)
S = []
for i in s_set:
    S.append(s.count(i))

ans = 1
for i in S:
    ans *= i + 1
    ans %= 10 ** 9 + 7

print(ans - 1)
### BUGGY CODE ###

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

def main():
    N = int(input())
    act = np.array([[int(item) for item in input().split()] for _ in range(N)])

    dp = np.zeros((2, 3), dtype='int64')
    selector = np.array([[0,1,1], [1,0,1], [1,1,0]])

    for i in range(0,N):
        for k in range(3):
            act_array = act[i][k]
            dp[i%2^1][k] = np.max(dp[i%2]*selector[k]) + act_array

        # print(dp)

    print(max(dp[N%2]))

main()

### FIXED CODE ###

N = int(input())
act = [[int(item) for item in input().split()] for _ in range(N)]

dp = [[0 for _ in range(3)] for _ in range(N+1)]

for i in range(N):
    for j in range(3):
        temp_hp = []
        for k in range(3):
            if k != j:
                temp_hp.append(dp[i-1][k] + act[i][j])
        dp[i][j] = max(temp_hp)
# print(dp)
print(max(dp[N-1]))
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
listx = [int(i) for i in input().split()]
listy = [int(i) for i in input().split()]
listz = [int(i) for i in input().split()]

import numpy as np
listxy = np.zeros([x*y,],dtype=np.int)
c = 0
for i in range(0,x):
    for j in range(0,y):
        listxy[c] = listx[i]+listy[j]
        c+=1

listxy.sort()
#print(listxy)
if x*y>k:
    listxy=listxy[-k:]
    listxyz =np.zeros([k*z,],dtype=np.int)
    c = 0
    for i in range(0,k):
        for j in range(0,z):
            listxyz[c] = listxy[i]+listz[j]
            c+=1
else:
    listxyz =np.zeros([x*y*z,],dtype=np.int)
    c = 0
    for i in range(0,x*y):
        for j in range(0,z):
            listxyz[c] = listxy[i]+listz[j]
            c+=1

listxyz.sort()

for i in range(0,k):
    print(listxyz[-(i+1)])

### 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)
A = A[0:K]
B.sort(reverse=True)
B = B[0:K]
AB = [a+b for a in A for b in B]

AB.sort(reverse=True)

AB = AB[0:K]

C.sort(reverse=True)
C=C[0:K]
ABC = [ab+c for ab in AB for c in C]

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
z = sum(a)
ans = 2000000000
for i in range(1, n):
    if abs(z - 2 * sum(a[0: i]))  < ans:
        ans = abs(z - 2 * sum(a[0: i]))
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
z = sum(a)
ln = []
x = 0
for i in range(n - 1):
    x += a[i]
    ln.append(abs(z - 2 * x))
print(min(ln))
### BUGGY CODE ###

S_split = input().split('?')
n = len(S_split) - 1
s = ''
output = ''
large = 0
count = 0
for i in range(2**n):
    s = S_split[0]
    for j in range(n):
        if ((i >> j) & 1) == 1:
            s = s + 'P' + S_split[j+1]
        else:
            s = s + 'D' + S_split[j+1]
    count = s.count('D') + s.count('PD')
    if  count >= large:
      large = count
      output = s
print(output)

### FIXED CODE ###

T = input()
print(T.replace('?', 'D'))
### BUGGY CODE ###

if __name__ == '__main__':
	n = int(input())
	lists = list()

	for i in range(n):
		a = int(input())
		lists.append(a)
	
	m = None

	for i in range(n - 1):
		j = max(lists[i + 1:n])
		m = j - lists[i] if m is None or m < j - lists[i] else m
	print(m)




### FIXED CODE ###

if __name__ == '__main__':
	n = int(input())
	lists = list()

	for i in range(n):
		a = int(input())
		lists.append(a)

	S = None
	while len(lists) > 1:
		mini = min(lists)
		mini_ind = lists.index(mini)
		l = len(lists)

		if mini_ind + 1 == l:
			if S is None or S < lists[mini_ind] - lists[mini_ind - 1]:
				S = lists[mini_ind] - lists[mini_ind - 1]
			lists.pop(mini_ind)
			continue


		maxi = max(lists[mini_ind : l])
		T = maxi - mini

		if S is None or S < T:
			S = T

		lists = lists[0 : mini_ind]
		continue

	print(S)
### BUGGY CODE ###

K = input()
N = len(K)
D = int(input())
mod = 10**9+7

dp = [[[0]*D for _ in range(2)] for _ in range(N+1)]
dp[0][1][0] = 0
dp[0][0][0] = 1

for i in range(N):
    a = ord(K[i])-48
    
    for j in range(D):
        for k in range(10):
            dp[i+1][1][(j+k)%D] += dp[i][1][j]
            dp[i+1][1][(j+k)%D] %= mod

    for j in range(D):
        dp[i+1][0][(j+a)%D] += dp[i][0][j]
        dp[i+1][0][(j+a)%D] %= mod

    for j in range(D):
        for k in range(a):
            dp[i+1][1][(j+k)%D] += dp[i][0][j]
            dp[i+1][1][(j+k)%D] %= mod

print((dp[N][1][0] + dp[N][0][0]-1)%mod)

### FIXED CODE ###

K = input()
N = len(K)
D = int(input())
mod = 10**9+7

dp = [[[0]*D for _ in range(2)] for _ in range(N+1)]
dp[0][1][0] = 0
dp[0][0][0] = 1

for i in range(N):
    a = ord(K[i])-48
    
    for j in range(D):
        for k in range(10):
            dp[i+1][1][(j+k)%D] += dp[i][1][j]
            dp[i+1][1][(j+k)%D] %= mod

    for j in range(D):
        dp[i+1][0][(j+a)%D] += dp[i][0][j]
        dp[i+1][0][(j+a)%D] %= mod

    for j in range(D):
        for k in range(a):
            dp[i+1][1][(j+k)%D] += dp[i][0][j]
            dp[i+1][1][(j+k)%D] %= mod

print((dp[N][1][0] + dp[N][0][0]-1)%mod)
### BUGGY CODE ###

import math

N,M = map(int,input().split(' '))
An = [ int(input()) for _ in range(M)]
factorial_list = [1] * (N+1)
for i in range(1,N+1):
    factorial_list[i] = factorial_list[i-1] * i

def combinations_count(n, r):
    return factorial_list[n] // (factorial_list[n - r] * factorial_list[r])

def one_two_comb(N):
    two_n = N//2
    comb_list = []
    for i in range(1,two_n+1):
        comb_list.append([N-i,i])
    return comb_list

def sum_comb(comb_list):
    comb_sum = 0
    for val in comb_list:
        comb_sum += combinations_count(val[0],val[1])
    return comb_sum
    

diff_list = []
current_num = 0
max_diff = -1
for a in An:
    diff = a - current_num
    if diff == 0:
        print(0)
        exit(0)
    diff_list.append(diff)
    current_num = a +1
diff = N+1 - current_num
diff_list.append(diff)
#print(diff_list)


all_sum = 1
for idx,diff in enumerate(diff_list):
    if idx == 0 or len(diff_list):
        diff -= 1
    '''
    else:
        diff -= 2
    '''

    if diff == 0:
        all_sum *= 1
    else:
        internal_comb_list = one_two_comb(diff)
        comb_count = sum_comb(internal_comb_list) + 1
        if all_sum > 10**9+7:
            all_sum = all_sum%(10**9+7)
        all_sum *= comb_count
print(all_sum%(10**9+7))




### FIXED CODE ###

import math

N,M = map(int,input().split(' '))
An = [ int(input()) for _ in range(M)]

'''
factorial_list = [1] * (N+1)
for i in range(1,N+1):
    factorial_list[i] = factorial_list[i-1] * i

def combinations_count(n, r):
    return factorial_list[n] // (factorial_list[n - r] * factorial_list[r])
'''

feruma_list = [1] * (N+1)
for i in range(2,N+1):
    feruma_list[i] = feruma_list[i-2] + feruma_list[i-1]


def nCk(n, k):
    ret = 1
    mo = 10**9 + 7
    for i in range(k):
        ret = ret * (n - i) * pow(i + 1, mo - 2, mo) % mo
    return ret

def one_two_comb(N):
    two_n = N//2
    comb_list = []
    for i in range(1,two_n+1):
        comb_list.append([N-i,i])
    return comb_list

def sum_comb(comb_list):
    comb_sum = 0
    for val in comb_list:
        comb_sum += nCk(val[0],val[1])
    return comb_sum
    

diff_list = []
current_num = 0
max_diff = -1
for a in An:
    diff = a - current_num
    if diff == 0:
        print(0)
        exit(0)
    diff_list.append(diff)
    current_num = a +1
diff = N+1 - current_num
diff_list.append(diff)
#print(diff_list)


all_sum = 1
for idx,diff in enumerate(diff_list):
    
    if idx == 0 or len(diff_list):
        diff -= 1
    '''
    if diff == 0:
        all_sum *= 1
    else:
        internal_comb_list = one_two_comb(diff)
        comb_count = sum_comb(internal_comb_list) + 1
        if all_sum > 10**9+7:
            all_sum = all_sum%(10**9+7)
        all_sum *= comb_count
    '''

    comb_count = feruma_list[diff]
    if all_sum > 10**9+7:
        all_sum = all_sum%(10**9+7)
    all_sum *= comb_count

print(all_sum%(10**9+7))
### BUGGY CODE ###

import collections

n = int(input())
s = [input() for i in range(n)]
t = collections.Counter(s)
x = [t.most_common()[i][0] for i in range(len(t.most_common())) if t.most_common()[i][1]==t.most_common()[0][1]]
x.sort()
for i in range(len(x)):
    print(x[i])

### FIXED CODE ###

import collections

n = int(input())
s = [input() for i in range(n)]
t = collections.Counter(s)
tm = t.most_common()
x = [tm[i][0] for i in range(len(tm)) if tm[i][1]==tm[0][1]]
x.sort()
for i in range(len(x)):
    print(x[i])
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [9999999999]*n
dp[0] = 0
for i in range(1,n):
    for j in range(1,k+1):
        if(i >= j):
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[-1])


### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [9999999999]*n
dp[0] = 0
for i in range(1,n):
    for j in range(1,k+1):
        if(i >= j):
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[-1])
### BUGGY CODE ###

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

l = len(ai)

s = 0
for j in range(l):
    for i in range(j+1, l):
        s += ai[j] * ai[i]

ans = s % (1000000000 + 7)

print(ans)


### FIXED CODE ###

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

# n=3
# ai = np.array([1, 2, 3])

# ai = ai[np.newaxis, :]
# 
# ai2 = ai.T.dot(ai)
# ai2u = np.triu(ai2, k=1)
# 
# s = ai2u.sum()


l = len(ai)

integ = [ai[0]] * len(ai)
for i in range(1, len(ai)):
    integ[i] = integ[i-1] + ai[i]

s = 0
for j in range(l):
    this_s = integ[-1] - integ[j]
    s += ai[j] * this_s

ans = s % (1000000000 + 7)

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

n = int(input())
ans = 0
if n % 2 != 0:
    print(ans)
    exit
else:
    n = n // 2
    temp = 1
    while n != 1:
        n = n // 5
        ans += n
    print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
if n % 2 != 0:
    print(ans)
    exit
else:
    n = n // 2
    while (n != 1 and n != 0):
        n = n // 5
        ans += n
    print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

num_of_R = S.count('R')


num_of_left_R = S[:num_of_R].count('R')
ans = 0
while num_of_R != num_of_left_R:
    ans = ans + 1
    
    left_white_idx = S.find('W')
    right_red_idx  = S.rfind('R')

    S = S[:left_white_idx] + 'R' + S[left_white_idx+1:]
    S = S[:right_red_idx] + 'W' + S[right_red_idx+1:]

    num_of_left_R = S[:num_of_R].count('R')

print(ans)


### FIXED CODE ###

N = int(input())
S = input()

ans = 0
while True:
    left_white_idx = S.find('W')
    right_red_idx  = S.rfind('R')

    if left_white_idx == -1 or right_red_idx == -1 or left_white_idx > right_red_idx:
        break

    # 左のRの連続とW　Rと右のWの連続を切り取った文字列に更新
    S = S[left_white_idx+1:right_red_idx]

    ans = ans + 1

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

s = input()
cnt = 0
num_list = []
list4 = []
for i in range(1,10001):
    num_list.append(i*2019)
    list4.append(int(str(i*2019)[-4::]))
for j in range(0,len(s)-4+1):
    if int(s[0+j:4+j]) in list4:
        
        if s[4+j-len(str(num_list[list4.index(int(s[0+j:4+j]))])):4+j] == str(num_list[list4.index(int(s[0+j:4+j]))]):
            cnt += 1
            
print(cnt)

### FIXED CODE ###

s = input()
from collections import Counter
x = 1
mod = 2019
total = 0
ans = 0
cnt = Counter()
for i in range(len(s)-1,-1,-1):
    cnt[total] += 1
    total = total + int(s[i])*x
    total %= mod
    ans += cnt[total]
    x = x*10%2019
print(ans)
### BUGGY CODE ###

x,y = map(int, input().split())
list = [x, y]

while True:

    if x == 0 and y == 0:
        break

    print(sorted(list, reverse=True))
       


### FIXED CODE ###

while True:
    x,y = map(int, input().split())

    if x == 0 and y == 0:
        break

    elif x <= y:
        print(str(x) + " " + str(y))
    else:
        print(str(y) + " " + str(x))
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
s = input()

ans = set()
a_alr = []
b_alr = {}

for i in range(10):
    b_alr[str(i)] = []

for i in range(n-2):
    if(len(a_alr) == 10):
        break
    if(s[i] in a_alr):
        continue

    for j in range(i+1,n-1):
        if(len(b_alr[s[i]]) == 10):
            break
        if(s[j] in b_alr[s[i]]):
            continue
        c_alr = set()
        for k in range(j+1,n):
            c_alr = c_alr | set([s[k]])   
            tmp = s[i]+s[j]+s[k]
            ans = ans | set([tmp])
            if(len(c_alr) == 10):
                break

        b_alr[s[i]].append(s[j])
    a_alr.append(s[i])

print(len(ans))

### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
s = input()

ans = 0
a_alr = []
b_alr = {}

for i in range(10):
    b_alr[str(i)] = []

for i in range(n-2):
    if(len(a_alr) == 10):
        break
    if(s[i] in a_alr):
        continue

    for j in range(i+1,n-1):
        if(len(b_alr[s[i]]) == 10):
            break
        if(s[j] in b_alr[s[i]]):
            continue
        
        ans += len(set(s[j+1:]))
        
        b_alr[s[i]].append(s[j])
    a_alr.append(s[i])

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

n,k = (int(x) for x in input().split())
a = [int(x) for x in input().split()]

now = 0
next = a[0]

for i in range(k):
  now = next
  next = a[now-1]
  
print(now)

### FIXED CODE ###

n,k = (int(x) for x in input().split())
a = tuple([int(x) for x in input().split()])
 
c = [0] + [-1]*(n)
l = [1]
now = 1
dupl = -1

for i in range(k):
  now = a[now - 1]
  c[now - 1] += 1
   
  if c[now - 1] == 1:
    dupl = now
    break
  else:
    l.append(now)
    
if dupl == -1:
  print(now)
  exit()
       
notloop = l.index(dupl)
length = len(l)-notloop
print(l[(k-notloop)%length+notloop])
### BUGGY CODE ###

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

for i in range(1,N+1):
  print(A.count(i))

### FIXED CODE ###

from collections import Counter

N=int(input())
A=list(map(int,input().split()))
B=set(A)
C=Counter(A)
for i in range(1,N+1):
  if i not in B:
    print(0)
  else:
    print(C[i])
### BUGGY CODE ###

import collections

def solve():
  n = int(input())
  query = []
  query2 = []
  ans = [0]*n
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
    query2.append(a)
    query2.append(b)
  c = list(int(i) for i in input().split())
  c = sorted(c,reverse =True)
  d = collections.Counter(query2)
  for i in range(len(d)):
    tmp = d.most_common()[i][0]
    #print(tmp)
    ans[tmp-1] = c[i]
  print(sum(c) +(-1)*max(c))
  #dの処理
  print(*ans)
  
solve()

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline
import heapq
from array import array
def solve():
  n = int(input())

  query2 = collections.deque([])
  edge = [[] for _ in range(n)]
  ans = array('I', [ 0 for i in range(n)])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
  c = list(int(i) for i in input().split())
  if n == 1:
    print(1)
    print(c[0])
    exit()
  c = collections.deque(sorted(c,reverse =True))
  d = collections.Counter(query2)
  d2 = d.most_common()
  bfs = []
  heapq.heappush(bfs,(-1*d2[0][1],d2[0][0]-1,-1))#回数,場所、親
  ct = 0
  visit = [False]*n
  while bfs:
    times,place,parent = heapq.heappop(bfs)
    if visit[place]:
      continue
    else:
      visit[place] = True

      for i in range(len(edge[place])):
        newp = edge[place][i]
        newtimes = len(edge[newp])
        if not visit[newp]:
          heapq.heappush(bfs,(-1*newtimes,newp,place))
      #print(place,parent,times)
      ans[place] = c.popleft()

      #print(c,place)

  print(sum(ans)-max(ans))
  print(*ans)
  
solve()
### BUGGY CODE ###

base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl):
    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)
    return tmp


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(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 = calc_hash(p, 10, pl)
        keys0, keys1 = keys[0], keys[1:pl - 9]
        if pl not in h:
            hash_array = h[10] = calc_hash(t, 10, tl)
        else:
            hash_array = h[10]
        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:
        key = calc_hash(p, pl, pl).pop() & mask
        if pl not in h:
            h[pl] = calc_hash(t, pl, tl)
        print(1 if key in h[pl] else 0)
    q -= 1

### FIXED CODE ###

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(input())
ps = [input().strip() for _ in range(q)]
h = dict()
a = []
hash_len = 19
for p in ps:
    p = [ord(c) for c in p]
    pl = len(p)
    if pl > tl:
        a.append(0)
        continue
    bs = min(hash_len, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    a.append(1 if keys.issubset(h[bs]) else 0)
print('\n'.join(map(str, a)))