Two bored soldiers are playing card war. Their card deck consists of exactly n cards, numbered from 1 to n, all values are different. They divide cards between them in some manner, it's possible that they have different number of cards. Then they play a "war"-like card game. 

The rules are following. On each turn a fight happens. Each of them picks card from the top of his stack and puts on the table. The one whose card value is bigger wins this fight and takes both cards from the table to the bottom of his stack. More precisely, he first takes his opponent's card and puts to the bottom of his stack, and then he puts his card to the bottom of his stack. If after some turn one of the player's stack becomes empty, he loses and the other one wins. 

You have to calculate how many fights will happen and who will win the game, or state that game won't end.


-----Input-----

First line contains a single integer n (2 ≤ n ≤ 10), the number of cards.

Second line contains integer k_1 (1 ≤ k_1 ≤ n - 1), the number of the first soldier's cards. Then follow k_1 integers that are the values on the first soldier's cards, from top to bottom of his stack.

Third line contains integer k_2 (k_1 + k_2 = n), the number of the second soldier's cards. Then follow k_2 integers that are the values on the second soldier's cards, from top to bottom of his stack.

All card values are different.


-----Output-----

If somebody wins in this game, print 2 integers where the first one stands for the number of fights before end of game and the second one is 1 or 2 showing which player has won.

If the game won't end and will continue forever output  - 1.


-----Examples-----
Input
4
2 1 3
2 4 2

Output
6 2
Input
3
1 2
2 1 3

Output
-1


-----Note-----

First sample:  [Image] 

Second sample:  [Image]

Difficulty: interview

Starter code:

Solutions:
n = int(input())
k1 = list(map(int, input().split()[1:]))
k2 = list(map(int, input().split()[1:]))

i = 0
while True:
    if len(k1) == 0 or len(k2) == 0:
        break
    if i > 10000:
        break
    if k1[0] > k2[0]:
        k1 = k1[1:] + k2[0:1] + k1[0:1]
        k2 = k2[1:]
    else:
        k2 = k2[1:] + k1[0:1] + k2[0:1]
        k1 = k1[1:]
    i += 1

if i > 10000:
    print(-1)
else:
    winner = 1
    if len(k1) == 0:
        winner = 2
    print(i, winner)


__author__ = 'Andrey'
import collections
import time
start = time.time()
n = int(input())
cards_1 = collections.deque(list(map(int, input().split()))[1:])
cards_2 = collections.deque(list(map(int, input().split()))[1:])
c = 0
bad = False
while cards_1 and cards_2:
    end = time.time()
    if end - start > 1.85:
        bad = True
        break
    n_1 = cards_1.popleft()
    n_2 = cards_2.popleft()
    c += 1
    if n_1 > n_2:
        cards_1.append(n_2)
        cards_1.append(n_1)
    else:
        cards_2.append(n_1)
        cards_2.append(n_2)
else:
    print(c, 1 if cards_1 else 2)
if bad:
    print(-1)


n = int(input())
a = list(map(int, input().split()))[1:]
b = list(map(int, input().split()))[1:]

used = set()
cnt = 0
while len(a) != 0 and len(b) != 0:
    if (tuple(a), tuple(b)) not in used:
        used.add((tuple(a), tuple(b)))
    else:
        print(-1)
        return
    x, y = a.pop(0), b.pop(0)
    if x > y:
        a.append(y)
        a.append(x)
    else:
        b.append(x)
        b.append(y)
    cnt += 1
print(cnt, '1' if len(b) == 0 else '2')


N = input()
s1 = input().split(' ')[1:]
s2 = input().split(' ')[1:]

s1 = tuple(map(int, s1))
s2 = tuple(map(int, s2))

already_seen = set()
num_fights = 0

while len(s1) > 0 and len(s2) > 0:

    num_fights += 1

    if (s1, s2) in already_seen:
        break
    else:
        already_seen.add((s1, s2))

    if s1[0] < s2[0]:
        s2 = s2[1:] + (s1[0], s2[0])
        s1 = s1[1:]
    else:
        s1 = s1[1:] + (s2[0], s1[0])
        s2 = s2[1:]

