IUST Problem F

Time Limit: 2 Seconds    Memory Limit: 32768 KB

The people of the city want to elect a mayor from among some candidates. Each person has only one vote. There is a man behind the scenes who wants to change the result of the election. He wants to do that by making people meet each other. It is known that if two groups of people meet, they start to debate about the election and change the minds of other group’s members in the way described below:

 

1: If member x1 is in the first group and he wants to vote for p1, if there is at least one other person like y1 in the other group who also wants to vote for, p1, his opinion doesn’t change.

 

2: If member x2 is in the first group and he wants to vote for p1, if there is no other person voting for p1 in the other group, one of these happens:

 

2.1: If a candidate like p2 has more votes than any other candidate in the other group, x2 changes his vote to p2.

 

2.2: If there isn’t a definite candidate who has the most votes in the other group (For example if p3 and p4 both have the same number of votes, which is more than any other candidate, in that group), p2’s opinion doesn’t change.

 

3: People won’t state their new candidate choice before the meeting is completely finished, so, if someone changed his vote, other people won’t know that before the meeting has finished. This means that to change votes, people look at the state of the other group’s members’ votes before the start of the meeting.

 

4: After a meeting, members of the two groups will merge and form a single new group consisting of all of them.

 

5: At the start, there is no group with more than one members.

 

6: Each person is always a member of one, and only one group.

 

To facilitate a meeting, the man behind the scenes invites two people to meet each other, knowing well that both of them will bring their respective groups to the meeting.

 

Your goal is to write a program that, given the initial opinion of the people, and the man behind the scene’s plan of meetings, prints each person’s votes after all of the meetings have taken place.

Input

Input consists of number N (N < 10000), which is the number of the people of the city, followed by each person’s vote (which is a non-negative integer less than 10). After that, it gets M, which is the number of planned meetings, followed by pairs of numbers, representing the index of the people who are going to meet. The meetings are sequential, which means that each one happens after the previous one is finished.

 

Output

Output is the vote of each person after the meetings, which are separated by a new line.

 

Sample Input

4
9
3
3
2
4
1 2
3 2
2 0
3 0

Sample Output

2
9
9
9

Submit

Source: 12th Iran Nationwide Internet Contest II