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

mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    if N == 2:
        if A[0] == A[1]:
            print(0)
        elif A[0] < A[1]:
            print(-1)
        else:
            if (A[0] - A[1]) %2 == 0:
                print((A[0] -  A[1])//2)
            else:
                print(-1)
        exit()

    g1 = A[0]
    g2 = A[1]
    g3 = 0
    for i in range(2, N):
        g3 ^= A[i]
    n1 = g1.bit_length()
    n2 = g2.bit_length()
    n3 = g3.bit_length()
    NN = max(n1, n2, n3)
    ans = 0
    while True:
        for i in range(NN):
            if (g1 >> i & 1) ^ (g2 >> i & 1) != (g3 >> i & 1):
                r1 = g1 % (1 << i) + 1
                r2 = (1<<i) - g2 % (1 << i)
                if r1 < r2:
                    g1 -= r1
                    g2 += r1
                    ans += r1
                    break
                elif r1 > r2:
                    g1 -= r2
                    g2 += r2
                    ans += r2
                    break
                else:
                    print(-1)
                    exit()
            if g1 ^ g2 == g3:
                if ans != A[0]:
                    print(ans)
                else:
                    print(-1)
                exit()


if __name__ == '__main__':
    main()


### FIXED CODE ###

mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    if N == 2:
        if A[0] == A[1]:
            print(0)
        elif A[0] < A[1]:
            print(-1)
        else:
            if (A[0] - A[1]) %2 == 0:
                print((A[0] -  A[1])//2)
            else:
                print(-1)
        exit()

    g1 = A[0]
    g2 = A[1]
    g3 = 0
    for i in range(2, N):
        g3 ^= A[i]
    n1 = g1.bit_length()
    n2 = g2.bit_length()
    n3 = g3.bit_length()
    NN = max(n1, n2, n3)
    ans = 0
    cnt = 0
    while True:
        cnt += 1
        if cnt == 10000:
            print(-1)
            exit()
        for i in range(NN):
            if (g1 >> i & 1) ^ (g2 >> i & 1) != (g3 >> i & 1):
                r1 = g1 % (1 << i) + 1
                r2 = (1<<i) - g2 % (1 << i)
                if r1 < r2:
                    g1 -= r1
                    g2 += r1
                    ans += r1
                    break
                elif r1 > r2:
                    g1 -= r2
                    g2 += r2
                    ans += r2
                    break
                else:
                    print(-1)
                    exit()
            if g1 ^ g2 == g3:
                if ans != A[0]:
                    print(ans)
                else:
                    print(-1)
                exit()


if __name__ == '__main__':
    main()
### BUGGY CODE ###

def floor(x) :
    return int(x)
    
s = input().split(" ")
a = int(s[0])
b = int(s[1])
n = int(s[2])
M = 0

for i in range(1,n+1) :
    if M<(floor(a*i/b)-a*floor(i/b)) :
        M = (floor(a*i/b)-a*floor(i/b))

print(M)


### FIXED CODE ###

s = input().split()

a = int(s[0])
b = int(s[1])
n = int(s[2])

if b==1 :
    print(0)
else :
    c = min(b-1,n)
    m = (a*c)//b
    print(m)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import itertools

N = int(input())
name_list = []
for i in range(N):
    name_str = input()
    # 1文字目がMARCHの名前だけリストに詰める
    if name_str[0] == "M" or name_str[0] == "A" or name_str[0] == "R" or name_str[0] == "C" or name_str[0] == "H":
        name_list.append(name_str)
# 3人を選ぶ組み合わせ
cmb_list = list(itertools.combinations(name_list, 3))

ans = 0
for names in cmb_list:
    # 各人の名前のイニシャルを取得
    init1 = names[0][0]
    init2 = names[1][0]
    init3 = names[2][0]
    # 重複がなければ条件を満たす
    if init1 != init2 and init1 != init3 and init2 != init3:
        ans += 1
    
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

import itertools

N = int(input())
name_dict = {"M":0, "A":0, "R":0, "C":0, "H":0}

# 各イニシャル毎に集計
for i in range(N):
    name_str = input()
    if name_str[0] == "M":
        name_dict["M"] += 1
    if name_str[0] == "A":
        name_dict["A"] += 1
    if name_str[0] == "R":
        name_dict["R"] += 1
    if name_str[0] == "C":
        name_dict["C"] += 1
    if name_str[0] == "H":
        name_dict["H"] += 1

# MARCHから3文字を選ぶ組み合わせ
cmb_list = list(itertools.combinations(["M","A","R","C","H"], 3))

ans = 0
for cmb in cmb_list:
    # 各イニシャルの人数毎に掛け合わせて合計していく
    ans += name_dict[cmb[0]] * name_dict[cmb[1]] * name_dict[cmb[2]]
    
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [0] * N


for i in range(1, N):
  c = 10 ** 4 * N
  j=0 if i<K else i-K
  H = h[i]
  for k,l in zip(dp[j:i], h[j:i]):
    c1 = k + abs(l-H)
    c = min(c1, c)
  dp[i] = c
print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [0] * N

for i,H in enumerate(h):
  if i != 0:
    j=0 if i<K else i-K
    dp[i] = min(k + abs(l-H) for k,l in zip(dp[j:i], h[j:i]))
print(dp[-1])
### BUGGY CODE ###

s = input()
n = len(s)

temp = [0]*2019
num = 0
for i in range(n):
    num += int(s[n-i-1])*10**(i)
    temp[num % 2019] += 1

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))


### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)
### BUGGY CODE ###

input()
a=list(map(int,input().split()))
b=int(input())
for i in range(b):
  c,d=map(int,input().split())
  a=[d if j==c else j for j in a]
  print(sum(a))

### FIXED CODE ###

from sys import stdin
input=stdin.readline
input()
a=list(map(int,input().split()))
ans=sum(a)
b=[0]*(10**5+1)
for i in a:
  b[i]+=1
c=int(input())
for i in range(c):
  n,m=map(int,input().split())
  if b[n]>0:
    x=b[n]
    if x>0:
      b[m]+=x
      b[n]=0
      ans+=(m-n)*x
  print(ans)
### BUGGY 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)
B.sort(reverse=True)
C.sort(reverse=True)

max_b = max(B)
max_c = max(C)
summs = []
for a in A[:K]:
    if len(summs) >= K and a + max_b + max_c < summs[K-1]:
        break

    for b in B[:K]:
        if len(summs) >= K and a + b + max_c < summs[K-1]:
            break

        for c in C[:K]:
            summ = a + b + c
            if len(summs) >= K:
                min_sum = summs[K-1]    
                if summ < min_sum:
                    break
            summs.append(summ)
        summs.sort(reverse=True)

for s in summs[0:K]:
    print(s)

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

N = int(input())

l = 0
r = N -1

print(0, flush=True)
a = input()
if a == 'Vacant':
  exit()
b = a
while r > l:
  i = (r - l)//2
  print(i, flush=True)
  a = input()
  if a == 'Vacant':
    exit()
  if i%2 == 0:
    if a == b:
      l = i + 1
    else:
      r = i
  else:
    if a == b:
      r = i
    else:
      l = i + 1
  b = a
      
print(l, flush=True)



### FIXED CODE ###

N = int(input())

l = 0
j = 0
r = N -1

print(0, flush=True)
a = input()
if a == 'Vacant':
  exit()
b = a
while r - l > 1:
  i = (r + l)//2
  print(i, flush=True)
  a = input()
  if a == 'Vacant':
    exit()
  if abs(i-j)%2 == 0:
    if a == b:
      if i > j:
        l = i
      else:
        r = i
    else:
      if i > j:
        r = i
      else:
        l = i
  else:
    if a == b:
      if i > j:
        r = i
      else:
        l = i
    else:
      if i > j:
        l = i
      else:
        r = i
      
  b = a
  j = i

