An array of N different natural numbers from 1 to N is given. works as follows. First, the first and second elements are compared, and if the first is greater than the second, then they are swapped. Then the same procedure is carried out with the second and third element, …, with the penultimate and last. Then this procedure is repeated again with the first and second, with the second and third, …, with the penultimate and last elements. And so (N & ndash; 1) times.
Sorting "with candy" is performed according to the same rules, but additionally given a list of pairs of numbers that do not change with each other under any conditions (in this case, the sorter gets a candy for missing the corresponding exchange). For example, the presence of a pair (4,1) in the list means that if at some point the numbers 4 and 1 or 1 and 4 are nearby, and according to the sorting algorithm they need to be swapped, then the exchange will not happen, and the sorter will get candy .
It is required to sort "with candy" given array and return the sort result.
Input
First enter the number N — the number of numbers in the array, then N numbers — array elements. Next, the number M — the number of pairs of numbers for which they give a candy, and then M pairs of numbers. If there is a pair (i,j) in the list, then the pair (j,i) also gets candy.
1≤ N≤ 5000.0≤ M≤ 10000.
Imprint
It is required to display the array after sorting.
Examples
| # |
Input |
Output |
| 1 |
4
1 4 2 3
2
4 3
1 2
| 1 2 4 3 |