You are given *n* strings *s*<sub class="lower-index">1</sub>, *s*<sub class="lower-index">2</sub>, ..., *s*<sub class="lower-index">*n*</sub> consisting of characters 0 and 1. *m* operations are performed, on each of them you concatenate two existing strings into a new one. On the *i*-th operation the concatenation *s*<sub class="lower-index">*a*<sub class="lower-index">*i*</sub></sub>*s*<sub class="lower-index">*b*<sub class="lower-index">*i*</sub></sub> is saved into a new string *s*<sub class="lower-index">*n* + *i*</sub> (the operations are numbered starting from 1). After each operation you need to find the maximum positive integer *k* such that all possible strings consisting of 0 and 1 of length *k* (there are 2<sup class="upper-index">*k*</sup> such strings) are substrings of the new string. If there is no such *k*, print 0.
The first line contains single integer *n* (1 ≤ *n* ≤ 100) — the number of strings. The next *n* lines contain strings *s*<sub class="lower-index">1</sub>, *s*<sub class="lower-index">2</sub>, ..., *s*<sub class="lower-index">*n*</sub> (1 ≤ |*s*<sub class="lower-index">*i*</sub>| ≤ 100), one per line. The total length of strings is not greater than 100.

The next line contains single integer *m* (1 ≤ *m* ≤ 100) — the number of operations. *m* lines follow, each of them contains two integers *a*<sub class="lower-index">*i*</sub> abd *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *n* + *i* - 1) — the number of strings that are concatenated to form *s*<sub class="lower-index">*n* + *i*</sub>.
On the first operation, a new string "0110" is created. For *k* = 1 the two possible binary strings of length *k* are "0" and "1", they are substrings of the new string. For *k* = 2 and greater there exist strings of length *k* that do not appear in this string (for *k* = 2 such string is "00"). So the answer is 1.

On the second operation the string "01100" is created. Now all strings of length *k* = 2 are present.

On the third operation the string "1111111111" is created. There is no zero, so the answer is 0.
5
01
10
101
11111
0
3
1 2
6 5
4 4
1
2
0
5
01
1
0011
0
01
6
5 5
3 2
4 2
6 7
5 1
9 7
1
1
1
2
1
2
5
111101000111100011100110000100
000111001
01101000
0000110100100010011001000000010100100111110110
0110001
10
5 5
2 2
5 6
1 1
1 7
10 6
6 2
11 1
3 6
8 2
2
2
2
3
3
4
3
4
2
3
1
1
1
1 1
0
5
110101010101010110000011011
111111
1000100011100111100101101010011111100000001001
00
1111101100001110000
10
4 3
6 6
7 5
8 8
8 7
10 8
11 9
10 12
13 13
12 13
4
4
4
4
4
4
4
4
4
4
5
100010010
0
1001100110010111
0001000011000111000011011000110000010010010001110001000011011
0100000100100
10
5 5
6 6
6 7
7 8
8 9
10 8
11 9
10 9
12 13
12 13
1
1
1
1
1
1
1
1
1
1
5
0
1
11
110000010001100101001
1101011011111
10
5 3
6 4
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
1
4
5
5
5
5
5
5
5
5
10
0
1
1111100000
0
1
0000
11000
1010001110010010110
01101001111
010101110110111111
20
10 3
11 4
12 5
13 6
14 7
15 8
16 9
17 16
18 17
19 18
20 19
21 20
22 21
23 22
24 23
25 24
26 25
27 26
28 27
29 28
2
2
3
3
3
4
5
6
6
6
6
6
6
6
6
6
6
6
6
6
10
0
1
1111
110000000
100000
1
1
000010100001110001
00100010110001101000111100100110010101001011
100110110011101
50
10 3
11 4
12 5
13 6
14 7
15 8
16 9
17 1
18 1
19 2
20 2
21 2
22 2
23 2
24 1
25 2
26 1
27 2
28 1
29 2
30 2
31 1
32 2
33 1
34 2
35 2
36 2
37 2
38 1
39 2
40 2
41 1
42 2
43 2
44 2
45 1
46 2
47 2
48 2
49 2
50 2
51 2
52 2
53 52
54 53
55 54
56 55
57 56
58 57
59 58
2
2
3
3
3
4
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
2
001010011100101110111
001100110011001100110011001100110011001100110011001100111001
14
1 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
0
40
1 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
011
100
63
1 1
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
2 2
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 51
52 52
53 53
54 54
55 55
56 56
57 57
58 58
59 59
60 60
61 61
62 62
63 63
33 64
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
0000000000000000000000000000000000000000000000000000000000000000
25
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
# coding=utf-8
import random
import re
import time
import threading
import requests
from bs4 import BeautifulSoup
from lxml import etree