print(l, flush=True)
a = input()
if a == 'Vacant':
  exit()
  
print(r, flush=True)
### BUGGY CODE ###

def gcd(a,b):
    if ( b==0 ):
        return a
    else:
        return (gcd(b, a%b))

kosuu = int(input())
nums = list(map(int,input().split()))

i=0
max = 0
while i < len(nums):
    x,l=0,0
    while x < i:
        l = gcd(l,nums[x])
        x += 1
    y,r = i+1,0
    while y < len(nums):
        r = gcd(r,nums[y])
        y +=1
    i +=1
    tmp = gcd(l,r)
    if max < tmp:
        max = tmp
print(max)

### FIXED CODE ###

def gcd(a,b):
    if ( b==0 ):
        return a
    else:
        return (gcd(b, a%b))

kosuu = int(input())
nums = list(map(int,input().split()))

L = []
R = []
for temp in range(kosuu-1):
    if temp == 0:
        L.append(nums[0])
    else:
        L.append(gcd(L[temp-1],nums[temp]))

for temp in range(kosuu-1):
    if temp == 0:
        R.append(nums[kosuu-1])
    else:
        R.append(gcd(R[temp-1],nums[len(nums)-temp-1]))

saidai=[]
for i in range(kosuu):
    if i == 0:
        saidai.append(L[-1])
    elif i == kosuu-1:
        saidai.append(R[-1])
    else:
        saidai.append(gcd(L[i-1],R[-1-i]))

print(max(saidai))
### BUGGY CODE ###

#WarshallFloyd法(全点対最短路)　計算量O(|V|**3)
#V:頂点の集合 E:辺の集合

