Maximizing Team A’s Score with Limited Operations

Alice has 4·n dolls playing rock-paper-scissors. They are split into two teams: Team A and Team B, each with 2·n dolls. The game is played in 2·n rounds; in the i-th round the i-th doll in Team A plays against the i-th doll in Team B.

The scoring rule is as follows: if the doll from Team A wins the round, Team A gets +1 point; if it loses, Team A loses 1 point; and if it ties, no points are awarded. In this game, the moves are encoded as 1 for rock, 2 for scissors, and 3 for paper. The winning relationships are:

• Rock (1) beats Scissors (2)
• Scissors (2) beats Paper (3)
• Paper (3) beats Rock (1)

Alice already knows the initial choices of both teams: the array a of length 2·n represents the choices for Team A and the array b of length 2·n those for Team B (the i-th element of each array corresponds to the i-th round).

Now, for each team, Alice is allowed to change the moves of exactly n dolls. In other words, she must choose exactly n rounds in which Team A’s move is replaced by a new move of her choice and exactly n rounds in which Team B’s move is replaced. The goal is to construct new moves for each team so that the final score of Team A is maximized. In any round where at least one team changes its move, Alice can set the final moves arbitrarily (subject to the constraint on the number of changes) to guarantee a win for Team A (i.e. final pair yielding +1 point for Team A). Rounds where no change is made will retain their original outcome.

Output the maximum achievable score for Team A, followed by the final move arrays for Team A and Team B. If there are multiple valid constructions achieving the maximum score, output any one of them.

Note on the rules:

If a round is not modified by either team, its score is determined by the initial moves. The outcome function f(x,y) (in terms of Team A’s move x and Team B’s move y) is defined as follows:

• If (x,y) is one of \( (1,2), (2,3), (3,1) \), then \( f(x,y)=+1 \) (Team A wins).
• If \( x=y \), then \( f(x,y)=0 \) (tie).
• Otherwise, \( f(x,y)=-1 \) (Team A loses).

For rounds where at least one move is changed, Alice can choose the new moves to force the round to yield +1. However, exactly n moves in Team A and exactly n moves in Team B must be changed overall. For rounds where only one team’s move is changed, the unmodified move remains and the changed move must be set to the winning counter move. For rounds where both sides are changed, you may choose any winning pair (for example, Team A’s move 1 and Team B’s move 2, since 1 beats 2).

---

Formally, let there be 2·n rounds. For each round i (1 ≤ i ≤ 2·n), you decide whether to change Team A’s move and/or Team B’s move. You must make exactly n changes in each team. If no change is made in a round, the score is \( f(a_i, b_i) \); if at least one move is changed, Alice can force the round result to +1. The overall score is the sum over the rounds. Maximize the final score and output one valid assignment of moves for both teams.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵). The second line contains 2·n space‐separated integers, the array a (each element is 1, 2, or 3). The third line contains 2·n space‐separated integers, the array b (each element is 1, 2, or 3).

It is guaranteed that the input size does not exceed reasonable limits.

outputFormat

On the first line, output the maximum achievable score for Team A.

On the second line, output 2·n integers — the final moves for Team A.

On the third line, output 2·n integers — the final moves for Team B.

If there are multiple solutions, output any one.

sample

1
1
2

1
1
2

</p>