Description

You are the organizer of a tennis tournament with $n$ players, numbered from $1$ to $n$. Before the tournament, you tested their initial rankings on three types of courts (Court A, Court B, Court C). In this tournament, every pair of players plays exactly one match, so there are $\dfrac{n \times (n-1)}{2}$ matches in total.

There are no draws. For a match, the player who has a better initial ranking on the chosen court type wins. Your tournament also has some “behind-the-scenes” arrangements: you want the winner of each match to play on the court type where they are stronger (i.e., where they have a better initial ranking). If multiple court types satisfy this, choose the one where the loser has a better ranking. If there is still more than one, choose the one with the smaller index (A $<$ B $<$ C).

You want to know how many matches are held on each court, and how many matches each player wins.

Input Format

The first line contains an integer $n$, the number of players.
The second line contains $n$ integers, giving the players’ initial rankings on Court A from strongest to weakest.
The third line contains $n$ integers, giving the players’ initial rankings on Court B from strongest to weakest.
The fourth line contains $n$ integers, giving the players’ initial rankings on Court C from strongest to weakest.

Output Format

The first line contains three integers, the numbers of matches held on Court A, Court B, and Court C, respectively.
The second line contains $n$ integers, where the $i$-th integer is the number of matches won by player $i$.

3
3 2 1
1 3 2
3 2 1

1 2 0
2 0 1

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

3 2 1
1 0 2 3

Hint

Sample 1 Explanation

For the match between players 1 and 2, it should be played on Court B, because the winner (player 1) has their best ranking on that court (1st). For the match between players 1 and 3, the winner has the same ranking on all three courts, but the loser has a higher ranking on Court B. For the match between players 2 and 3, the rankings on Court A and Court C are the same, so we choose the court with the smaller index, Court A.

Constraints

This problem uses bundled testdata.

• Subtask 1 (35 pts): $1 \le n \le 300$.
• Subtask 2 (15 pts): $1 \le n \le 3000$.
• Subtask 3 (60 pts): $1 \le n \le 10^5$.

Full score is 110 points.

Notes

Translated from Croatian Open Competition in Informatics 2020 ~ 2021 Round 1 E Tenis 。

Translated by ChatGPT 5