class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]
                  for i in range(N)]  # d[u][v] : 辺uvのコスト(存在しないときはinf)

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        # これを d[i][j]: iからjへの最短距離 にする
        # 本来無向グラフでのみ全域木を考えるが、二重辺なら有向でも行けそう
        # d[i][i] < 0 なら、グラフは負のサイクルを持つ
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(
                        self.d[i][j], self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        for i in range(self.N):
            if self.d[i][i] < 0:
                hasNegativeCycle = True
                break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d

#ABC012D
n,m,l=map(int,input().split())
ABC=[list(map(int, input().split())) for i in range(m)]
q=int(input())
st=[list(map(int, input().split())) for i in range(q)]

graph=WarshallFloyd(n)
graph2=WarshallFloyd(n)
for a,b,c in ABC:
    graph.add(a-1,b-1,c)
hasNegativeCycle, d = graph.WarshallFloyd_search()
#ans = sorted([[i, max(d[i])] for i in range(n)], key=lambda x: x[0])
ans=graph.WarshallFloyd_search()
#print(ans)
L=[[0,0,0] for _ in range(n**2)]
for i in range(n):
    for j in range(n):
        L[i*n+j][0],L[i*n+j][1],L[i*n+j][2]=i+1,j+1,ans[1][i][j]
#print(L)
#print(L)
for a,b,c in L:
    if 0<c<=l:
        graph2.add(a-1,b-1,1)
ans1=graph2.WarshallFloyd_search()
#print(ans1)
for i,j in st:
    if ans1[1][i-1][j-1]-1!=float('inf'):
        print(ans1[1][i-1][j-1]-1)
    else:
        print(-1)

### FIXED CODE ###

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


n,m,l= map(int,input().split()) #n:頂点数　w:辺の数

d=[[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(m):
    a,b,c = map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(d)

d2=[[float("inf") for i in range(n)] for i in range(n)] 
for i in range(n):
    for j in range(n):
        if d[i-1][j-1]<=l:
            d2[i-1][j-1]=1
            d2[j-1][i-1]=1
warshall_floyd(d2)
q=int(input())
l=[list(map(int, input().split())) for i in range(q)]
for i in range(q):
    if d2[l[i][0]-1][l[i][1]-1]-1!=float('inf'):
        print(d2[l[i][0]-1][l[i][1]-1]-1)
    else:
        print(-1)
### BUGGY CODE ###

N,K=map(int,input().split())
A=[int(s) for s in input().split()]
dp=[0]*(N-K+2)
dp[1]=1
for j in range(K):
    dp[1]*=A[j]
for i in range(1,N-K+1):
    dp[i+1]=dp[i]*A[K+i-1]/A[i-1]
    if dp[i+1]>dp[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(N-K):
    if A[K+i]/A[i]>1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n,m=map(int,input().split())
*a,=map(int,input().split())
l=[list(map(int,input().split()))[::-1] for _ in range(m)]
a.sort()
d=[]
for c,b in sorted(l)[::-1]:
	d+=[c]*b
for i,(x,y) in enumerate(zip(a,d)):
	if x<y:a[i]=y
print(sum(a))

### FIXED CODE ###

from operator import itemgetter
n,m = map(int,input().split())
*a,= map(int,input().split())
l = [tuple(map(int,input().split()))for _ in range(m)]
a.sort()
l.sort(key = itemgetter(1), reverse = True)
cmp = []
cnt = 0
for b,c in l:
	cmp += [c]*b
	cnt += b
	if cnt >= n:
		cnt = n
		break
cut = cnt
for i,(x,y) in enumerate(zip(a,cmp[:min(n,cnt+1)])):
	if x > y:
		cut = i
		break
print(sum(cmp[:cut] + a[cut:]))
### BUGGY CODE ###

def num(pos,list1):
    count = 0
    val = list1[pos]
    for x in range(pos+1,len(list1)):
        if list1[x]<=val:
            count+=1
            val=list1[x]
        else:
            return count
    return count
maximum = 0
n = int(input())
list1 = [int(i) for i in input().split()]
for y in range(len(list1)):
    ans = num(y,list1)
    if ans>maximum:
        maximum = ans
print(maximum)

### FIXED CODE ###

def num(pos,list1):
    count = 0
    val = list1[pos]
    for x in range(pos+1,len(list1)):
        if list1[x]<=val:
            count+=1
            val=list1[x]
        else:
            return count
    return count
maximum = 0
n = int(input())
list1 = [int(i) for i in input().split()]
y = 0
while y<len(list1):
    ans = num(y,list1)
    if ans>maximum:
        maximum = ans
    y+=ans+1
print(maximum)
### BUGGY CODE ###

import sys
import heapq
n,m=map(int,sys.stdin.readline().split())
a=list(map(int,sys.stdin.readline().split()))
heapq.heapify(a)
for i in range(m):
    b,c=map(int,sys.stdin.readline().split())
    for j in range(b):
        if a[0]<c:
            heapq.heappop(a)
            heapq.heappush(a,c)
        else:
            break
print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1],reverse=True)
for b,c in bc:
    a.extend([c]*b)
    if len(a)>2*n:
        break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
a.insert(0,0)
a.append(0)
for i in range(n):
    m=0
    b = list(a)
    del b[i+1]
    for j in range(n):
        m += abs(b[j]-b[j+1])
    print(m)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.insert(0,0)
a.append(0)
cost = 0
for i in range(n+1):
    cost += abs(a[i]-a[i+1])
for i in range(1,n+1):
    print(cost-(abs(a[i-1]-a[i])+abs(a[i]-a[i+1]))+abs(a[i-1]-a[i+1]))
### BUGGY CODE ###

n, p = map(int, input().split())
s =list(str(input()))
s = [int(c) for c in s]
s.reverse()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if s[i]%p == 0:
            ans += n-1-i+1
    print(ans)
    exit()


#print(s)

#s = [0] + s
#from itertools import accumulate
#cum =list(accumulate(s))
#cum = [c%p for c in cum]
temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*10**i
    cum[i] = temp
    cum[i] = cum[i]%p
cum = [0]+cum

#print(cum)

d = {}
ans = 0
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
print(ans)


### FIXED CODE ###

n, p = map(int, input().split())
s =list(str(input()))
s = [int(c) for c in s]
s.reverse()

if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if s[i]%p == 0:
            ans += n-1-i+1
    print(ans)
    exit()


#print(s)

#s = [0] + s
#from itertools import accumulate
#cum =list(accumulate(s))
#cum = [c%p for c in cum]

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*power(10, i, p)
    temp = temp%p
    cum[i] = temp
cum = [0]+cum

#print(cum)

d = {}
ans = 0
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
print(ans)
### BUGGY CODE ###

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

l = []
r = []
for i in range(k):
  a, b = map(int, input().split())
  l.append(a)
  r.append(b)

mod = 998244353

dp = [0] * (n + 1)
#１マス目の行き方は１通り
dp[1] = 1
dpsum = [0] * (n + 1)
dpsum[1] = 1
for i in range(2, n + 1):
  for j in range(k):
    li = i - r[j]
    ri = i - l[j]
    if ri < 0:
      continue
    li = max(1, li)

    dp[i] += dpsum[ri] - dpsum[li - 1]
  
  dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[n] % mod)



### FIXED CODE ###

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

l = []
r = []
for i in range(k):
  a, b = map(int, input().split())
  l.append(a)
  r.append(b)

mod = 998244353

dp = [0] * (n + 1)
#１マス目の行き方は１通り
dp[1] = 1
dpsum = [0] * (n + 1)
dpsum[1] = 1
for i in range(2, n + 1):
  for j in range(k):
    li = i - r[j]
    ri = i - l[j]
    if ri < 0:
      continue
    li = max(1, li)

    dp[i] += (dpsum[ri] - dpsum[li - 1]) % mod
  
  dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[n] % mod)
