Giải tennis

Mirko là một người hâm mộ tennis cuồng nhiệt. Sắp tới sẽ diễn ra một giải đấu gồm \(n\) vận động viên.
Mirko đã nghiên cứu các tay vợt trong nhiều năm và thu thập được thông tin về thứ hạng của họ trên ba mặt sân: sân cỏ, sân đất nện và sân cứng.

Cụ thể, với mỗi mặt sân, Mirko có một dãy hoán vị các tay vợt từ mạnh nhất đến yếu nhất (vị trí \(1\) là mạnh nhất).

Trong giải đấu này, mỗi cặp người chơi sẽ đấu đúng một trận. Trận đấu không thể hòa và người mạnh hơn trên mặt sân được chọn sẽ giành chiến thắng.

Ban tổ chức chọn mặt sân cho từng trận đấu theo quy tắc sau:

• Với hai người chơi \(A\) và \(B\), xét thứ hạng của họ trên từng mặt sân trong ba bảng xếp hạng.
• Mặt sân được chọn là mặt sân mà người thắng cuộc sẽ có thứ hạng tốt nhất (nghĩa là thứ hạng nhỏ nhất) trong bảng xếp hạng của mặt sân đó.
• Nếu có nhiều mặt sân cho kết quả như nhau, chọn mặt sân mà người thua cuộc có thứ hạng tốt nhất.
• Nếu vẫn còn hòa, chọn mặt sân có chỉ số nhỏ nhất (1 là cỏ, 2 là đất nện, 3 là cứng).

Yêu cầu: Hãy xác định số trận diễn ra trên từng mặt sân và số trận thắng của mỗi tay vợt.

\InputFile

Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 100\,000\)).

Ba dòng tiếp theo, mỗi dòng chứa một hoán vị của các số từ \(1\) tới \(n\), biểu diễn thứ hạng trên sân cỏ, sân đất nện và sân cứng.
Vị trí thứ \(i\) trong dãy là tay vợt mạnh thứ \(i\) trên mặt sân đó.

\OutputFile

In ra ba số nguyên: số trận diễn ra trên sân cỏ, sân đất nện và sân cứng.

Dòng thứ hai in ra \(n\) số nguyên: số trận thắng của từng tay vợt từ \(1\) đến \(n\).

\Scoring

• Subtask 1 (35 điểm): \(1 \le n \le 300\).
• Subtask 2 (15 điểm): \(1 \le n \le 3000\).
• Subtask 3 (50 điểm): \(1 \le n \le 100000\).

Example

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