Vrtić

Υπάρχουν ​Ν παιδιά σε ένα νηπιαγωγείο και κάθε παιδί θεωρεί ένα παιδί ως τον καλύτερό του φίλο. Τα παιδιά είναι αρκετά ασυνήθιστα, επομένως ισχύει ότι δύο παιδία δεν γίνεται να θεωρούν το ίδιο παιδί τον καλύτερο τους φίλο , αλλά είναι πιθανό ένα παιδί να είναι ο καλύτερος φίλος του εαυτού τους! Επιπλέον, εάν το παιδί Β είναι ο καλύτερος φίλος του παιδιού Α, ο Α δεν είναι απαραίτητα ο καλύτερος φίλος του παιδιού Β.

Η νηπιαγωγός έχει N σακουλάκια με καραμέλες που θέλει να μοιράσει στα παιδιά έτσι ώστε κάθε παιδί να πάρει ακριβώς μια τσάντα. Ωστόσο, το πρόβλημα είναι ότι οι τσάντες δεν περιέχουν απαραίτητα τις ίδιες ποσότητες καραμέλας, οπότε τα παιδιά μπορεί να δυσαρεστηθούν. Δεδομένου ότι τα παιδιά έχουν πολύ ανεπτυγμένο το αίσθημα της δικαιοσύνης, η δυσαρέσκεια του παιδιού Α ισούται με την απόλυτη διαφορά μεταξύ του αριθμού των γλυκών Α και του καλύτερου φίλου τους που έλαβαν.

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

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει τον ακέραιο αριθμό ​N​ (1 ≤ N ≤ 150). Η δεύτερη γραμμή εισαγωγής περιέχει ​N διακριτούς ακέραιους αριθμούς, όπου ο i-οστός αριθμός είναι η ετικέτα του καλύτερου φίλου του παιδιού i. Τα παιδιά είναι αριθμημένα με αριθμούς από το 1 έως το Ν. Η τρίτη γραμμή εισαγωγής περιέχει ​N ακέραιους αριθμούς, ενώ ο i-οσστός αριθμός είναι ίσος με τον αριθμό των γλυκών στο ι-οστό σακουλάκι. Οι αριθμοί δεν θα ξεπερνούν το ~10^9~.

Έξοδος

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

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 20% των συνολικών πόντων, ο καλύτερος φίλος του i-οστού παιδιού θα είναι το (i+1)-οστό παιδί για όλα τα i < N,​ και ο καλύτερος φίλος του N-οστού παιδιού θα είναι το πρώτο παιδί. Σε πρόσθετες περιπτώσεις δοκιμών αξίας 30% των συνολικών πόντων, θα ισχύει ​N ≤ 20.

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

input

3
2 1 3
3 8 5

output

2
5 3 8

input

5
3 5 4 1 2
24 45 39 19 16

output

8
16 39 24 19 45

input

8
6 3 7 1 4 8 2 5
6 5 2 4 7 4 4 3

output

2
3 4 4 4 6 5 2 7