Podnizovi

Σας δίνεται ένας πίνακας ακεραίων μήκους ~N~ . Έστω ~s_1,\;s_2,\;\ldots,\;s_q~ ο λεξικογραφικά ταξινομημένος πίνακας όλων των μη κενών υποακολουθιών του. Μια υποακολουθία του πίνακα είναι ένας πίνακας που λαμβάνεται αφαιρώντας μηδέν ή περισσότερα στοιχεία από τον αρχικό πίνακα. Παρατηρήστε ότι ορισμένες υποακολουθίες μπορεί να είναι ίσες και ότι ισχύει ~q = 2^N - 1~.

Ένας πίνακας ~A~ είναι λεξικογραφικά μικρότερος από τον πίνακα ~B~ αν ~A_i < B_i~ όπου ~i~ είναι η πρώτη θέση στην οποία διαφέρουν οι πίνακες ή εάν το \(Α\) είναι αυστηρό πρόθεμα του πίνακα \(Β\).

Ας ορίσουμε τον κατακερματισμό ενός πίνακα που αποτελείται από τιμές ~v_1,\;v_2,\;...,\;v_p~ ως:

~h(s) = (v_1 \times B^{p-1} + v_2 \times B_{p-2} + \ldots + v_{p-1} \times B + v_p) mod M~

όπου ~B~, ~M~ είναι ακέραιοι αριθμοί που δίνονται.
Υπολογίστε τα ~h(s_1),\;h(s_2),\;\ldots,\;h(s_K)~ για ένα δεδομένο ~K~.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~N,\;K,\;B,\;M\;(1 \leq N \leq 100\,000,\;1 \leq K \leq 100\,000, 1 \leq B, M \leq 1\,000\,000)~.
Η δεύτερη γραμμή περιέχει ακέραιους αριθμούς ~a_1 ,\;a_2 ,\;a_3,\;\ldots,\;a_N\;(1 \leq a_i \leq 100\,000)~.
Σε όλες τις περιπτώσεις δοκιμής, θα κρατήσει ~K \leq 2^N - 1~.

Έξοδος

Τυπώστε ~K~ γραμμές, με την ~j~-οστή γραμμή να περιέχει ~h(s_j)~.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 60% των συνολικών πόντων, θα έχει επιπλέον ~1 \leq a_1,\;a_2,\;\ldots,\;a_N \leq 30~.

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

input

2 3 1 5
1 2

output

1
3
2

Επεξήγηση του 1ου παραδείγματος: Ισχύει: ~s_1\;=\;l[1],\;s_2\;=\;[1,\;2],\;s_3\;=\;[2].\;h\;(s_1)\;=\;1\;mod\;5\;=\;1,\;h\;(s_2)\;=\;l(1\;+\;2)\;mod\;5\;=\;3,\;h\;(s_3)\;=\;2\;mod\;5\;=\;2~.

input

3 4 2 3
1 3 1

output

1
1
0
2

Επεξήγηση του 2ου παραδείγματος: Ισχύει: ~s_1\;=\;[1],\;s2\;=\;[1],\;s_3\;=\;[1,\;1],s_4\;=\;[1,\;3].\;h\;(s_1)\;=\;1\;mod\;3\;=\;1,\;h\;(s_2)\;=\;1\;mod\;3\;=\;1,\;h\;(s_3)\;=\;(1\;\times\;2\;+\;1)\;mod\;3\;=\;0,\;h\;(s_4)\;=\;(1\;\times\;2\;+\;3\;)\;mod\;3\;=\;2~.

input

5 6 23 1000
1 2 4 2 3

output

1
25
25
577
274
578