#Username
name='' 
#Password
password=''

user_agent = [
	'Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_6_8; en-us) AppleWebKit/534.50 (KHTML, like Gecko) Version/5.1 '
	'Safari/534.50',
	'Mozilla/5.0 (Windows; U; Windows NT 6.1; en-us) AppleWebKit/534.50 (KHTML, like Gecko) Version/5.1 Safari/534.50',
	'Mozilla/5.0 (Windows NT 10.0; WOW64; rv:38.0) Gecko/20100101 Firefox/38.0',
	'Mozilla/5.0 (Windows NT 10.0; WOW64; Trident/7.0; .NET4.0C; .NET4.0E; .NET CLR 2.0.50727; .NET CLR 3.0.30729; '
	'.NET CLR 3.5.30729; InfoPath.3; rv:11.0) like Gecko',
	'Mozilla/5.0 (compatible; MSIE 9.0; Windows NT 6.1; Trident/5.0)',
	'Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.0; Trident/4.0)',
	'Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 6.0)',
	'Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1)',
	'Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:2.0.1) Gecko/20100101 Firefox/4.0.1',
	'Mozilla/5.0 (Windows NT 6.1; rv:2.0.1) Gecko/20100101 Firefox/4.0.1',
	'Opera/9.80 (Macintosh; Intel Mac OS X 10.6.8; U; en) Presto/2.8.131 Version/11.11',
	'Opera/9.80 (Windows NT 6.1; U; en) Presto/2.8.131 Version/11.11',
	'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_7_0) AppleWebKit/535.11 (KHTML, like Gecko) Chrome/17.0.963.56 '
	'Safari/535.11',
	'Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; Maxthon 2.0)',
	'Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; TencentTraveler 4.0)',
	'Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1)',
	'Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; The World)',
	'Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; Trident/4.0; SE 2.X MetaSr 1.0; SE 2.X MetaSr 1.0; .NET CLR '
	'2.0.50727; SE 2.X MetaSr 1.0)',
	'Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; 360SE)',
	'Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; Avant Browser)',
	'Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1)',
	'Mozilla/5.0 (iPhone; U; CPU iPhone OS 4_3_3 like Mac OS X; en-us) AppleWebKit/533.17.9 (KHTML, like Gecko) '
	'Version/5.0.2 Mobile/8J2 Safari/6533.18.5',
	'Mozilla/5.0 (iPod; U; CPU iPhone OS 4_3_3 like Mac OS X; en-us) AppleWebKit/533.17.9 (KHTML, like Gecko) '
	'Version/5.0.2 Mobile/8J2 Safari/6533.18.5',
	'Mozilla/5.0 (iPad; U; CPU OS 4_3_3 like Mac OS X; en-us) AppleWebKit/533.17.9 (KHTML, like Gecko) Version/5.0.2 '
	'Mobile/8J2 Safari/6533.18.5',
	'Mozilla/5.0 (Linux; U; Android 2.3.7; en-us; Nexus One Build/FRF91) AppleWebKit/533.1 (KHTML, like Gecko) '
	'Version/4.0 Mobile Safari/533.1',
	'MQQBrowser/26 Mozilla/5.0 (Linux; U; Android 2.3.7; zh-cn; MB200 Build/GRJ22; CyanogenMod-7) AppleWebKit/533.1 ('
	'KHTML, like Gecko) Version/4.0 Mobile Safari/533.1',
	'Opera/9.80 (Android 2.3.4; Linux; Opera Mobi/build-1107180945; U; en-GB) Presto/2.8.149 Version/11.10',
	'Mozilla/5.0 (Linux; U; Android 3.0; en-us; Xoom Build/HRI39) AppleWebKit/534.13 (KHTML, like Gecko) Version/4.0 '
	'Safari/534.13',
	'Mozilla/5.0 (BlackBerry; U; BlackBerry 9800; en) AppleWebKit/534.1+ (KHTML, like Gecko) Version/6.0.0.337 Mobile '
	'Safari/534.1+',
	'Mozilla/5.0 (hp-tablet; Linux; hpwOS/3.0.0; U; en-US) AppleWebKit/534.6 (KHTML, like Gecko) wOSBrowser/233.70 '
	'Safari/534.6 TouchPad/1.0',
	'Mozilla/5.0 (SymbianOS/9.4; Series60/5.0 NokiaN97-1/20.0.019; Profile/MIDP-2.1 Configuration/CLDC-1.1) '
	'AppleWebKit/525 (KHTML, like Gecko) BrowserNG/7.1.18124',
	'Mozilla/5.0 (compatible; MSIE 9.0; Windows Phone OS 7.5; Trident/5.0; IEMobile/9.0; HTC; Titan)',
	'UCWEB7.0.2.37/28/999',
	'NOKIA5700/ UCWEB7.0.2.37/28/999',
	'Openwave/ UCWEB7.0.2.37/28/999',
	'Mozilla/4.0 (compatible; MSIE 6.0; ) Opera/UCWEB7.0.2.37/28/999', ]
