버블 맵

Bubble Inc.는 지도를 여러 확대 단계(zoom level)로 살펴볼 수 있는 새로운 기술을 개발하고 있다. 지도로 나타낼 영역은 직사각형 평면이며, 이를 더 깊은 확대 단계를 나타내는 직사각형 하위 영역들로 재귀적으로 분할한다.

이 기술은 지도를 사분트리(quadtree) 라는 구조로 표현한다. 이름이 x인 직사각형 영역은 가로와 세로를 모두 절반으로 나누어 크기가 같은 네 개의 하위 영역으로 분할할 수 있다. 이들은 x의 자식 영역이며 다음과 같이 이름 붙인다.

• xp — 왼쪽 위
• xq — 오른쪽 위
• xr — 오른쪽 아래
• xs — 왼쪽 아래

여기서 xc는 문자열 x와 문자 p, q, r, s 중 하나를 이어 붙인 것을 뜻한다. 왼쪽 위에서 시작해 시계 방향으로 나열하면 xp, xq, xr, xs 순이다.

+----+----+
| p  | q  |
+----+----+
| s  | r  |
+----+----+

기준 영역의 이름은 m이므로 그 자식 영역은 mp, mq, mr, ms이다. 어떤 영역이든 더 잘게 나눌 수 있다. 예를 들어 ms는 msp, msq, msr, mss로 나뉜다.

이름의 길이가 같은 두 영역은 크기가 같으므로 같은 확대 단계에 있다. 같은 확대 단계의 두 영역이 한 변 전체를 공유하면 서로 이웃이라고 한다. 기준 영역 m의 바깥은 지도에 나타내지 않으며, 모든 확대 단계에서 m의 모든 하위 영역은 지도에 나타난다.

영역의 이름이 주어지면, 위·아래·왼쪽·오른쪽 방향으로 인접한 네 이웃 영역의 이름을 구하여라.

첫째 줄에 테스트 케이스의 개수 N이 주어진다. 이어지는 N개의 줄에는 각각 C개의 문자로 이루어진 영역 이름이 하나씩 주어진다($2 \le C \le 5000$). 첫 문자는 항상 m이고, 나머지 문자는 각각 p, q, r, s 중 하나이다.

각 테스트 케이스마다 한 줄에 인접한 네 영역의 이름을 위, 아래, 왼쪽, 오른쪽 순서로 공백 한 칸으로 구분하여 출력한다. 지도 바깥에 있어 존재하지 않는 이웃은 이름 대신 <none>을 출력한다.