ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1859. Last Season of Team.GOV

Time limit: 0.5 second
Memory limit: 64 MB
Four regional contests, twelve different teammates… Twenty sixth place is not that bad indeed, but World Finals would have been much better. And now the career is over, Team.GOV project is closed. The road back home to Yekaterinburg, graduation, and master's degree in France are ahead…
These thoughts were running around the head of Vadim Kantorov when the dean's voice drew him back to reality:
“Vadim, whom do you want to share a compartment with?”
A compartment on a sleeping car contains four main couchettes and two side couchettes. There are exactly 6n people in the Ural SU delegation, that's why the dean bought tickets for n consecutive compartments of a sleeping car. Every delegation member said what type of couchette they like more: main or side. Apart from that, everyone wants to share a compartment with their friends. The delegation needs to decide who occupies which compartment so that all these requirements are satisfied.

Input

The first line contains an integer n (1 ≤ n ≤ 1000). The second line contains a bit string of length of 6n. i-th bit in this string is equal to 1 if the i-th delegation member wants to occupy a couchette of main type, and 0 if they want a couchette of side type. The next line contains an integer m that is the number of pairs of friends (0 ≤ m ≤ 15n). The next m lines contain all those pairs as integers aj and bj (1 ≤ aj < bj ≤ 6n). All these pairs are distinct.

Output

Output n lines. Each line should contain a space-separated list of delegation members who should occupy a compartment together. Each pair of friends should occupy the same compartment. The order of people in a single list can be arbitrary. The order of lists also does not matter. If there are multiple solutions, you can output any of them. It is guaranteed that at least one solution exists.

Sample

inputoutput
2
001111001111
2
1 2
7 8
1 2 3 4 5 6
7 8 9 10 11 12
Problem Author: Mikhail Rubinchik (idea by Dmitriy Kuznetsov)
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011