### BUGGY CODE ###

from functools import lru_cache

n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

@lru_cache(maxsize=None)
def f(i):
  cnt = 0
  while i > 0:
    # if box[i] != 0:
    #   return box[i]
    i %= bin(i).count("1")
    cnt += 1
  return cnt

for i in range(lenx):
  if x[i] == "0":
    t = x10 + 2 ** (lenx - 1 - i)
  else:
    t = x10 - 2 ** (lenx - 1 - i)
  print(f(t))

### FIXED CODE ###

n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

maxbit = x.count("1")
xc0 = x10 % (maxbit + 1)
xc1 = x10 % (maxbit - 1) if maxbit > 1 else 0

def f(ii):
  cnt = 0
  while ii > 0:
    ii %= bin(ii).count("1")
    cnt += 1
  return cnt

for i in range(lenx):
  if x[i] == "0":
    t = xc0 + pow(2, (lenx - 1 - i), maxbit + 1)
    ans = f(t % (maxbit + 1)) + 1
  else:
    if maxbit - 1 == 0:
      ans = 0
    else:
      t = xc1 - pow(2, (lenx - 1 - i), maxbit - 1)
      ans = f(t % (maxbit - 1)) + 1
  print(ans)
### BUGGY CODE ###

# https://agc023.contest.atcoder.jp/tasks/agc023_a

N = list(map(int, input()))[0]

li = list(map(int, input().split()))

# print(N)
#
# print(li)


counter = []

found = 0

for i in li:
    for j in range(len(counter)):
        counter[j] += i
        if counter[j] == 0:
            found += 1
    counter.append(i)
    if i == 0:
        found += 1

print(found)



### FIXED CODE ###

# https://agc023.contest.atcoder.jp/tasks/agc023_a

import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def convert_map(l):
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


N = list(map(int, input()))[0]

li = list(map(int, input().split()))

counter = [0]
for i in li:
    counter.append(counter[-1] + i)

# print(counter)

d = convert_map(counter)

