Vođe

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

Το παιχνίδι παίζεται έτσι ώστε συνολικά \(Ν\) ζώα (που μπορεί να είναι κατσίκες ή πρόβατα) σχηματίζουν έναν κύκλο (η ακριβής σειρά των κατσικιών και των προβάτων είναι μια συμφωνία μεταξύ των αρχηγών τους). Μετά το ζώο ~i~ ~(1 \le i \le N-1)~, το παιχνίδι συνεχίζεται από το ζώο ~i+1~ και μετά το ζώο \(Ν\), το παιχνίδι συνεχίζεται από το ζώο 1. Το ζώο που ξεκινά το παιχνίδι μπορεί να πει οποιονδήποτε θετικό ακέραιο από το διάστημα ~[1, K]~, αλλά μόνο εάν αυτός ο αριθμός δεν είναι μεγαλύτερος από ~M~. Εάν το ζώο που ξεκίνησε το παιχνίδι είπε τον αριθμό ~j~, τότε το επόμενο ζώο μπορεί να πει έναν αριθμό στο διάστημα ~[j+1, j+K]~, αλλά μόνο εάν αυτός ο αριθμός δεν είναι μεγαλύτερος από Μ. Με άλλα λόγια, κάθε ζώο μπορεί να πει έναν αριθμό που είναι μεγαλύτερος, τουλάχιστον, κατά 1 και, το πολύ, κατά ​Κ από τον αριθμό που είπε το ζώο πριν, αλλά μόνο εάν ο νέος αριθμός δεν είναι μεγαλύτερος από ~M~. Εάν ένα ζώο πρέπει να πει τον αριθμό ~M~, η ομάδα του (κατσίκες ή πρόβατα) χάνει.

Αν και οι κατσίκες και τα πρόβατα παίζουν βέλτιστα, για κάθε ~i~ ~(1 \le i \le N)~, καθορίστε ποιος θα κερδίσει το γήπεδο εάν το παιχνίδι ξεκινήσει από το ~i~-οστό ζώο.

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει ~N~, ~M~ και ~K~ ~(1 \le N, M, K \le 5.000)~,​ τους αριθμούς από την περιγραφή εργασίας.

Έξοδος

Έξοδος ~N~ αριθμών διαχωρισμένων με κενό. Για κάθε ζώο ~i~ \((1 \le i \le N​)\) βγάζετε 0 εάν το πρόβατο θα κερδίσει το χωράφι και 1 εάν οι κατσίκες θα κερδίσουν, εάν το i-οστό ζώο ξεκινά το παιχνίδι.

Βαθμολογία

Σε περιπτώσεις δοκιμής συνολικής αξίας 60% των πόντων, θα ισχύει ~1 \le N, M, K \le 500~.

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

input

2 9 2
0 1

output

0 1

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

Όταν ένα πρόβατο παίζει πρώτο, μπορεί να παίξει ως εξής:
Το πρόβατο ξεκινά με τον αριθμό 2, μετά από τον οποίο το κατσίκι μπορεί να πει 3 ή 4. Και στις δύο περιπτώσεις, το πρόβατο μπορεί να πει 5, μετά το κατσίκι μπορεί να πει είτε 6 είτε 7. Και στις δύο περιπτώσεις, το πρόβατο μπορεί να πει 8, μετά το οποίο ο τράγος δεν έχει άλλη επιλογή από το 9 και έτσι χάνει το παιχνίδι και το χωράφι.

input

6 499 5
1 0 0 1 1 0

output

0 1 1 1 1 0

input

10 100 10
0 0 0 1 1 1 1 0 1 1

output

1 1 1 1 1 1 1 1 1 1