Tenis

Ο Mirko είναι μεγάλος λάτρης του τένις. Σύντομα θα πραγματοποιηθεί ένα σημαντικό τουρνουά με ~n~ παίκτες. Ο Mirko έχει περάσει χρόνια μαθάινοντας για παίκτες του τένις και έχει συλλέξει διάφορα στατιστικά στοιχεία για τους ανταγωνιστές. Έχει κατατάξει την ικανότητά τους σε τρία διαφορετικά είδη γηπέδου: γήπεδο με χορτάρι, με χώμα και τραχύ γήπεδο. Πιο συγκεκριμένα, για κάθε γήπεδο έχει καθορίσει τη σειρά (λίστα κατάταξης) των παικτών, με τον πρώτο παίκτη να είναι ο πιο δυνατός και τον τελευταίο να είναι ο πιο αδύναμος.

Σε αυτό το τουρνουά, κάθε παίκτης θα παίξει εναντίον κάθε άλλου παίκτη ακριβώς μία φορά, επομένως θα υπάρχουν ~\frac{n(n-1)}{2}~ αγώνες συνολικά. Ένας αγώνας τένις δεν μπορεί να τελειώσει ισόπαλος και ο παίκτης που είναι πιο δυνατός στο γήπεδο στο οποίο παίζεται ο αγώνας θα κερδίσει. Οι διοργανωτές το γνωρίζουν, γι' αυτό αποφάσισαν ότι κάθε αγώνας πρέπει να παίζεται στο γήπεδο για τον οποίο ο νικητής θα είναι ο ισχυρότερος, δηλαδή θα έχει την καλύτερη θέση στην αντίστοιχη λίστα κατάταξης. Εάν ορισμένα γήπεδα είναι ίσα με αυτή την έννοια (δηλαδή, η θέση του νικητή στον αγώνα μεταξύ των παικτών ~A~ και ~B~ θα ήταν η ίδια, π.χ. ο παίκτης ~A~ θα κέρδιζε στο γήπεδο 1 και ο παίκτης ~B~ στο γήπεδο 2, τότε και οι δύο κατατάσσονται τρίτοι στους αντίστοιχες λίστες κατάταξης του γηπέδου), θα επιλέξουν το γήπεδο για το οποίο ο ηττημένος θα είχε την καλύτερη θέση. Εάν τα γήπεδα εξακολουθούν να είναι ίσα, επιλέγεται αυτό με τον μικρότερο δείκτη.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~n~, τον αριθμό των παικτών. Οι παίκτες επισημαίνονται με ακέραιους αριθμούς από το 1 έως το ~n~.

Η ~i~-οστή από τις ακόλουθες τρεις γραμμές περιέχει μια ανταλλαγή ακεραίων από το 1 έως το ~n~, τη λίστα κατάταξης των παικτών για την ~i~-οστή επιφάνεια, ξεκινώντας από τον ισχυρότερο παίκτη.

Έξοδος

Στην πρώτη γραμμή, εκτυπώστε τον αριθμό των αγώνων που παίχτηκαν στην πρώτη, στην δεύτερη και στην τρίτη επιφάνεια.

Στη δεύτερη γραμμή, εκτυπώστε τον αριθμό των αγώνων που κέρδισε κάθε παίκτης από 1 έως ~n~.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	35	~1 \le n \le 300~
2	15	~1 \le n \le 3000~
3	60	~1 \le n \le 100\,000~

Εάν η λύση σας εκτυπώνει σωστά τουλάχιστον μία από τις δύο γραμμές σε κάθε δοκιμαστική περίπτωση ενός υποπροβλήματος, αλλά δεν εκτυπώνει σωστά και τις δύο γραμμές σε τουλάχιστον μία δοκιμαστική περίπτωση, θα λάβετε τους μισούς πόντους για αυτό το υποπρόβλημα.

Παραδείγματα

input

3
3 2 1
1 3 2
3 2 1

output

1 2 0
2 0 1

Επεξήγηση του 1ου παραδείγματος:

Ο αγώνας μεταξύ των παικτών 1 και 2 παίζεται στο γήπεδο 2, επειδή ο νικητής (παίκτης 1) έχει την καλύτερη (πρώτη) θέση. Για τον αγώνα μεταξύ των παικτών 1 και 3, ο νικητής καταλαμβάνει την ίδια θέση και στα τρία γήπεδα, αλλά ο ηττημένος έχει καλύτερη θέση στο γήπεδο 2. Για τον αγώνα μεταξύ των παικτών 2 και 3, τα γήπεδα 1 και 3 είναι ίσα, άρα επιλέγεται αυτό με τον μικρότερο δείκτη (γήπεδο 1).

input

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

output

3 2 1
1 0 2 3