An archive stores an ancient inscription in a compacted form: the scroll's text is written as a sequence of blocks, where each block is a single lowercase letter immediately followed by a positive integer repeat count with no leading zeros (for example, a2b3c1 decodes to aabbbc). A reader device processes the compacted string one character of the decoded text at a time, supporting two operations, given as a sequence of queries:
NEXT: return the next character of the decoded text and advance the reader's position by one, or return a special end marker if the decoded text has already been fully consumed.HASNEXT: report whether the decoded text still has at least one character left to read, without advancing the reader.Repeat counts can be enormous (up to 1,000,000,000), so the reader must never build the full decoded string in memory — it must answer each query using only the compact block representation and its current position within it.
Given the compressed scroll and a sequence of queries, process them in order and report the result of each.
Line 1: the compressed scroll string S.
Line 2: an integer q, the number of queries.
Each of the next q lines: either the word NEXT or the word HASNEXT.
q lines, one per query, in order:
HASNEXT, print true or false.NEXT, print the single decoded character returned, or print END if the decoded text was already exhausted.S consists of one or more blocks; each block is a lowercase English letter followed by a positive integer with no leading zeros.S (as written, letters plus digits) <= 2000Example 1
Input
a2b3c1 8 HASNEXT NEXT NEXT NEXT NEXT NEXT NEXT HASNEXT
Expected
true a a b b b c false
Explanation
The scroll a2b3c1 decodes to 'aabbbc' (6 characters). HASNEXT first reports true since characters remain. The six NEXT calls then return 'a','a','b','b','b','c' in order, consuming the whole decoded text. The final HASNEXT reports false since nothing is left.
Example 2
Input
x1 3 NEXT NEXT HASNEXT
Expected
x END false
Explanation
The scroll x1 decodes to the single character 'x'. The first NEXT returns 'x', consuming the only character. The second NEXT finds the text already exhausted and returns 'END'. The final HASNEXT reports false.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →