You are given an integer array \(A\) of length \(2 \cdot N\) and integer \(K\). Your should divide this array onto two arrays \(B\) and \(C\) with such rules:

1. The sizes of arrays \(B\) and \(C\) are equal to \(N\).
2. Each element of array \(A\) belongs to exactly one of the arrays \(B\) or \(C\).
3. Arrays \(B\) and \(C\) store indices of selected elements.
4. You must maintain the relative order of the elements (arrays \(B\) and \(C\) must be sorted by ascending).
5. You can't take \(K\) consecutive indices in either of two arrays. (for example if \(K\) is equal to \(3\), then you can't take indices \([5, 6, 7]\) into arrays \(B\) or \(C\)).

Your task is to maximize the following value: \(\sum\limits_{i=1}^N f(A_{B_i}, A_{C_i})\), where \(f(x, y)\) is equal to \(1\) if \(x < y\) and \(0\) otherwise.

Input format:

First line contains two space-separated integers \(N\) \((1 \leq N \leq 5 \cdot 10^4)\) and \(K\) \((2 \leq K \leq min(2 \cdot N, 100))\).

Next line contains \(2 \cdot N\) space-separated integers denoting the array \(A\) \((1 \leq A_i \leq 10^9)\).

Output format:

In a first line output \(N\) space-separated integers denoting array \(B\).

In a second line output \(N\) space-separated integers denoting array \(C\).

Verdict and scoring:

Your score is equal to the sum of the values of all test cases.

The value of each test is calculated using this formula: \(\sum\limits_{i=1}^N f(A_{B_i}, A_{C_i})\), where \(f(x, y)\) is equal to \(1\) if \(x < y\) and \(0\) otherwise.

If at least one of the rules will be violated, then your value for this test will be \(0\).

Test generation plan:

Each test has own upper bound \(Z\) (\(1 \leq Z \leq 10^9\)), denoting that every \(A_i\) in this test is not exceeding \(Z\).

In each test \(N\) and \(K\) are randomly generated (considering constraints), \(Z\) is not randomly generated.

In 38% tests: all elements of array \(A\) are randomly generated (considering constraints and limit \(Z\)).

In all other tests: while the current amount of written elements is not equal to \(2 \cdot N\) do:

• take two randomly generated positive integers \(X\) (considering constraints and limit \(Z\)) and \(Y\)
• \(Y\) times write number \(X\) (guaranteed that the current amount of written elements plus \(Y\) is less than or equal to \(2 \cdot N\))