Mirko is a big fan of tennis. Soon an important tournament with players will take place. Mirko has spent years researching tennis players and has collected various statistics about the competitors. He has ranked their ability on three different courts: grass, clay and hard. More precisely, for each court he has determined the order (rank list) of the players, with the first player being the strongest, and the last being the weakest.
In this tournament, every player will play against every other player exactly once, so there will be matches in total. A tennis match cannot end in a draw, and the player who is stronger on the court the match is played on will win. The organisers know that, so they have decided that each match should be played on the court for which the winner will be the strongest, i.e. have the best position in the corresponding rank list. If some courts are equal in that sense (the position of the winner of the match between players and would be the same, e.g. player would win on court , and player on court , and they are both ranked third on the corresponding court rank lists), they will choose the court for which the loser would have the best position. If the courts are still equal, the one with the smallest index is chosen.
Determine the outcome of this tournament: the number of matches played on each court and the number of wins for each player.
Input
The first line contains an integer , the number of players. The players are labeled with integers from to .
The -th of the following three lines contains a permutation of integers from to , the rank list of the players for the -th surface, starting with the strongest player.
Output
In the first line, print the number of matches played on the first, second and third surface.
In the second line, print the number of matches won by each player from to .
Scoring
Subtask | Score | Constraints |
---|---|---|
If your solution prints at least one of the lines correctly on each test case of a subtask, but it doesn't print both lines correctly on at least one test case, you will get half of the points for that subtask.
Sample Input 1
3
3 2 1
1 3 2
3 2 1
Sample Output 1
1 2 0
2 0 1
Explanation for Sample Output 1
The match between players and is played on court , because the winner (player ) has the best (first) position. For the match between players and , the winner has the same position on all three courts, but the loser has a better position on court . For the match between players and , court and are equal, so the one with the smaller index is chosen (court ).
Sample Input 2
4
4 3 2 1
3 1 2 4
1 2 3 4
Sample Output 2
3 2 1
1 0 2 3
Comments