Monkey Cards

View as PDF

Submit solution

Points: 12
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Sanjay, the monkey, is playing a game with some cards! Sanjay has a deck of N cards a, and Tony, his opponent, has a deck of N cards b. Each card has a value.

The game consists of N rounds. In each round, both players flip over the top card of their deck. For the first K rounds, Sanjay gains a point if he has a card with strictly lower value than Tony. For the remaining N - K rounds, he gains a point if he has a card with strictly higher value than Tony.

Sanjay is setting up the decks before Tony arrives and can shuffle them into any order he chooses, but he cannot swap cards between decks. What order should he put the cards in so he achieves the most points?

Constraints

1 \le N \le 5 \times 10^5

0 \le K \le N

1 \le a_i, b_i \le 10^9

Input Specification

The first line of input will contain N and K separated by a single space.

The next line of input will contain N integers each separated by a space, denoting the values in the deck of cards a.

The final line of input will contain N integers each separated by a space, denoting the values in the deck of cards b.

Output Specification

The first line of output should contain the highest possible score if Sanjay arranges the decks optimally.

The second line of output should contain the optimal arrangement of deck a, with all N integers separated by a single space.

The final line of output should contain the optimal arrangement of deck b, with all N integers separated by a single space.

If there are multiple valid arrangements, output any of them.

Note: The checker is strict; do not output any extra whitespace.

Sample Input

5 4
4 4 4 4 4
5 2 1 3 1

Sample Output

2
4 4 4 4 4
3 5 2 1 1

Explanation

Sanjay scores a point on the second and fifth round.


Comments

There are no comments at the moment.