Cryptogram Cracking Club

Η Cyrene, η αρχηγός της Λέσχης Αποκρυπτογράφησης Κρυπτογραφημάτων (CCC), συνάντησε ένα ανησυχητικά μεγάλο κρυπτογράφημα. Ευτυχώς, αυτό το κρυπτογράφημα αποτελείται από πεζούς χαρακτήρες (a-z). Ακόμη καλύτερα, το κρυπτογράφημα αποτελείται από ένα μοτίβο που επαναλαμβάνεται άπειρες φορές.

Η Cyrene επιθυμεί να εντοπίσει τον ~c~-οστό χαρακτήρα του κρυπτογραφήματος. Για να κάνει τη δουλειά σας ευκολότερη, τα μέλη της CCC έχουν εξαγάγει το επαναλαμβανόμενο μοτίβο και το έχουν συμπιέσει χρησιμοποιώντας τον αλγόριθμο Run-Length Encoding (RLE), ο οποίος αντικαθιστά διαδοχικούς επαναλαμβανόμενους χαρακτήρες με μία μοναδική εμφάνιση του χαρακτήρα, ακολουθούμενη από το πλήθος των φορών που επαναλήφθηκε.

Για παράδειγμα, για το μοτίβο aaaabccdddd, ο αλγόριθμος RLE παράγει a4b1c2d4.

Σας δίνεται η έξοδος του αλγορίθμου RLE για ένα συγκεκριμένο μοτίβο. Μπορείτε να προσδιορίσετε τον ~c~-οστό χαρακτήρα του μεγάλου κρυπτογραφήματος που σχηματίζεται επαναλαμβάνοντας αυτό το μοτίβο άπειρες φορές;

Είσοδος

Η πρώτη γραμμή της εισόδου αποτελείται από μια συμβολοσειρά ~S~, που αναπαριστά ένα μοτίβο παραγόμενο από τον αλγόριθμο RLE. Το μήκος της ~S~ είναι τουλάχιστον ~2~ και το πολύ ~2 \cdot 10^5~. Επιπλέον, όλοι οι αριθμοί που εμφανίζονται στη ~S~ είναι μεταξύ ~1~ και ~10^{12}~.

Η επόμενη γραμμή της εισόδου περιέχει έναν μοναδικό ακέραιο ~c~, που αναπαριστά τον δείκτη του χαρακτήρα που θέλετε να εντοπίσετε, ξεκινώντας από τον δείκτη ~0~.

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι διαθέσιμες 15 μονάδες:

Βαθμοί	Όρια του ~c~	Επιπλέον Περιορισμοί
~6~	~0 \le c \le 2000~	Όλοι οι αριθμοί που εμφανίζονται στη ~S~ είναι μεταξύ ~1~ και ~9~ (συμπεριλαμβανομένων) και το μήκος του επαναλαμβανόμενου μοτίβου είναι το πολύ ~2000~ χαρακτήρες.
~3~	~0 \le c \le 10^6~	Το μήκος του επαναλαμβανόμενου μοτίβου είναι το πολύ ~10^6~ χαρακτήρες.
~3~	~0 \le c \le 10^{12}~	Το μήκος του επαναλαμβανόμενου μοτίβου είναι το πολύ ~10^6~ χαρακτήρες.
~3~	~0 \le c \le 10^{12}~	Κανένας επιπλέον περιορισμός.

Έξοδος

Εκτυπώστε τον ~c~-οστό χαρακτήρα του μεγάλου κρυπτογραφήματος.

input

r2d2
8

output

r

Επεξήγηση του πρώτου παραδείγματος: Η έξοδος του αλγορίθμου RLE r2d2 αντιστοιχεί στο μοτίβο rrdd, το οποίο δημιουργεί το άπειρα επαναλαμβανόμενο κρυπτογράφημα rrddrrddrrddrrdd..., όπου ο χαρακτήρας με ~c = 8~ είναι ο r. Σε αυτό το παράδειγμα, ο ~c = 8~-οστός χαρακτήρας είναι επισημασμένος με ένα πλαίσιο.

input

a4b1c2d10
100

output

d

Επεξήγηση του δεύτερου παραδείγματος: Η έξοδος του αλγορίθμου RLE a4b1c2d10 αντιστοιχεί στο μοτίβο aaaabccdddddddddd. Όταν επαναλαμβάνεται άπειρες φορές, ο ~c = 100~-οστός χαρακτήρας είναι d.