Under construction

Still being built. Things may change

I am Sherlocked

Time limit1sMemory limit2048 MB

Summary
Given a phonebook of digit strings and a list of cursor commands, print the digits written to the output, or MISS ME! if a command is invalid.
Level

Medium4 of 10

Topics
Simulation, String, Implementation
Solved
No attempts yet

Problem

Detectives of Scotland Yard, the headquarters of the Metropolitan Police, informed Sherlock Holmes about a cyber attack on the Central Bank by James Moriarty. They also found a secret code that can stop the attack. According to their top agent, Moriarty hid the code in the phonebook of one of his clients. Sherlock has access to this client.

Each correct phone number has 11 digits and starts with a leading zero. The client may separate the digits of each phone number with hyphens (-) or spaces. Some phone numbers in the phonebook may be missing the leading zero. For example, 09163264128 might be written as 916 32 64 128, or even as - 0916-16-32--64 - 128-.

Sherlock arranged a friendly conversation with the client at a cafe. Meanwhile, Dr. John Watson, Sherlock's colleague, took the phonebook without the client noticing. Sherlock told Dr. Watson to clean the phonebook into a new sequence CC of digit characters on his computer. CC is zero-indexed. Dr. Watson types the phone numbers one after another, in the order they appear, with all non-digit characters removed. He adds the leading zero where it is needed.

Dr. Watson has prepared CC and placed the cursor at the first character. The cursor can be placed before any character of CC. He waits for Sherlock's instructions to produce the output sequence SS. Sherlock sends one of the following instructions.

  • go ii: Moves the cursor to the beginning of the iith cleaned phone number in CC. For example, go 0 moves the cursor to the first phone number.
  • forward ii: Moves the cursor forward by ii digits.
  • backward ii: Moves the cursor backward by ii digits.
  • next ii: Writes the next ii digits starting at the cursor into SS. If the cursor is before position cc, the digits at c,c+1,…,c+i−1c, c + 1, \dots, c + i - 1 are written. The cursor does not move.
  • pick ii jj: If i<ji < j, writes the digits at positions i,i+1,…,ji, i + 1, \dots, j of the current phone number into SS. Otherwise, writes the digits at positions i,i−1,…,ji, i - 1, \dots, j. The current phone number is the one that the digit after the cursor belongs to. The cursor does not move. Note that 0≤i,j≤100 \le i, j \le 10, and pick 0 0 writes the first digit.

Sherlock may also send the following instruction to correct a mistake.

  • delete ii: Deletes the last ii digits from the end of SS.

Input

The input consists of the phonebook's content and Sherlock's instructions. The phonebook contains nn phone numbers (1≤n≤1,0001 \le n \le 1{,}000), separated by commas or newlines. Each phone number is a string of 10 or 11 digits (0-9), possibly with hyphens and/or spaces. The phonebook has at most 10610^6 characters. The list of phone numbers ends with a line containing only the character #.

Each remaining line contains one of Sherlock's instructions. He sends at most 10,000 instructions. All arguments are non-negative integers no greater than 20,000. Every instruction is one of the six listed above.

Output

Print the extracted secret code, which is a string of digits. The code may be empty. If the code has more than 10,000 digits, print only the first 10,000 digits.

Sherlock may lose focus and send a malformed instruction. This happens when go refers to a phone number that does not exist, or when forward, backward, next, pick, or delete has an argument that refers to a digit or phone number that does not exist in CC. In such cases, Moriarty has succeeded, and you must print MISS ME! in capital letters.

Examples2

  1. Example 1

    Input
    0912 358 8908
    0872-3344567,0989112-2345
    9899988782
    #
    go 0
    pick 0 3
    next 4
    forward 12
    next 2
    backward 2
    pick 0 1
    go 3
    pick 0 1
    delete 1
    
    Expected output
    0912091287090
    
  2. Example 2

    Input
    09242424024
    00188990376
    #
    go 2
    next 4
    delete 1
    
    Expected output
    MISS ME!