if len(s1) == 0:
    print(str(num_fights) + ' 2')
elif len(s2) == 0:
    print(str(num_fights) + ' 1')
else:
    print(-1)

n=int(input())
s1=list(map(int, input().split()))
s1.pop(0)
s2=list(map(int, input().split()))
s2.pop(0)
#print(s1, s2, n)
c=0
while s1 and s2 and c<10**5:
    if s1[0]>s2[0]:
        s1.append(s2[0])
        s1.append(s1[0])
    else:
        s2.append(s1[0])
        s2.append(s2[0])
    s1.pop(0)
    s2.pop(0)
    c+=1
if not(s1):
    print(c, 2)
elif not(s2):
    print(c, 1)
else:
    print(-1)

n = int(input())
sol_1 = list(map(int, input().split()))
l1 = sol_1[0]
s1 = l1
sol_1 = sol_1[1:]
sol_2 = list(map(int, input().split()))
l2 = sol_2[0]
s2 = l2
sol_2 = sol_2[1:]
i = 0
j = 0
sol_11 = []
sol_22 = []
p = 10000
c = 0
while s1 != 0 and s2 != 0 and p > 0:
    if i == len(sol_1):
        i = 0
        sol_1 = sol_11[:]
        sol_11 = []
    if j == len(sol_2):
        j = 0
        sol_2 = sol_22[:]
        sol_22 = []    
    if sol_1[i] > sol_2[j]:
        sol_11.append(sol_2[j])
        sol_11.append(sol_1[i])
        s1 += 1
        s2 -= 1
    else:
        sol_22.append(sol_1[i])
        sol_22.append(sol_2[j])    
        s2 += 1
        s1 -= 1
    i += 1
    j += 1
    c += 1
    p -= 1
if p == 0:
    print(-1)
else:
    if s1 == 0:
        print(c, '2')
    else:
        print(c, '1')

import sys
import collections


def get_code(first_cards, second_cards):
    c1 = 0
    for i, card in enumerate(first_cards):
        c1 += (card - 1) * 10**i
    c2 = 0
    for i, card in enumerate(second_cards):
        c2 += (card - 1) * 10**i
    return (c1, c2)


def main():
    n = int(sys.stdin.readline())
    first_cards = collections.deque(reversed(list(map(int, sys.stdin.readline().split()))[1:]))
    second_cards = collections.deque(reversed(list(map(int, sys.stdin.readline().split()))[1:]))


    existing_states = set()
    number_of_fights = 0

    while first_cards and second_cards:
        # code = get_code(first_cards, second_cards)
        code = (tuple(first_cards), tuple(second_cards))
        if code in existing_states:
            print (-1)
            return
        existing_states.add(code)

        if first_cards[-1] > second_cards[-1]:
            first_cards.appendleft(second_cards.pop())
            first_cards.appendleft(first_cards.pop())
        else:
            second_cards.appendleft(first_cards.pop())
            second_cards.appendleft(second_cards.pop())
        number_of_fights += 1

    print ('%d %d' % (number_of_fights, 1 if not second_cards else 2))


def __starting_point():
    main()
__starting_point()


n = int(input())
l1 = [int(i) for i in input().split()]
k1 = l1.pop(0)
#print (k1, l1)
l1.reverse()
l2 = [int(i) for i in input().split()]
k2 = l2.pop(0)
l2.reverse()
#print(k1, k2, l1, l2)
i = 0
dup = set()
while len(l1) > 0 and len(l2) > 0:
    c = tuple(l1 + [0.5] + l2)
    #print (c)
    if c in dup:
        break
    dup.add(c) 
    a = l1.pop()
    b = l2.pop()
    if a>b:
        l1.insert(0,b)
        l1.insert(0,a)
    else:
        l2.insert(0,a)
        l2.insert(0,b)
    #print(l1,l2)
    i+=1
