This page is still under construction.

Parts of this page are still being built. What you see may change.

Broken Cipher Generator

Time limit8sMemory limit512 MB

Summary
Decode a broken cipher string with +/- shifts, bracket reversals, and up to three unreadable '?' letters, choosing letters that make the decoded result lexicographically smallest.
Level

Medium7 of 10

Topics
Brute force, String, Implementation, Recursion
Solved
No attempts yet

Problem

JAG (Japanese Alumni Group) is a mysterious organization made up of many programmers. To enter the building that houses its headquarters, one must each time solve a ciphertext produced by a certain machine. This ciphertext consists of the symbols '+', '-', '[', ']' and uppercase letters, and is represented by <Cipher>, defined by the following BNF.

<Cipher> ::= <String> | <Cipher><String>
<String> ::= <Letter> | '['<Cipher>']'
<Letter> ::= '+'<Letter> | '-'<Letter> |
             'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' | 'J' | 'K' | 'L' | 'M' |
             'N' | 'O' | 'P' | 'Q' | 'R' | 'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z'

Each symbol has the following meaning.

  • +(letter): represents the letter after that letter in the alphabet. The letter after 'Z' is 'A'.
  • -(letter): represents the letter before that letter in the alphabet. The letter before 'A' is 'Z'.
  • [(string)]: represents the string obtained by reversing that string left to right.

However, the machine that produces this ciphertext is currently broken, so some of the letters in the ciphertext may be damaged and unreadable. An unreadable letter is written temporarily as '?'. Investigation revealed that the damaged letters are filled in so that the decrypted string is the lexicographically smallest among all strings that can result from decryption. Your job is to decrypt this ciphertext correctly.

Input

The input consists of multiple datasets. Each dataset is a single line containing a string in which some uppercase letters of a ciphertext defined by the above BNF have been replaced by '?'. You may assume the length of each string is at most 8080. You may also assume that the number of '?' in each dataset is between 00 and 33 inclusive.

The end of the input is indicated by a line containing only the single character '.'.

Output

For each dataset, output the decrypted string obtained when the ciphertext is decrypted so that the decrypted string is lexicographically smallest.

Examples1

  1. Example 1

    Input
    A+A++A
Z-Z--Z+-Z
[ESREVER]
J---?---J
++++++++A+++Z-----------A+++Z
[[++-+--?[--++-?++-+++L]][-+-----+-O]]++++---+L
.
    Expected output
    ABC
ZYXZ
REVERSE
JAG
ICPC
JAPAN