|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
D - Bubble Maps
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Bubble Inc. is developing a new technology for browsing a map at different zoom levels. Their new technology assumes that the region to be mapped is a rectangular plane surface and it divides this surface in rectangular sub-regions, which represent deeper zoom levels.
Bubble Inc. technology represents maps using a structure known as quad-tree. In a quad-tree, a rectangular region named $\texttt{x}$ may be divided in half, both horizontally and vertically, resulting in four equal-sized rectangular sub-regions. Those sub-regions are called child regions of $\texttt{x}$, and are named $\texttt{xp}$ for the top-left, $\texttt{xq}$ for the top-right, $\texttt{xr}$ for the bottom-right and $\texttt{xs}$ for the bottom-left regions, where $\texttt{xc}$ represents the concatenation of string x and character $c = \texttt{‘p’}, \texttt{‘q’}, \texttt{‘r’}$ or $\texttt{‘s’}$. For example, if the base region to be mapped is called m, the child regions of $\texttt{m}$ are, from top-left in clockwise order: $\texttt{mp}$, $\texttt{mq}$, $\texttt{mr}$ and $\texttt{ms}$, as illustrated below.
Any region can be further subdivided. For example, the region named $\texttt{ms}$ can be further divided into sub-regions $\texttt{msp}$, $\texttt{msq}$, $\texttt{msr}$ and $\texttt{mss}$, as illustrated below.
As another example, the figure below shows the result of subdividing the child sub-regions of the region named $\texttt{msr}$.
Sub-regions with names of the same length have the same zoom level, since they represent regions of the same size. Sub-regions in the same zoom level that share a common side are said to be neighbors.
Anything that lies outside the base region $\texttt{m}$ is not mapped and, for every zoom level, all sub-regions of $\texttt{m}$ are mapped.
Bubble’s map technology provides a way for the user to navigate from a given sub-region to neighboring sub-regions in the directions up, down, left and right. You mission is to help Bubble Inc. in finding the neighboring sub-regions of a given sub-region. That is, given the name of a rectangular sub-region, you must determine the names of its four neighboring sub-regions.
Input
The input contains several test cases. The first line contains one integer $N$ indicating the number of test cases. Each of the following $N$ lines represents a test case, containing the name of a region composed by $C$ characters $(2 \leq C \leq 5000)$, the first always being the letter $\texttt{‘m’}$ and the following being either $\texttt{‘p’}$, $\texttt{‘q’}$, $\texttt{‘r’}$ or $\texttt{‘s’}$.
The input must be read from standard input.
Output
For each test case in the input your program must produce one line of output, containing the names of the four neighboring regions of the given region in the order of direction up, down, left, right. For the neighbors that are not mapped you should output $\texttt{<none>}$ instead of its name. Leave one blank space between two consecutive names.
The output must be written to standard output.
Sample test(s)
Input
2
mrspr
mps
Output
mrspq mrssq mrsps mrsqs
mpp msp <none> mpr