B. Balanced Permutations
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a permutation $$$p$$$ of size $$$n$$$, let a (contiguous) subarray of $$$p$$$ be 'unstable' if the maximum value contained within the subarray is its first or last element. A permutation is considered 'balanced' if it has the minimum number of 'unstable' subarrays over all permutations of size n.

Given integers $$$n, l,$$$ and $$$k$$$, report the $$$l$$$-th lexicographically-minimum 'balanced' permutation and the $$$k$$$-th lexicographically-maximum 'balanced' permutation of size $$$n$$$. If no such permutation exists output $$$-1$$$ instead.

Input

The only line of input contains three integers $$$n, l,$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq l,k \leq 10^{18}$$$) — the length of the desired permutation and the indices of which lex-min and lex-max permutation should be provided.

Output

Output two lines. The first line should contain the $$$l$$$-th lexicographically-minimum 'balanced' permutation of size $$$n$$$ — denoted $$$p$$$.

The second line should contain the $$$k$$$-th lexicographically-maximum 'balanced' permutation of size $$$n$$$ — denoted $$$q$$$.

$$$p$$$ and $$$q$$$ should satisfy $$$1 \leq p_i, q_i \leq n$$$ for all $$$1 \leq i \leq n$$$.

If $$$p$$$ or $$$q$$$ does not exist (ie. there do not exist $$$l$$$ or $$$k$$$ 'balanced' permutations of size $$$n$$$) then report an answer of $$$-1$$$ instead.

Examples
Input
3 1 2
Output
1 3 2
1 3 2
Input
4 9 13
Output
3 1 4 2
-1