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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import Counter, defaultdict
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


n, *a = map(int, read().split())
counter = list(Counter(a).items())
cnt = defaultdict(int)
memo = defaultdict(int)
for k, v in counter:
    if v > 1:
        cnt[k] = cmb(v, 2)
    else:
        cnt[k] = 0
    if v > 2:
        memo[k] = cmb(v - 1, 2)
    else:
        memo[k] = 0
for aa in a:
    print(sum(cnt.values()) - cnt[aa] + memo[aa])


### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
count = collections.Counter(a)
sm = {}
sm2 = {}
for key, value in count.items():
    sm[key] = value * (value - 1) // 2
    sm2[key] = (value - 1) * (value - 2) // 2
total = sum(sm.values())

for num in a:
    print(total - sm[num] + sm2[num])
### BUGGY CODE ###

n = input()
count = 0
for i in range(n):
    x = input()
    if x == 2: count += 1
    elif x % 2 != 0:
        for j in xrange(3,int(x*0.5+1),2):
            if x % j == 0: break
        else: count += 1
print count

### FIXED CODE ###

import math
def prime(x):
    if x == 2: return True
    elif x % 2 == 0: return False
    else:
        for j in xrange(3,int(math.sqrt(x))+1,2):
            if x % j == 0: return False
        else:
            return True 
n = input()
count = 0
for i in xrange(n):
    if prime(input()): count += 1
print count
### BUGGY CODE ###


S = input()

count = 0
while 'ABC' in S:
    if 'ABCBC' in S:
        S = S.replace('ABCBC','BCABC',1)
        count += 1
        continue
    if 'AABC' in S:
        S = S.replace('AABC','ABCA',1)
        count += 1
        continue
    else:
        S = S.replace('ABC','BCA',1)
        count += 1
print(str(count))

### FIXED CODE ###

import re
S = input()
N1 = S.replace('A','0').replace('BC','1')
S_li = re.split('B|C',N1)
 
count = 0
for l in S_li:
    a = sum([i for i,x in enumerate(l) if '1' in x])
    su=sum([x for x in range(l.count('1'))])
    count += (a-su)
print(str(count))
### BUGGY CODE ###

#!/ust/bin/env python

N,A,B=[int(i) for i in input().split()]

def main():
    def sum(count, num):
        tmp=0
        for i in range(0, count):
            tmp+=num
        # print("tmp",tmp)
        return tmp

    if(A>B):
        print(0)
        return
    elif(A==B):
        print(1)
        return

    ### A<B
    Max=(A+B)+sum(N-2, B)
    Min=(A+B)+sum(N-2, A)

    if(N==1):
        print(0)
    elif(N==2):
        print((B+B)-(A+A)+1)
    elif(Max-Min+1<=0):
        print(0)
    else:
        print(Max-Min+1)

main()


### FIXED CODE ###

#!/ust/bin/env python

N,A,B=[int(i) for i in input().split()]

def main():
    if(A>B):
        print(0)
        return
    elif(A==B):
        print(1)
        return

    ### A<B
    Max=(A+B)+(N-2)*B
    Min=(A+B)+(N-2)*A

    if(N==1):
        print(0)
    elif(N==2):
        print((B+B)-(A+A)+1)
    elif(Max-Min+1<=0):
        print(0)
    else:
        print(Max-Min+1)

main()
### BUGGY CODE ###

n = int(input())
l = [int(i) for i in input().split()]
l.sort()
ans = 0
for i in range(n-2):
    a = l[i]
    for j in range(i+1, n-1):
        b = l[j]
        p = a + b
        for k in range(j+1, n):
            if p > l[k]: ans += 1
            else: break
print(ans)

### FIXED CODE ###

from bisect import bisect_left
n = int(input())
l = [int(i) for i in input().split()]
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect_left(l, l[i]+l[j]) - j - 1
print(ans)
### BUGGY CODE ###

import sys

N,M=map(int, sys.stdin.readline().split())
S=[None]+map(int, sys.stdin.readline().split())
T=[None]+map(int, sys.stdin.readline().split())

dp=[ [ 0 for m in range(M+1) ] for n in range(N+1) ]

