~Mirko~ rất thích chơi tennis. Sắp tới, sẽ có một giải đấu tennis gồm ~n~ tuyển thủ tham gia, các tuyển thủ được đánh số từ ~1~ đến ~n~ . Sau nhiều năm để tìm hiểu thì ~Mirko~ đã thống kê được thông tin về khả năng của từng tuyển thủ. Như đã biết tennis được chơi trên ba loại sân khác nhau: sân cỏ, sân đất nện và sân cứng, các sân được đánh số lần lượt là ~1~ , ~2~ và ~3~ . Với mỗi loại sân, Mirko có được danh sách xếp hạng của từng tuyển thủ khi chơi trên loại sân đó. Trong danh sách sách xếp hạng mà ~Mirko~ có, các người chơi được xếp hạng từ mạnh đến yếu, với vị trí đầu tiên là mạnh nhất và cuối cùng là yếu nhất.

Trong giải đấu này, mỗi tuyển thủ sẽ đấu đúng một lần với từng người trong số các tuyển thủ còn lại, do đó sẽ có tổng cộng ~\frac{n(n-1)}{2}~

trận đấu. Một trận đấu tennis sẽ không thể kết thúc với tỷ số hòa và người chiến thắng là người mạnh hơn trên sân đấu hiện tại. Biết được điều này, ban tổ chức quyết định sẽ chọn sân cho mỗi trận đấu theo nguyên tắc sau:

• Trong cả ba sân, sân được chọn là sân mà người thắng sẽ có thứ hạng cao nhất có thể.
• Nếu như có nhiều hơn 1 sân thoả mãn điều kiện trên, vậy trong những sân đó, ta chọn sân mà thứ hạng của người thua chơi trên sân đó là cao nhất có thể.
• Nếu như vẫn có nhiều hơn một sân thoả mãn hai điều kiện trên, vậy trong những sân đó, ta chọn sân có chỉ số nhỏ nhất.

Hãy xác định kết quả giải đấu bao gồm: số trận đấu được chơi trên mỗi loại sân và số lượng trận thắng của từng tuyển thủ.

Input

Dòng đầu tiên chứa một số nguyên ~n~ , số lượng tuyển thủ.

Mỗi dòng thứ ~i~ trong ba dòng tiếp theo gồm ~n~ số là hoán vị của các số tự nhiên từ ~1~ đến ~n~ , là bảng xếp hạng của các tuyển thủ trên sân thứ ~i~ biểu diễn chỉ số của các tuyển thủ theo thứ tự từ mạnh đến yếu.

Output

Dòng đầu tiên, in ba số nguyên, lần lượt là số lượng trận đấu được chơi trên sân thứ nhất, sân thứ hai và sân thứ ba.

Dòng thứ hai, in ra số lượng trận thắng tương ứng với mỗi tuyển thủ từ ~1~ đến ~n~ .

Scoring

Giới hạn và điểm của từng sub task:

• Subtask 1: gồm 3 test ứng với ~1 \le n \le 300~ .
• Subtask 2: gồm 1 test ứng với ~1 \le n \le 3000~ .
• Subtask 3: gồm 6 test ứng với ~1 \le n \le 100000~ .

Với mỗi subtask:

• Nếu kết quả bạn đưa ra đúng hết ở mọi test, bạn được điểm cả subtask đó.
• Nếu có ít nhất ~1~ test bạn sai cả ~2~ dòng, bạn không có điểm cho cả subtask đó.
• Các trường hợp còn lại, bạn được phân nửa số điểm của subtask đó

Sample 1

Input

3
3 2 1
1 3 2
3 2 1

Output

1 2 0
2 0 1

Sample 2

Input

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

Output

3 2 1
1 0 2 3

Giải thích cho ví dụ đầu tiên:

• Trận đấu giữa tuyển thủ ~1~ và ~2~ được chơi trên sân ~2~ , vì người chiến thắng (tuyển thủ ~1~ ) có thứ hạng tốt nhất (hạng nhất) trên sân ~2~ (thứ hạng tốt nhất của người thắng trên từng sân là: ~1~ , ~2~ , ~2~ ).

• Trận đấu giữ tuyển thủ ~1~ và ~3~ , người thắng có cùng thứ hạng trên cả ba sân, nhưng người thua lại có thứ hạng tốt hơn ở sân ~2~ .

• Trận đấu giữa tuyển thủ ~2~ và ~3~ khi chơi trên sân ~1~ hay sân ~3~ đều có kết quả như nhau nên sân có chỉ số nhỏ nhất được chọn (sân ~1~ ).