# print(d)

patterns = 0
for key, value in d.items():
    if value >= 2:
        patterns += combinations_count(value, 2)

print(patterns)
### BUGGY CODE ###

n, m = map(int, input().split())

g = [[] for _ in range(1005)]

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

vis = [0] * 1005


def dfs(x, p):
    if vis[x]:
        return []
    p.append(x)
    vis[x] = 1
    for v in g[x]:
        if v in p:
            return p
        t = dfs(v, p)
        if len(t):
            return t
    p.pop()
    return []


tmp = 0
ans = 10 ** 10
tmpp = []
p = []
vs = [0] * 1005


def dfs2(x):
    global ans, p, tmp, tmpp
    if len(p) >= ans:
        return
    p.append(x)
    for v in g[x]:
        if v == tmp:
            ans = len(p)
            tmpp = p[:]
            continue
        if not vs[v]:
            vs[v] = 1
            dfs2(v)
            vs[v] = 0
    p.pop()


a = []
for i in range(1, 1 + n):
    tmp = i
    p = []
    dfs2(i)
    if len(tmpp) == ans:
        a = tmpp[:]

if not len(a):
    print(-1)
    exit(0)

print(len(a))
for i in a:
    print(i)

#
# pre = t[0]
# next = [0] * 1005
# for i in range(1, len(t)):
#     now = t[i]
#     next[pre] = now
#     pre = now
# next[t[-1]] = t[0]
# s = set()
# for i in t:
#     s.add(i)
#
# cnt = 0
# now = t[0]
# while cnt < len(s):
#     cnt += 1
#     for i in g[now]:
#         if i == next[now]:
#             continue
#         if i in s:
#             cnt = 0
#             k = next[now]
#             while k != i:
#                 s.remove(k)
#                 k = next[k]
#             next[now] = i
#     now = next[now]
#
# print(len(s))
# for i in s:
#     print(i)


### FIXED CODE ###

n, m = map(int, input().split())

g = [[] for _ in range(1005)]

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

vis = [0] * 1005


def dfs(x, p):
    if vis[x]:
        return []
    p.append(x)
    vis[x] = 1
    for v in g[x]:
        if v in p:
            return p
        t = dfs(v, p)
        if len(t):
            return t
    p.pop()
    return []


t = []
for i in range(1, 1 + n):
    t = dfs(i, [])
    if len(t):
        print(0)
        exit(0)

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

import sys
sys.setrecursionlimit(10**8)
from functools import lru_cache

T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    if S[-1]=='1':
        print(1)
        continue

    @lru_cache(maxsize=10**7)
    def rec(i,x):
        if i==N:
            return 1 if x>0 else 0
        if S[i]=='0':
            a = rec(i+1,x^A[i])
            if a == 0: ret = 0
            else:
                b = rec(i+1,x)
                ret = b
        else:
            a = rec(i+1,x^A[i])
            if a == 1: ret = 1
            else:
                b = rec(i+1,x)
                ret = b
        return ret
    print(rec(0,0))

### FIXED CODE ###

def gauss_jordan(bs):
    rank = 0
    pivot_cols = []
    for col in reversed(range(61)):
        pivot = -1
        for i,row in enumerate(bs[rank:]):
            if row&(1<<col):
                pivot = rank+i
                break
        if pivot < 0: continue
        pivot_cols.append(col)
        bs[pivot],bs[rank] = bs[rank],bs[pivot]
        for i,row in enumerate(bs):
            if i != rank and row&(1<<col):
                bs[i] ^= bs[rank]
        rank += 1
    return bs

def solve():
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    bs = []
    for a,s in zip(A[::-1],S[::-1]):
        x = a
        for b in bs:
            x = min(x, x^b)
        if x:
            if s=='0':
                bs.append(x)
                bs = gauss_jordan(bs)
            else:
                return 1
    return 0

T = int(input())
for _ in range(T):
    print(solve())