for m in range(M+1): dp[0][m]=1	
for n in range(n+1): dp[n][0]=1	


for i in range(1,N+1):
	for j in range(1,M+1):
		if S[i]==T[j]:
			dp[i][j]+=dp[i][j-1]+dp[i-1][j]
		else:
			dp[i][j]+=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]
		

print dp[-1][-1]%(10**9+7)


### FIXED CODE ###

import sys

N,M=map(int, sys.stdin.readline().split())
S=[None]+map(int, sys.stdin.readline().split())
T=[None]+map(int, sys.stdin.readline().split())

dp=[ [ 0 for m in range(M+1) ] for n in range(N+1) ]

for m in range(M+1): dp[0][m]=1	
for n in range(n+1): dp[n][0]=1	

mod=10**9+7
for i in range(1,N+1):
	for j in range(1,M+1):
		if S[i]==T[j]:
			dp[i][j]+=dp[i][j-1]+dp[i-1][j]
		else:
			dp[i][j]+=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]
		dp[i][j]%=mod
		

print dp[-1][-1]%mod
### BUGGY CODE ###

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort()

target = 0
cnt = 0
while target < n:
    x, h = xh[target]
    atk_end = x + d + d
    atk_cnt = (h + a - 1) // a
    cnt += atk_cnt
    for i in range(target, n):
        if xh[i][0] > atk_end:
            break
        xh[i][1] -= a * atk_cnt
        if xh[i][1] < 1 and i == target+1:
            target += 1
    # while xh[target][1] < 1:
    #     target += 1
    #     if target >= n:
    #         break

print(cnt)

### FIXED CODE ###

import math
from collections import deque

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort(key=lambda x:x[0])
xh = deque(xh)

xh_field = deque()

cnt = 0
now_damage = 0
while xh:
    pos, hp = xh.popleft()
    if xh_field:
        while (xh_field and xh_field[0][0] < pos) :
            now_damage -= a * xh_field[0][1]
            xh_field.popleft() 
    if hp <= now_damage:
        pass
    elif hp > now_damage:
        atk_cnt = math.ceil((hp - now_damage) / a)
        cnt += atk_cnt
        now_damage += atk_cnt * a
        xh_field.append((2*d + pos, atk_cnt))        
print(cnt)
### BUGGY CODE ###

from collections import deque

class Graph:
    # n is the number of N
    # E is a set of edges where each edge is a two tuple (u, v)
    def __init__(self, n, E):
        self.N = n # number of vertices
        self.V = list(range(0, n)) # V = [0, 1, ..., n-1]
        self.AL = [set() for i in range(n)] # adjacency list
        for e in E:
            self.add_edge(e[0], e[1])

    def add_edge(self, u, v): # u is head, v is tail
        self.AL[u].add(v)
        self.AL[v].add(u)

# 入力
N, M, K = [int(x) for x in input().split()]
Ef = [-1] * M
Eb = [-1] * K

for i in range(M):
    Ef[i] = [int(x) - 1 for x in input().split()]

for i in range(K):
    Eb[i] = [int(x) - 1 for x in input().split()]

Gf = Graph(N, Ef)   # 友達
Gb = Graph(N, Eb)   # ブロック
ans = [0] * N
visited = [False] * N

for root in range(N):
    if visited[root]: continue
    que = deque()
    que.append(root)
    tree_nodes = set()

    while len(que) > 0:
        u = que.pop()
        visited[u] = True
        tree_nodes.add(u)
        
        for v in Gf.AL[u]:
            if visited[v] or v in que:
                continue
            que.append(v)

    for v in tree_nodes:
        ans[v] = max(0, len(tree_nodes) - 1 - len(Gb.AL[v] & tree_nodes)- len(Gf.AL[v]))

print(" ".join([str(f) for f in ans]))


### FIXED CODE ###

