#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<utility>

using namespace std;

pair<string,bool> solve(string str){
	bool check = false;
	vector<char> strv(str.begin(), str.end());
	stack<char> inside;
	int count = 0;
	int left = 0, right = 0;
	for(char ch:strv){
		inside.push(ch);
		if(ch == '['){
			left = count;
			stack<char> empty;
			swap(inside, empty);
		}
		if(ch == ']'){
			check = true;
			right = count;
			inside.pop();
			strv.erase(strv.begin()+left);
			strv.erase(strv.begin()+right-1);
			int i = 0;
			while(!inside.empty()){
				strv[left+i] = inside.top();
				inside.pop();
				i++;
			}
			break;
		}
		count++;
	}
	string res(strv.begin(), strv.end());
	pair<string,bool> result = make_pair(res, check);
	return result;
}

char reading(char c, int &count){
	if(c == '+') count++;
	else if(c == '-') count--;
	else if(c != '[' && c != ']' && c != '?'){
		int zover = count / ('Z'-'A');
		count -= ('Z'-'A'+1)*zover;
		char newchar = (char)c+count;
		while(newchar>'Z')	newchar = 'A' + newchar - 'Z' - 1;
		while(newchar<'A')	newchar = 'Z' - ('A' - newchar)+1;
		count = 0;
		return (char)newchar;
	}else if(c == '?'){
		count = 0;
		return 'A';
	}else return c;
	return 0;
}
		

int main(){
	string str;
	while(cin >> str,str != "."){
		int count = 0;
		vector<char> res;
		for(char s:str){
			char ch = reading(s, count);
			if(ch != 0)	res.push_back(ch);
		}

		bool check = true;
		string finals(res.begin(), res.end());
		while(check){
			pair<string, bool> pair_res = solve(finals);
			finals = pair_res.first;
			check = pair_res.second;
		}

		cout << finals << endl;
	}

	return 0;
}
### Prompt

Please provide a CPP coded solution to the problem described below:

Broken crypto generator

JAG (Japanese Alumni Group) is a mysterious organization composed of many programmers, and in order to enter the building where the headquarters of this organization is located, it is necessary to solve the ciphertext generated by a certain machine every time. This ciphertext consists of the symbols'+','-','[',']' and the uppercase alphabet, 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 '

Here, each symbol has the following meaning.

* + (Character): Represents the alphabet following that character (provided that the alphabet following'Z'is'A')
*-(Character): Represents the alphabet before that character (provided that the alphabet before'A'is'Z')
* [(Character string)]: Represents a character string that is horizontally inverted.



However, the machine that generates this ciphertext is currently out of order, and some letters of the alphabet in the ciphertext may be broken and unreadable. Unreadable characters are tentatively represented as'?'. As a result of the investigation, it was found that the method of filling the broken characters is such that the decrypted character string is the smallest in the dictionary order among the possible character strings after decoding. Your job is to decrypt this ciphertext correctly.

Input

The input consists of multiple datasets. Each dataset consists of one line containing a string in which some uppercase letters have been replaced with ‘?’ In the ciphertext defined by BNF above. You can assume that the length of each string is less than $ 80 $. You can also assume that the number of'?' In each dataset is greater than or equal to $ 0 $ and less than or equal to $ 3 $.

The end of the input is represented by a line containing only one character,'.'.

Output

For each data set, output the decrypted character string when the ciphertext is decrypted so that the decrypted character string is the smallest in the dictionary order.

Sample Input


A + A ++ A
Z-Z--Z + -Z
[ESREVER]
J ---? --- J
++++++++ A +++ Z ----------- A +++ Z
[[++-+-? [-++-? ++-+++ L]] [-+ ----- + -O]] ++++ --- + L
..

Output for Sample Input


ABC
ZYXZ
REVERSE
JAG
ICPC
JAPAN





Example

Input

A+A++A
Z-Z--Z+-Z
[ESREVER]
J---?---J
++++++++A+++Z-----------A+++Z
[[++-+--?[--++-?++-+++L]][-+-----+-O]]++++---+L
.


Output

ABC
ZYXZ
REVERSE
JAG
ICPC
JAPAN

### Response

```cpp
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<utility>

using namespace std;

pair<string,bool> solve(string str){
	bool check = false;
	vector<char> strv(str.begin(), str.end());
	stack<char> inside;
	int count = 0;
	int left = 0, right = 0;
	for(char ch:strv){
		inside.push(ch);
		if(ch == '['){
			left = count;
			stack<char> empty;
			swap(inside, empty);
		}
		if(ch == ']'){
			check = true;
			right = count;
			inside.pop();
			strv.erase(strv.begin()+left);
			strv.erase(strv.begin()+right-1);
			int i = 0;
			while(!inside.empty()){
				strv[left+i] = inside.top();
				inside.pop();
				i++;
			}
			break;
		}
		count++;
	}
	string res(strv.begin(), strv.end());
	pair<string,bool> result = make_pair(res, check);
	return result;
}

char reading(char c, int &count){
	if(c == '+') count++;
	else if(c == '-') count--;
	else if(c != '[' && c != ']' && c != '?'){
		int zover = count / ('Z'-'A');
		count -= ('Z'-'A'+1)*zover;
		char newchar = (char)c+count;
		while(newchar>'Z')	newchar = 'A' + newchar - 'Z' - 1;
		while(newchar<'A')	newchar = 'Z' - ('A' - newchar)+1;
		count = 0;
		return (char)newchar;
	}else if(c == '?'){
		count = 0;
		return 'A';
	}else return c;
	return 0;
}
		

int main(){
	string str;
	while(cin >> str,str != "."){
		int count = 0;
		vector<char> res;
		for(char s:str){
			char ch = reading(s, count);
			if(ch != 0)	res.push_back(ch);
		}

		bool check = true;
		string finals(res.begin(), res.end());
		while(check){
			pair<string, bool> pair_res = solve(finals);
			finals = pair_res.first;
			check = pair_res.second;
		}

		cout << finals << endl;
	}

	return 0;
}
```