if len(l1) == 0:
    print (i, 2)
elif len(l2) == 0:
    print (i,1)
else:
    print(-1)

import sys

n = int(input())
d1 = list(map(int, input().split(" ")))
d2 = list(map(int, input().split(" ")))
k1 = d1[0]
k2 = d2[0]
d1.remove(d1[0])
d2.remove(d2[0])

moves = 0

while True:
    if moves > 500000:
        print(-1)
        return
    a = d1[0]
    d1.remove(d1[0])
    b = d2[0]
    d2.remove(d2[0])
    if a > b:
        moves += 1
        d1.append(b)
        d1.append(a)
        if len(d2) == 0:
            print(str(moves) + " 1")
            return
    if b > a:
        moves +=1
        d2.append(a)
        d2.append(b)
        if len(d1) == 0:
            print(str(moves) + " 2")
            return

n = int(input())
s1 = [int(x) for x in input().split()]
s1.pop(0)
s2 = [int(x) for x in input().split()]
s2.pop(0)
c = 0
chk = [[False for x in range(11)] for x in range(11)]
while(True):
	if(c > 1000):
		print(-1)
		return
	
	if(not s1 or not s2):
		print(c,1 if not s2 else 2)
		return
	else:
		chk[s1[0]][s2[0]] = True
		if(s1[0] > s2[0]):
			s1.append(s2[0])
			s1.append(s1[0])
			s1.pop(0)
			s2.pop(0)
		else:
			s2.append(s1[0])
			s2.append(s2[0])
			s1.pop(0)
			s2.pop(0)
		c += 1


n = int(input())
s1 = [int(i) for i in input().split()]
s1.pop(0)
s2 = [int(i) for i in input().split()]
s2.pop(0)
t = 0
while s1 and s2:
    t += 1
    a = s1.pop(0)
    b = s2.pop(0)
    if a > b:
        s1.append(b)
        s1.append(a)
    else:
        s2.append(a)
        s2.append(b)
    if t>1000:
        break
if t>1000:
    print(-1)
else:
    if s1:
        print(t, 1)
    else:
        print(t, 2)


def comp(a,b):
	if(len(a) != len(b)):
		return False
	n = len(a)
	for i in range(n):
		if(a[i] != b[i]):
			return False
	return True

n = int(input())

a = []
b = []

a = list(map(int,input().split()))
b = list(map(int,input().split()))

k1 = a[0]
k2 = b[0]

del a[0]
del b[0]

p = []
q = []

for i in a:
	p.append(i)

for i in b:
	q.append(i)

#print(a)
#print(b)

total = 0
flag = True

while(True):
	x = a[0]
	y = b[0]
	if(x > y):
		a.pop(0)
		b.pop(0)
		a.append(y)
		a.append(x)
	else:
		a.pop(0)
		b.pop(0)
		b.append(x)
		b.append(y)
	#print(a,b)
	total += 1
	if((p == a and q == b) or total >= 100000):
		flag = False
		break
	if(len(a) == 0 or len(b) == 0):
		break

if(flag == False):
	print(-1)
else:
	if(a == []):
		print(total,2)
	else:
		print(total,1)

# coding:utf-8

n = int(input())
f_deck = list(map(int, input().split(' ')))[1:]
s_deck = list(map(int, input().split(' ')))[1:]

# print('- - - - -')
idx = 0
rec = []
while 1:
    # print('-')
    # print(f_deck)
    # print(s_deck)
    rec.append(''.join(list(map(str,f_deck))) +'_'+ ''.join(list(map(str,s_deck))))
    if f_deck[0] > s_deck[0]:
        f_deck.append(s_deck.pop(0))
        f_deck.append(f_deck.pop(0))
    else:
        s_deck.append(f_deck.pop(0))
        s_deck.append(s_deck.pop(0))
    idx += 1
    if ''.join(list(map(str,f_deck))) +'_'+ ''.join(list(map(str,s_deck))) in rec:
        break
    if len(f_deck) == 0 or len(s_deck) == 0:
        break
    # if idx>5000000:
    #     break
