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.

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 a_j and b_j (1 ≤ a_j < b_j ≤ 6n). All these pairs are distinct.

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.