atcoder#ABC253G. [ABC253G] Swap Many Times

[ABC253G] Swap Many Times

Score : 600600 points

Problem Statement

For an integer NN greater than or equal to 22, there are N(N1)2\frac{N(N - 1)}{2} pairs of integers (x,y)(x, y) such that 1x<yN1 \leq x \lt y \leq N.

Consider the sequence of these pairs sorted in the increasing lexicographical order. Let (x1,y1),,(xRL+1,yRL+1)(x_1, y_1), \dots, (x_{R - L + 1}, y_{R - L + 1}) be its LL-th, (L+1)(L+1)-th, \ldots, and RR-th elements, respectively. On a sequence A=(1,,N)A = (1, \dots, N), We will perform the following operation for i=1,,RL+1i = 1, \dots, R-L+1 in this order:

  • Swap AxiA_{x_i} and AyiA_{y_i}.

Find the final AA after all the operations.

We say that (a,b)(a, b) is smaller than (c,d)(c, d) in the lexicographical order if and only if one of the following holds:

  • a<ca \lt c
  • a=ca = c and b<db \lt d

Constraints

  • 2N2×1052 \leq N \leq 2 \times 10^5
  • 1LRN(N1)21 \leq L \leq R \leq \frac{N(N-1)}{2}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN LL RR

Output

Print the terms of AA after all the operations in one line, separated by spaces.

5 3 6
5 1 2 3 4

Consider the sequence of pairs of integers such that 1x<yN1 \leq x \lt y \leq N sorted in the increasing lexicographical order. Its 33-rd, 44-th, 55-th, and 66-th elements are (1,4),(1,5),(2,3),(2,4)(1, 4), (1, 5), (2, 3), (2, 4), respectively.

Corresponding to these pairs, AA transitions as follows.

$(1, 2, 3, 4, 5) \rightarrow (4, 2, 3, 1, 5) \rightarrow (5, 2, 3, 1, 4) \rightarrow (5, 3, 2, 1, 4) \rightarrow (5, 1, 2, 3, 4)$

10 12 36
1 10 9 8 7 4 3 2 5 6