if len(f_deck) == 0:
    print("{} {}".format(idx,2))
elif len(s_deck) == 0:
    print("{} {}".format(idx,1))
else:
    print(-1)

'''
Input
4
2 1 3
2 4 2
Output
6 2

Input
3
1 2
2 1 3
Output
-1
'''

from collections import deque
from copy import deepcopy
n = int(input())
A = deque(list(map(int, input().split()))[1:])
B = deque(list(map(int, input().split()))[1:])
state = []
state.append((deepcopy(A), deepcopy(B)))
cnt = 0
while len(A) > 0 and len(B) > 0:
    if A[0] > B[0]:
        A.append(B.popleft())
        A.append(A.popleft())
    else:
        B.append(A.popleft())
        B.append(B.popleft())
    if (A, B) in state:
        print(-1)
        break
    state.append((deepcopy(A), deepcopy(B)))
    cnt += 1
else:
    print(cnt, 1 if len(B) == 0 else 2)


def fight(k1, k2):
    l = k1.pop(0)
    r = k2.pop(0)
    if l < r:
        k2.extend([l, r])
    else:
        k1.extend([r, l])


n = int(input())
k1 = list(map(int, input().split()))
k1.pop(0)
k2 = list(map(int, input().split()))
k2.pop(0)

combs = set()
fights = 0
while k1 and k2:
    topcomb = (''.join(map(str, k1)), ''.join(map(str, k2)))
    if topcomb in combs:
#        print(fights)
        fights = -1
        break
    combs.add(topcomb)
    fight(k1, k2)
    fights += 1


print(fights, end=' ')
if fights > -1:
    print(1 if k1 else 2)

n=int(input())
a=list(map(int,input().split()))
k1=a[0]
s1=a[1:]
a=list(map(int,input().split()))
k2=a[0]
s2=a[1:]
flag=0
fights=0
count=0
while(len(s1)!=0 and len(s2)!=0):
    count+=1
    if count>1000000:
        flag=1
        break
    t=s1.pop(0)
    p=s2.pop(0)
    if t>p:
        s1.append(p)
        s1.append(t)
    else:
        s2.append(t)
        s2.append(p)
    fights+=1
if flag==1:
    print("-1")
else:
    if len(s1)==0:
        won="2"
    else :
        won="1"
    print(fights,won,sep=" ")




a = int(input())

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

num = 0
states = []
while len(x)>0 and len(y)>0:
	tx = x[0]
	ty = y[0]
	if tx > ty:
		x = x[1:] + [ty] + [tx]
		y = y[1:]
	else:
		y = y[1:] + [tx] + [ty]
		x = x[1:]
	num += 1
	
	states.append([x, y])
	
	if num > 10**5:
		if [x, y] in states:
			print(-1)
			quit()
	
if x == []:
	print(num, 2)
else:
	print(num, 1)


n = int(input())
a = list((map(int,input().split())))
b = list((map(int,input().split())))
k,l = a[0],b[0]
a.pop(0)
b.pop(0)
cnt = 0
while len(a)>0 and len(b)>0 and cnt<1000:
    if a[0]>b[0]:
        a.append(b[0])
        a.append(a[0])

    if b[0]>a[0]:
        b.append(a[0])
        b.append(b[0])

    cnt+=1
    a.pop(0)
    b.pop(0)
if len(a)==0: #or i==len(b)-1:
        print(cnt,2)
        quit()
if len(b)==0:
        print(cnt,1)
        quit()
if len(a)>0 and len(b)>0:
    print(-1)
else:
    print(cnt)

n = int(input())
list1 = list(map(int, input().split()))
list2 = list(map(int, input().split()))
k1 = list1[0]
del list1[0]
k2 = list2[0]
del list2[0]
i = 0
count = 0
while(len(list1) != 0 and len(list2) != 0):
    if(list1[i] < list2[i]):
        list2.append(list1[i])
        list2.append(list2[i])
        del list1[i]
        del list2[i]
        count += 1
    elif(list2[i] < list1[i]):
        list1.append(list2[i])
        list1.append(list1[i])
        del list1[i]
        del list2[i]
        count += 1
    else:
        del list1[i]
        del list2[i]
    if count == n**2+10:
        print("-1")
        break
