Logaritam

Ο Hrvoje έμαθε πρόσφατα για την λογαριθμική συνάρτηση. Του αρέσει πολύ η ιδιότητα ~log(xy)~ = ~log(x) + log(y)~, για κάθε ζεύγος θετικών πραγματικών αριθμών ~x~ και ~y~.

Στην πραγματικότητα δεν ενδιαφέρεται για τη συνάρτηση αυτή καθαυτή, αλλά για τις λογαριθμικές ακολουθίες. Μια λογαριθμική ακολουθία μήκους ~n~ είναι μια ακολουθία πραγματικών αριθμών (~a_1, a_2, ..., a_n~) για την οποία η εξίσωση ~a_{xy}~ = ~a_x~ + ~a_y~ ισχύει για κάθε ζεύγος θετικών ακέραιων ~x~ και ~y~ τέτοιο ώστε ~xy~ ~\le~ ~n~. Ένα παράδειγμα μιας λογαριθμικής ακολουθίας μήκους ~6~ είναι η ~0~, ~1~, π, ~2~, ~0.7~, ~1~ +π.

Για την εργασία του, ο Hrvoje έπρεπε να γράψει ~q~ λογαριθμικές ακολουθίες μήκους ~n~, ωστόσο, μετά από μια πολύ μεγάλη νύχτα προσπάθειας, όταν ξύπνησε συνειδητοποίησε ότι ο Matej είχε αλλάξει ακριβώς ένα στοιχείο από κάθε ακολουθία. Ο Hrvoje δεν έχει πολύ χρόνο για να διορθώσει την εργασία του, οπότε τον ενδιαφέρει ο μικρότερος αριθμός στοιχείων κάθε ακολουθίας που πρέπει να αλλάξει ώστε η ακολουθία να γίνει λογαριθμική ξανά. Δυστυχώς, ο Matej είχε γράψει το στοιχείο του με στιλό , οπότε ο Hrvoje δεν μπορεί να αλλάξει εκείνο το στοιχείο της ακολουθίας.

Ο Hrvoje έχει ξεχάσει ποιές ακολουθίες έγραψε για την εργασία του οπότε το μόνο πράγμα που ξέρει είναι ο αριθμός των ακολουθιών ~q~, το μήκος κάθε ακολουθίας ~n~ και η θέσει ~x_i~ του στοιχείου που είχε αλλάξει ο Matej στην ~i~-οστη ακολουθία.

Σημείωση: Μπορεί να αποδειχθεί ότι για οποιαδήποτε αρχική λογαριθμική ακολουθία ο ελάχιστος αριθμός αλλαγών είναι ο ίδιος

Είσοδος

Στην πρώτη γραμή υπάρχουν δύο θετικοί ακέραιοι ~n~ και ~q~ (~1~ ~\le~ ~n~ ~\le~ ~10^8~, ~1~ ~\le~ ~q~ ~\le~ ~10^4~), το μήκος κάθε ακολουθίας και τον αριθμό των ακολουθιών.

Στην ~i~-οστη από τις επόμενες ~q~ γραμμές υπάρχει ένας θετικός ακέραιος ~x_i~ (~1~ ~\le~ ~x_i~ ~\le~ ~n~), τον δείκτη του στοιχείου που είχε αλλάξει ο Matej στην ~i~-οστη ακολουθία.

Έξοδος

Στην ~i~-οστη γραμμή εκτυπώστε ~-1~ αν ο Hrvoje δεν μπορεί να αλλάξει τα υπόλοιπα στοιχεία της ~i~-οστης ακολουθίας ώστε η ακολουθία να γίνει λογαριθμική ξανά, αλλιώς εκτυπώστε τον ελάχιστο αριθμό αλλαγών που χρειάζονται για να γίνει η ακολουθία λογαριθμική και πάλι.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	19	~n~ ~\le~ ~20~, ~q~ ~\le~ ~20~
2	26	~q~ ~\le~ ~8~
3	29	~n~ ~\le~ ~10^4~
4	36	Κανένας επιπλέον περιορισμός.

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

input

6 6
1
2
3
4
5
6

output

-1
2
1
2
0
1

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

Εάν η αρχική ακολουθία ήταν ~0~, ~1~, π, ~2~, ~0.7~, ~1~ + π και ο Matej αλλάξει το τέταρτο στοιχείο σε ~8~, ο Hrvoje μπορεί να αλλάξει το δεύτερο στοιχείο σε ~4~ και το έκτο σε ~4~ + π και μετά τις αλλαγές αυτές η ακολουθία ~0~, ~4~, π, ~8~, ~0.7~, ~4~ + π θα είναι λογαριθμική ξανά.

input

20 5
7
8
2
19
12

output

1
9
9
0
5

input

10000 4
1234
2345
3456
7890

output

15
148
3332
37