A. Shandom Ruffle
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Those of you who use Java (or are subscribed to SecondThread) likely know that calling Arrays.sort() on an array of primitives in Java can lead to TLE verdicts on Codeforces contests because there are some very specific cases in which quicksort runs in $$$n^2$$$ time. There are a couple solutions to this: one is to use Collections.sort() on an ArrayList. This uses mergesort and is always $$$n*log(n)$$$.

Another solution is to shandomly ruffle [aka randomly shuffle] the array before sorting so that it is very very very unlikely that it is still in some undesirable order. One way of doing this is to do the following:


shandom_ruffle(int a, int b, int[] array) {
  int bStart=b;
  while (a<bStart && b<=array.length) {
    swap(array[a], array[b]); //swap the values at indecies a and b
    a++;
    b++;
  }
}

In Java and the psuedocode above, arrays are pass-by-reference. Suppose David starts with the array $$$[1, 2, 3, 4, ... n]$$$, and calls this method $$$n$$$ times on the array, the ith time passing in $$$a_i$$$ and $$$b_i$$$. What will the array look like after these $$$n$$$ method calls?

Input

The first line will contain a single integer $$$n$$$. ($$$1 \leq n \leq 5*10^5$$$)

The following $$$n$$$ lines will each contain two integers $$$a_i$$$ and $$$b_i$$$. ($$$1 \leq a, b \leq n$$$) Note that $$$b$$$ may be less than or equal to $$$a$$$, in which case the method will not do anything.

Output

Print a single line containing n space-separated integers: the array after it has been shandomly ruffled all $$$n$$$ times.

Examples
Input
4
3 1
1 3
3 2
2 3
Output
3 1 4 2
Input
5
4 1
5 4
3 5
4 5
5 2
Output
1 2 5 3 4
Note

There's a much easier way to shandom_ruffle that takes $$$O(n)$$$, but that makes for a less interesting problem.