if len(list1) == 0:
    print("{} 2".format(count))
if len(list2) == 0:
    print("{} 1".format(count))

n = int(input())

s1 = [ int(card) for card in input().split() ]
s2 = [ int(card) for card in input().split() ]

s1 = s1[1:]
s2 = s2[1:]

magic = 1000000

fights = 0
flag = False
while True:
	card1, card2 = s1.pop(0), s2.pop(0)

	fights += 1
	if fights > magic:
		flag = True
		break

	if card1 > card2:
		s1.append(card2)
		s1.append(card1)
	else:
		s2.append(card1)
		s2.append(card2)

	if s1 == []:
		winner = 2
		break
	if s2 == []:
		winner = 1
		break

if flag:
	print(-1)
else:
	print(fights, winner)

#!/usr/bin/env python
# -*- coding: utf-8 -*-

n = int(input())
c1 = list(map(int,input().split()))[1:]
c2 = list(map(int,input().split()))[1:]

def check(c1,c2):
    t1,t2 = c1.pop(0),c2.pop(0)
    if t1 < t2:
        c2 += [t1,t2]
    else:
        c1 += [t2,t1]

count = 0
while c1 != [] and c2 != []:
    prev_c1,prev_c2 = c1[:],c2[:]
    check(c1,c2)
    if count > 10000:
        break
    count += 1
else:
    print(count, 2 if c1 == [] else 1)
    quit()
print(-1)


x=int(input())
A=list(map(int,input().split()))
A=A[1:]
#print(A)
D=A
#print(D)
B=list(map(int,input().split()))
B=B[1:]
E=B
C=[]
#print(A)
#print(B)
count=0
num=1000
while(num>0):
	if count==999:
		state=10000
		break
	#print(D)
	state=-100
	if A==C:
		state=10
		break
	if B==C:
		state=100
		break
	if A[0]>B[0]:
		A.append(B[0])
		A.append(A[0])
		A=A[1:]
		B=B[1:]
		count=count+1
		#print(A,B)
		state=0
		num=num-1
	if state!=0:	
		if B[0]>A[0]:
			B.append(A[0])
			B.append(B[0])
			B=B[1:]
			A=A[1:]
			count=count+1
			#print(A,B)
			num=num-1
	#if A==D:
	#	if B==E:
	#		state=1000
	#		break
	#if A==E:
	#	if B==D:
	#		state=1000
	#		break
if state==10:
	print(count,2)
if state==100:
	print(count,1)
if state==10000:
	print(-1)


x=int(input())
A=list(map(int,input().split()))
A=A[1:]
#print(A)
D=A
#print(D)
B=list(map(int,input().split()))
B=B[1:]
E=B
C=[]
#print(A)
#print(B)
count=0
num=1000
while(num>0):
	if count==999:
		state=10000
		break
	#print(D)
	state=-100
	if A==C:
		state=10
		break
	if B==C:
		state=100
		break
	if A[0]>B[0]:
		A.append(B[0])
		A.append(A[0])
		A=A[1:]
		B=B[1:]
		count=count+1
		#print(A,B)
		state=0
		num=num-1
	if state!=0:	
		if B[0]>A[0]:
			B.append(A[0])
			B.append(B[0])
			B=B[1:]
			A=A[1:]
			count=count+1
			#print(A,B)
			num=num-1
	#if A==D:
	#	if B==E:
	#		state=1000
	#		break
	#if A==E:
	#	if B==D:
	#		state=1000
	#		break
if state==10:
	print(count,2)
if state==100:
	print(count,1)
#CODE BASED ON THE TEST CASES
#MAHESH JASTI
#IIIT HYDERABAD
if state==10000:
	print(-1)