404343: GYM101484 D Joaozao, The Digit Maker

Joaozao is a famous digit maker in the city of Sao Carlos. He owns a shop downtown where he receives orders to create numbers. Nicoleta, his friend and a very recent hire, is trying to learn this fancy art of digit making.

Joaozao is specialized in making numbers in base B. A number in base B is a sequence of digits written in the following way:

Joaozao received an order to build an n-digit number in base B. It is a lot of work for one day, so he decided to ask Nicoleta, who is still learning, to help him.

The process of building the number is the following: First Joaozao creates 2n digits in base B. After that, Joaozao gives pairs of digits to Nicoleta, one after the other. As Nicoleta receives them, he adds these two digits together and takes the remainder of the division by B, creating a new digit z. Finally, Nicoleta attaches z to the beginning of the number they are building, making z its most significant digit. After n steps, they will have an n-digit number written in base B.

Joaozao has already created 2n digits in base B and they will soon start the next step of the process. They are wondering what is the largest number they can build (the larger the number, the more valuable it is). Nicoleta really wants to impress Joaozao, so he asked you to help him with this task.

The first line of the input contains two integers n (1 ≤ n ≤ 10⁵) and B (1 ≤ B ≤ 10⁹), indicating respectively the number of digits of the number Nicoleta will build and its base.

The second line contains 2n integers d_i representing the digits Joaozao has already created. (0 ≤ d_i ≤ B - 1).

Output n space separated integers: the digits of the largest number in base B that Joaozao and Nicoleta can build, from most significant to least significant.

If this number has leading zeros, output them anyway.

3 10
1 2 3 4 5 6

9 9 3 

2 19
1 2 16 17

18 18 

A number x_b = d₁d₂...d_m is larger than y_b = r₁r₂...r_p. If, and only if,