# Union-Find木（サイズ付き）
class UnionFind():
    # 初めは全ての頂点が別々の木の根
    def __init__(self, n):  # n要素で初期化
        self.parent = [None] * n # 親
        self.rank = [None] * n   # 木の深さ
        self._size = [1] * n # 要素が属する集合の大きさ（根の要素のみ参照すること）
        for i in range(n):
            self.parent[i] = i
            self.rank[i] = 0

    # 木の根を求める
    def root_of(self, x):
        children = [x]
        while self.parent[x] != x:
            x = self.parent[x]
            children.append(x)

        for ch in children:
            self.parent[ch] = x

        return x

    # xとyの属する集合を併合
    def unite(self, x, y):
        rx = self.root_of(x)
        ry = self.root_of(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]: # ランクの小さい木から大きい木の根に辺を張る
            self.parent[rx] = ry  # rxをryの子とする
            self._size[ry] += self._size[rx]
        else:
            self.parent[ry] = rx
            self._size[rx] += self._size[ry]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するかどうか
    def is_same(self, x, y):
        return self.root_of(x) == self.root_of(y)

    # 頂点xが属する集合のサイズ
    def size(self, x):
        return self._size[self.root_of(x)]


# 入力
N, M, K = [int(x) for x in input().split()]

Ef = [[int(x) - 1 for x in input().split()] for _ in range(M)]
Eb = [[int(x) - 1 for x in input().split()] for _ in range(K)]

ans = [0] * N
uf = UnionFind(N)
for i in range(M):
    uf.unite(Ef[i][0], Ef[i][1])
    ans[Ef[i][0]] -= 1  # すでに友達なら友達候補ではない
    ans[Ef[i][1]] -= 1

for i in range(K):
    if uf.is_same(Eb[i][0], Eb[i][1]):
        ans[Eb[i][0]] -= 1  # ブロックしているなら友達候補ではない
        ans[Eb[i][1]] -= 1

for i in range(N):
    ans[i] += uf.size(i) - 1

print(" ".join([str(i) for i in ans]))
### BUGGY CODE ###

s = input()
n = int(input())
qs = [input().split(' ') for i in range(n)]

div = True
for q in qs:
    if q[0] == '1':
        div = not div
    if q[0] == '2':
        if q[1] == '1':
            if div:
                s = q[2] + s
            else:
                s = s + q[2]
        if q[1] == '2':
            if div:
                s = s + q[2]
            else:
                s = q[2] + s

if div:
    print(s)
else:
    s = ''.join(list(reversed(s)))
    print(s)


### FIXED CODE ###

from collections import deque

s = input()
n = int(input())
ans = deque(s)

div = True
for i in range(n):
    q = input().split(' ')
    if q[0] == '1':
        div = not div
    elif (q[1] == '1' and div) or (q[1] == '2' and not div):
        ans.appendleft(q[2])
    else:
        ans.append(q[2])

if div:
    print(''.join(ans))
else:
    print(''.join(reversed(ans)))
### BUGGY CODE ###

import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if len(dpv) > 1:
                for d, (u0, u1, u2) in enumerate(dpv):
                    dpv[d] = (u0 + u2, u1, 0)
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        mxlen=0
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                mxlen=max(mxlen,len(dpv))
                merge(dpu, dpv)
        for d in range(-1,-1-mxlen,-1):
            u0,u1,u2=dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    n = int(input())
    to = [[] for _ in range(n+1)]
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()
### BUGGY CODE ###

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = [0]
b = [0]
ans = 0
max_num = 0
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])
for i in range(N+1):
    j = M
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -=1
        if j <0:
            break
    ans = max(ans,i + j)
print(ans)
        


### FIXED CODE ###

N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a = [0]
b = [0]
ans = 0
max_num = 0
j = M
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])
for i in range(N+1):
    if a[i] > K:
        break
    else:
        while b[j] > K - a[i]:
            j -=1
            if j <0:
                break
    if K>= a[i] + b[j]:
        ans = max(ans,i + j)
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_g
import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        # n: num of vertices
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfsWithDp(self, node, dp, visited):
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  # dp[i] := longest path starting from vertex i
        for i in range(self.n):
            if not visited[i]:
                self.dfsWithDp(i, dp, visited)
        return max(dp)


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    print(dag.findLongestPathWithDp())


main()


### FIXED CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_g
import sys
sys.setrecursionlimit(10**7)