s=requests.session()
#login
def login():
	agent=random.choice(user_agent)
	header={'User-Agent' : agent}
	s.headers.update(header)
	try:
		res = s.get('http://codeforces.com/enter?back=%2F')
		soup=BeautifulSoup(res.text,'lxml')
		csrf_token=soup.find(attrs={'name' : 'X-Csrf-Token'}).get('content')
		form_data={
			'csrf_token' : csrf_token,
			'action' : 'enter',
			'ftaa' : '',
			'bfaa' : '',
			'handleOrEmail' : name,
			'password' : password,
			'remember' : []
		}
		s.post('http://codeforces.com/enter',data=form_data)
	except Exception as e:
		print('Login Failed.',e)
#getcode
def getcode(a,b) :
	try:
		res=s.get('http://codeforces.com/problemset/submit')
		soup=BeautifulSoup(res.text,'lxml')
		csrf_token=soup.find(attrs={'name' : 'X-Csrf-Token'}).get('content')
		data={
			'csrf_token' : csrf_token,
			'action' : 'setupSubmissionFilter',
			'frameProblemIndex' : b,
			'verdictName' : 'OK',
			'programTypeForInvoker' : 'cpp.g++11',
			'comparisonType' : 'NOT_USED',
			'judgedTestCount' : '',
		}
		s.post('https://codeforces.com/contest/'+a+'/status',data=data)
		res=s.get('https://codeforces.com/contest/'+a+'/status')
		links=re.findall('submission/(.+?)"',res.text)
		if len(links)<=0 :
			return False
		res2=s.get('https://codeforces.com/contest/'+a+'/submission/'+links[0])
		selector=etree.HTML(res2.text)
		out=selector.xpath('//*[@id="program-source-text"]')[0]
	except Exception as e:
		print('Problem id:',a+b,'Failed to get the code.')
		print(e)
		exit(0)
	return out.text


def uploadcode(a,b,code) :
	res=s.get('http://codeforces.com/problemset/submit')
	soup=BeautifulSoup(res.text,'lxml')
	csrf_token=soup.find(attrs={'name' : 'X-Csrf-Token'}).get('content')
	post_data={
		'csrf_token' : csrf_token,
		'ftaa' : '',
		'bfaa' : '',
		'action' : 'submitSolutionFormSubmitted',
		'submittedProblemCode' : a+b,
		'programTypeId' : '42',
		'source' : code,
		'tabSize' : 0,
		'sourceFile' : '',
	}
	res=s.post('http://codeforces.com/problemset/submit?csrf_token='+csrf_token,data=post_data)
	if res.status_code!=200 :
		print('Problem id:',a+b,'Failed to submit the code.')
		print(res)
		exit(0)
	else:
		print('Problem id:',a+b,'AC!!!')


def solve(a) :
	global s
	html=s.get('https://codeforces.com/contest/'+a).text
	if not html :
		return
	links=re.findall('<a href="/contest/'+a+'/problem/(.+?)"><!--',html)
	setlinks=set(links)
	links=list(setlinks)
	links.sort()
	for b in links :
		if len(b)<3 :
			uploadcode(a,b,getcode(a,b))
			time.sleep(2)
	print('solve:',a)


name=input('User id: ')
password=input('password: ')
login()
print("Login Successfully")
print('contest id:   Example: 1')
f = int(input('from (contest id):')) 
t = int(input('to (contest id):'))
for a in range(f,t+1) :
	#solve(str(a))
	threading.Thread(target=solve, args=(str(a),)).start()
	time.sleep(60)
