Sliding Puzzle

Limits: 4 sec., 1024 MiB

In this problem, you have to solve a sliding tile puzzle similar to the well-known 15 puzzle. The puzzle frame is \(h\) tiles high and \(w\) tiles wide. The rows are numbered 1 to \(h\) from top to bottom. Similarly, the columns are numbered 1 to \(w\) from left to right. The frame contains \(h \cdot w - 1\) tiles labeled with letters and one unoccupied tile position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically, respectively. The goal of the puzzle is to place the tiles in alphabetical order leaving the bottom right corner unoccupied.

You are given the initial frame placement. In one move you can slide a tile or a group of neighboring tiles towards the open position. For example, consider the sample initial frame placement, which has three possible moves:

• slide down tile h

• slide left tile a

• in the bottom row, slide left tiles a and t

Your goal is to reach the target placement using as few moves as possible. It is guaranteed that the target placement can be reached from the initial one with not more than \(10^5\) moves. You can try solving the puzzle in manual mode at slide.algotester.com.

You are given the test generator that produces a puzzle frame based on a seed number. It is possible to check how your solution performs on five example test cases using our puzzle visualizer. Just click on the play icon next to one of your submissions to launch it. Note that it might take a few seconds to load the visualizer.

Input

The first line contains two integers \(h\) and \(w\). The following \(h\) lines describe the puzzle frame. Each of the lines contains \(w\) characters which can be a lowercase English letter (a-z) or underscore character (_) denoting the open position. There will be exactly one open position character in the input. Note that tile labels are not necessarily distinct and tiles with the same label are indistinguishable.

Output

In the first line print integer \(k\) which is the number of moves in your solution. In each of the next \(k\) lines print two integers \(r\) and \(c\) describing a move that slides tile at row \(r\) and column \(c\) toward the open position, pushing all tiles in between correspondingly. Note that the position \((r, c)\) must be on the same row or the same column as the open position and also must contain a tile labeled with a letter. After the move is performed, \((r, c)\) becomes unoccupied.

Constraints

\(2 \le h, w \le 10\),

\(1 \le r \le h\), \(1 \le c \le w\),

\(0 \le k \le 10^5\).

Samples

Input (stdin) сopy	Output (stdout) сopy
2 3 hot _at	7 2 2 2 3 1 3 1 1 2 1 2 2 2 3

Notes

You can print any valid sequence of moves your solution can find, not necessarily the most optimal one.

The sample output provided above corresponds to the quickstart solution. Please, refer to the Quickstart section for more details on how it solves the puzzle.

Scoring

If your output for a test is invalid, e.g. the number of moves is greater than \(10^5\), or it contains an invalid move, or the final puzzle placement is incorrect, etc. your score will be 0. Otherwise, your score for the test is calculated as \[\left\lfloor \frac{h \cdot w \cdot (h + w)}{k + 1} \cdot 10^7 \right\rfloor.\] Your overall score is the sum of your scores over all test cases.

Submissions

• The execution time limit is 4 seconds per test case and the memory limit is 1024 mebibytes.

• The code size limit is 64 kibibytes.

• The compilation time limit is 1 minute.

• There are 50 provisional test cases. Your submissions will be evaluated on the provisional set during the submission phase.

• You can submit your code once per 10 minutes and you will get feedback with your score for each of the provisional tests.

• There will be 500 test cases in the final testing after the submission phase is over. The final results will be announced in one week.

Quickstart

Check the sample solution, which solves the puzzle row-by-row and column-by-column. The exceptions are two bottommost rows and two rightmost columns that require special attention and case study.

The source code is available for some of the contest programming languages:

• C++

• Python

• Java

• C#

Tests

All test cases including provisional and final sets are generated by the generator. It randomly chooses the frame sizes as well as all tile labels. Then it starts from the target placement and applies up to \(10^5\) random moves. This guarantees that the given puzzle is solvable.

A test case is produced by providing the generator with a seed number. Seed number \(1\) corresponds to the sample case. You do NOT know seed numbers for provisional or final test sets, but you can use the generator for local testing by taking a few easy steps:

1. Check the generator source code

2. Save it to a file named generator.java

3. Compile the source code with Java

   javac generator.java

4. Generate a test case for some seed number

   java generator <seed>

   This will print the test case for <seed> to standard output.

Visualizer

For your submission, the problem visualizer can show all puzzle frame placements in a move-by-move mode for five example tests. To launch the visualizer, click the play icon next to your submission. Note that only tests with a valid solution output are available for visualization.

The visualizer has a test selector and several settings such as play speed, highlights, etc. You can use the progress bar to scroll the process to the desired moment.

Additionally, there is a manual mode. Just visit slide.algotester.com and enjoy the puzzle.