Input:
4
000000001111111111111111
8
4 5
6 7
8 15
16 17
17 18
19 20
21 22
23 24

Example output:
1 2 9 10 11 12
3 8 15 16 17 18
4 5 13 14 19 20
6 7 21 22 23 24


Input:
4
111010011110110110111100
15
1 2
2 3
3 4
5 6
8 9
9 10
11 12
13 14
14 15
16 17
19 20
20 21
21 22
22 23
23 24

Example output:
1 2 3 4 11 12
5 6 8 9 10 18
7 13 14 15 16 17
19 20 21 22 23 24


Input:
4
101101111001111001001111
14
1 2
3 4
4 5
7 8
8 9
9 10
10 11
13 14
15 16
16 17
19 20
21 22
22 23
23 24

Example output:
1 2 3 4 5 12
6 13 14 15 16 17
7 8 9 10 11 18
19 20 21 22 23 24


Input:
3
111111111111000000
9
1 2
1 13
3 4
5 6
6 7
8 15
10 16
11 17
12 18

Example output:
1 2 8 9 13 15
3 4 10 11 16 17
5 6 7 12 14 18