class DAG:
    def __init__(self, n):
        # n: num of vertices
        self.n = n
        self.adj = [[] for _ in range(n)]

    def addEdge(self, parent, child):
        self.adj[parent].append(child)

    def dfsWithDp(self, node, dp, visited):
        if(visited[node]):
            return dp[node]
        visited[node] = True
        for child in self.adj[node]:
            if not visited[child]:
                self.dfsWithDp(child, dp, visited)
            dp[node] = max(dp[node], 1 + self.dfsWithDp(child, dp, visited))
        return dp[node]

    def findLongestPathWithDp(self):
        visited = [False] * self.n
        dp = [0] * self.n  # dp[i] := longest path starting from vertex i
        ans = 0
        for i in range(self.n):
            ans = max(ans, self.dfsWithDp(i, dp, visited))
        return ans


def main():
    N, M = map(int, input().split())
    dag = DAG(N)
    for _ in range(M):
        parent, child = map(lambda i: int(i) - 1, input().split())
        dag.addEdge(parent, child)
    print(dag.findLongestPathWithDp())


main()
### BUGGY CODE ###

import functools
import operator

n, k = map(int, input().split())
a = [int(s) for s in input().split()]
vals = []
for i in range(k - 1, n):
    vals.append(functools.reduce(operator.mul, a[i - k + 1:i + 1]))

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

### FIXED CODE ###

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

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

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    tmp=0
    for j in range(n):
        if(j!=i and tmp<a[j]):
            tmp = a[j]
    print(tmp)


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
max = 0
max2 = 0
tmp = 0
for i in range(n):
    if max<a[i]:
        max = a[i]
        tmp=i
for i in range(n):
    if tmp!=i and max2<a[i]:
        max2 = a[i]

for i in range(n):
    if i != tmp:
        print(max)
    else:
        print(max2)
### BUGGY CODE ###

