407416: GYM102787 A Shandom Ruffle

Memory Limit:1024 MB Time Limit:8 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Shandom Ruffletime limit per test8 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard 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); //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.

ExamplesInput
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.

加入题单

上一题 下一题 算法标签: