Circle of Life

Ίσως έχετε ακούσει για το παιχνίδι της ζωής (the Game of Life) του Conway, το οποίο είναι ένα απλό σύνολο κανόνων που αφορούν κελιά σε ένα πλέγμα, που μπορούν να παράξουν απίστευτα πολύπλοκες διαμορφώσεις. Σε αυτό το πρόβλημα θα ασχοληθούμε με μια απλοποιημένη εκδοχή του παιχνιδιού.

Υπάρχει μια μονοδιάστατη κυκλική λωρίδα από ~N~ κελιά. Τα κελιά είναι αριθμημένα από το ~1~ έως το ~N~ με τη σειρά που θα περιμένατε: δηλαδή, το κελί ~1~ και το κελί ~2~ είναι γειτονικά, το κελί ~2~ και το κελί ~3~ είναι γειτονικά, κ.ο.κ., μέχρι το κελί ~N - 1~, το οποίο είναι γειτονικό με το κελί ~N~. Δεδομένου ότι η λωρίδα είναι κυκλική, το κελί ~1~ είναι επίσης διπλανό με το κελί ~N~.

Κάθε κελί είναι είτε ζωντανό (παριστάνεται με "~1~") είτε νεκρό (παριστάνεται με "~0~"). Τα κελιά αλλάζουν κατά τη διάρκεια ενός αριθμού γενεών. Εάν ακριβώς ένας από τους γείτονες ενός κελιού είναι ζωντανός στην τρέχουσα γενιά, τότε το κύτταρο αυτό θα είναι ζωντανό στην επόμενη γενιά. Διαφορετικά, το κύτταρο θα είναι νεκρό στην επόμενη γενιά.

Δεδομένης της αρχικής διαμόρφωσης της λωρίδας, βρείτε την διαμόρφωσή της μετά από ~T~ γενιές.

Είσοδος

Η πρώτη γραμμή θα περιέχει δύο ακέραιους αριθμούς, τους ~N~ και ~T\;(3 \le N \le 100\;000,\;1 \le T \le 10^{15})~, χωρισμένους με ένα κενό διάστημα. Η δεύτερη γραμμή θα περιέχει μια συμβολοσειρά αποτελούμενη από ακριβώς ~N~ χαρακτήρες, που θα αντιπροσωπεύουν την αρχική διαμόρφωση των ~N~ κελιών. Κάθε χαρακτήρας στη συμβολοσειρά θα είναι είτε "~0~" είτε "~1~". Η αρχική κατάσταση ενός κελιού ~i~ θα δίνεται από τον ~i~-οστό χαρακτήρα της συμβολοσειράς. Ο χαρακτήρας "~1~" αντιπροσωπεύει ένα ζωντανό κύτταρο και ο χαρακτήρας "~0~" αντιπροσωπεύει ένα νεκρό κύτταρο.

Για ~1~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 15~ και ~T \le 15~.

Για επιπλέον ~6~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 15~.

Για επιπλέον ~4~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 4000~ και ~T \le 10\;000\;000~.

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

• στη C/C++, θα πρέπει να χρησιμοποιηθεί ο τύπος ~long\;long~,
• στη Java, θα πρέπει να χρησιμοποιηθεί ο τύπος ~long~,
• στην Pascal, θα πρέπει να χρησιμοποιηθεί ο τύπος ~int64~.

Έξοδος

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

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

input

7 1
0000001

output

1000010

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

Το κελί ~1~ και το κελί ~N - 1~ είναι γειτονικά με το κελί ~N~ και συνεπώς είναι ζωντανά μετά από μία γενιά.

input

5 3
01011

output

10100

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

Μετά από μία γενιά, η διαμόρφωση γίνεται ~00011~. Μετά από δύο γενιές, η διαμόρφωση γίνεται ~10111~.