Doll Rock-Paper-Scissors

Alice has a lot of dolls. There are \(4\cdot n\) dolls playing rock-paper-scissors that are divided into two teams: Team A and Team B, each containing \(2\cdot n\) dolls. The game is played in \(2\cdot n\) rounds. In the \(i\text{-th}\) round, the \(i\text{-th}\) doll from Team A faces the \(i\text{-th}\) doll from Team B.

If the doll from Team A wins, Team A earns 1 point; if it loses, Team A loses 1 point; if the round is a tie, no points are awarded.

The choices of dolls are represented by two arrays \(a\) and \(b\). Here, \(a_i\) is the choice of the \(i\text{-th}\) doll in Team A and \(b_i\) is that in Team B. The mapping is: 1 for rock, 2 for scissors, and 3 for paper.

Alice is allowed to change the choice of at most \(n\) dolls in each team (i.e. at most \(n\) modifications in array \(a\) and at most \(n\) modifications in array \(b\)). She wants to modify the arrays in order to maximize the score of Team A and also provide one valid construction for which the maximum score is achieved. If there exist multiple valid answers, any one of them will be accepted.

Winning rules: Rock (1) beats Scissors (2), Scissors (2) beats Paper (3), and Paper (3) beats Rock (1).

Note: In a round, you can change the choice of only one doll (either from Team A or Team B) if that helps to produce a win for Team A. You do not have to force a win in rounds that are already winning.

inputFormat

The first line contains an integer \(n\).

The second line contains \(2\cdot n\) space-separated integers \(a_1, a_2, \dots, a_{2n}\) representing the choices of Team A.

The third line contains \(2\cdot n\) space-separated integers \(b_1, b_2, \dots, b_{2n}\) representing the choices of Team B.

outputFormat

Output three lines:

• The first line contains the maximum possible score of Team A after performing at most \(n\) modifications on each team.
• The second line contains \(2\cdot n\) space-separated integers representing the final configuration of Team A's choices.
• The third line contains \(2\cdot n\) space-separated integers representing the final configuration of Team B's choices.

sample

1
1 2
1 3

2
3 2
1 3