H, N = map(int, input().split(" "))
dp = [[float('inf') for i in range(H + 1)] for j in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[i][j] != float('inf'):
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            dp[i][min(j + A, H)] = min(dp[i][min(j + A, H)], dp[i][j] + B)
print(dp[N][H])

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, N = map(int, input().split(" "))
dp = [1e10 for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    A, B = map(int, input().split(" "))
    for j in range(H + 1):
        if dp[j] != 1e10:
            dp[min(j + A, H)] = min(dp[min(j + A, H)], dp[j] + B)
print(dp[H])
### BUGGY CODE ###

import itertools
 
N = input()
l_list = list(map(int,input().split()))
ans = 0
 
for v in itertools.combinations(l_list, 3):
  v = sorted(v,reverse=True)
  max_len = v[0]
  lens = v[1:]
  if max_len < sum(lens):
    ans += 1

print(ans)

### FIXED CODE ###

import bisect
N = int(input())
L_list = list(map(int,input().split()))
L_list.sort()
ans = 0

for i in range(N-1):
  for j in range(i+1,N-1):
    x = bisect.bisect_left(L_list,L_list[i]+L_list[j])
    ans += x-j-1
print(ans)
### BUGGY CODE ###

def nyu():
    num1,num2 = input().split()
    num1 = int(num1)
    num2 = int(num2)
    #   print("x = " ,x[i]  ,"y = ",y[i])
    return num1,num2

def otoshidama(n,y):
    n = n+1
    ichiman = 0
    gosen = 0
    senen = 0
    y_tmp = y
    for i in reversed(range(n)):
#        print(i)
        ichiman  = 0
        gosen  = 0
        senen = 0
        y_tmp = y
        g_ymp = y_tmp 
        if y_tmp >= 10000*i: 
            y_tmp = y_tmp - 10000*i
            ichiman = i
            g_ymp = y_tmp
 #           if check(y_tmp,ichiman,gosen,senen) == True:
 #            return ichiman,gosen,senen
        for g in reversed(range(n)):
            gosen = 0
            senen = 0
            y_tmp = g_ymp
            if y_tmp >= 5000*g:
                y_tmp = y_tmp - 5000 * g
                gosen = g
#                if check(y_tmp,ichiman,gosen,senen) == True:
#                   return ichiman,gosen,senen
            senen = int(y_tmp / 1000)
            y_tmp = y_tmp % 1000
            if check(y_tmp,ichiman,gosen,senen) == True:
                return ichiman,gosen,senen
    return -1,-1,-1

def check(y_tmp,ichiman,gosen,senen):
    #print("y_tmp:",y_tmp,"ichiman:",ichiman,"gosen:",gosen,"senen:",senen,"goukei",ichiman + gosen + senen,n)
    if y_tmp == 0 and ichiman + gosen + senen  == n:
        return  True    
    return False


n,y =nyu()
num1,num2,num3 = otoshidama(n,y)
print(num1,num2,num3)



### FIXED CODE ###

def nyu():
    num1,num2 = input().split()
    num1 = int(num1)
    num2 = int(num2)
    #   print("x = " ,x[i]  ,"y = ",y[i])
    return num1,num2

def otoshidama(n,y):
    n = n+1
    ichiman = 0
    gosen = 0
    senen = 0
    y_tmp = y
    for i in reversed(range(n)):
#        print(i)
        ichiman  = 0
        gosen  = 0
        senen = 0
        y_tmp = y
        g_ymp = y_tmp 
        if y_tmp >= 10000*i: 
            y_tmp = y_tmp - 10000*i
            ichiman = i
            g_ymp = y_tmp
 #           if check(y_tmp,ichiman,gosen,senen) == True:
 #            return ichiman,gosen,senen
        for g in reversed(range(n-i)):
            gosen = 0
            senen = 0
            y_tmp = g_ymp
            if y_tmp >= 5000*g:
                y_tmp = y_tmp - 5000 * g
                gosen = g
#                if check(y_tmp,ichiman,gosen,senen) == True:
#                   return ichiman,gosen,senen
            senen = int(y_tmp / 1000)
            y_tmp = y_tmp % 1000
            if check(y_tmp,ichiman,gosen,senen) == True:
                return ichiman,gosen,senen
    return -1,-1,-1

def check(y_tmp,ichiman,gosen,senen):
    #print("y_tmp:",y_tmp,"ichiman:",ichiman,"gosen:",gosen,"senen:",senen,"goukei",ichiman + gosen + senen,n)
    if y_tmp == 0 and ichiman + gosen + senen  == n:
        return  True    
    return False


n,y =nyu()
num1,num2,num3 = otoshidama(n,y)
print(num1,num2,num3)
### BUGGY CODE ###

n, s = map(int, input().split())
*A, = map(int, input().split())
p = 998244353
DP = [[0 for j in range(s + 1)] for i in range(n + 1)]
DP[0][0] = 1
for i in range(n):
    for j in range(s + 1):
        if j >= A[i]:
            DP[i + 1][j] = (2 * DP[i][j] + DP[i][j - A[i]]) % p
        else:
            DP[i + 1][j] = (2 * DP[i][j]) % p
print(DP[n][s] % p)


### FIXED CODE ###

n, s = map(int, input().split())
*A, = map(int, input().split())
p = 998244353
DP = [[0 for j in range(s + 1)] for i in range(n + 1)]
DP[0][0] = 1
for i in range(n):
    for j in range(s + 1):
        if j >= A[i]:
            DP[i + 1][j] = (2 * DP[i][j] + DP[i][j - A[i]]) % p
        else:
            DP[i + 1][j] = (2 * DP[i][j]) % p
print(DP[n][s] % p)
### BUGGY CODE ###

T = int(input())
ans = []
for _ in range(T):
    N = int(input())
    A = [int(_) for _ in input().split()]
    S = input()
    dp = set([0])
    for a, s in zip(A[::-1], S[::-1]):
        if s == '1':
            dp2 = set()
            for b in dp:
                if b ^ a in dp:
                    dp2.add(b)
            dp = dp2
        else:
            for b in dp.copy():
                dp.add(b ^ a)
    ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')


### FIXED CODE ###

T = int(input())
ans = []
for _ in range(T):
    N = int(input())
    A = [int(_) for _ in input().split()]
    S = input()
    dp = set([0])
    for a, s in zip(A[::-1], S[::-1]):
        for b in dp:
            a = min(a, a ^ b)
        if s == '1':
            if a:
                dp = set()
                break
        else:
            dp2 = set([a])
            for b in dp:
                dp2.add(min(b, a ^ b))
            dp = dp2
    ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')