Problem: Problem

Taro hides important books in the school locker, so he manages them more strictly than other people, and in addition to the keys provided by the school, he has installed the following button authentication type keys. ..

<image>

However, Taro, who easily forgets his password, has a habit of making it possible to write his password in one stroke. Even more sweet Taro wrote the candidates on paper when he thought about his password. Jiro, who happened to pick up the paper, tried to open the locker without throwing it away because he had a bad personality.

However, there are as many as 1000 password proposals written on the paper, and it seems that the sun will go down if you try all the inputs. Therefore, Jiro, who knows Taro's habits, decided to pick up only the ones that can be written with one stroke from the 1000 passwords in order to reduce the number of examinations, and asked the programmer to do the work.

There is always one or more candidates for each dataset. The rules for one-stroke writing are shown below.

1. The same characters are not consecutive. For example, AAA is not allowed.
2. One-stroke writing is possible in four directions, up, down, left and right. Do not move diagonally.
3. It does not go out of the frame of the button array and continue. Movement such as ABCA is not allowed.
4. You can pass over the characters that you have passed once.
5. Input of only one character of the button is regarded as one-stroke writing.



Input

The input consists of a group of 1000 character strings as shown below, and each line is an uppercase alphabetic string of 1 to 10 characters from A to I. It is assumed that there is no duplication of character string data.


string1
string2
...
string1000


Output

Extract only the candidate passwords (candidatePassword) from the input and list them as follows. In the following cases, N candidates are listed.


candidatePassword1
candidatePassword2
...
candidatePasswordN


The output is the same as the order of the input strings and the order must not be changed.

Example

Input

ABCFI
ABCABCABC
AEI
EFC
（中略）
DEHED
EEEEE
（以上でちょうど1000個）


Output

ABCFI
EFC
（中略）
DEHED

Solution (in CPP):

Solution:
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>

#define INF 100000000
#define EPS 1e-9

using namespace std;

typedef pair<int, int> P;
typedef long long ll;

vector<string> ans;
string maze[3];

int main() {

	maze[0] = "ABC";
	maze[1] = "DEF";
	maze[2] = "GHI";

	string str;
	int dx[] = { 1, 0, -1, 0 };
	int dy[] = { 0, 1, 0, -1 };

	for (int i = 0; i < 1000; i++){
		cin >> str;
		int sx, sy;
		for (int i = 0; i < 3; i++){
			for (int j = 0; j < 3; j++){
				if (maze[i][j] == str[0]){
					sx = j;
					sy = i;
				}
			}
		}
		queue<P> que;
		queue<int> num;
		que.push(P(sx, sy));
		num.push(0);
		bool flag = false;
		while (que.size()){
			P p = que.front();
			int n = num.front();
			que.pop();
			num.pop();

			n++;
			if (n == str.length()){
				flag = true;
				break;
			}

			int x = p.first;
			int y = p.second;

			for (int i = 0; i < 4; i++){
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3 && maze[ny][nx] == str[n]){
					que.push(P(nx, ny));
					num.push(n);
				}
			}
		}

		if (flag)
			ans.push_back(str);
	}

	for (int i = 0; i < ans.size(); i++){
		cout << ans[i] << endl;
	}

	return 0;
}