You are given an integer array A of length 2⋅N and integer K. Your should divide this array onto two arrays B and C with such rules:
Your task is to maximize the following value: N∑i=1f(ABi,ACi), 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≤N≤5⋅104) and K (2≤K≤min(2⋅N,100)).
Next line contains 2⋅N space-separated integers denoting the array A (1≤Ai≤109).
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: N∑i=1f(ABi,ACi), 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≤Z≤109), denoting that every Ai 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⋅N do:
Elements of array A corresponding to indices of array B: [1,2,2,4].
Elements of array A corresponding to indices of array C: [2,4,3,2].
In this case the score is equal to f(1,2)+f(2,4)+f(2,3)+f(4,2)=1+1+1+0=3.