Background

The Chinese translation of Umineko no Naku Koro ni EP8 was finally released at the end of this summer vacation. As Furudo Erika, a very popular character in the whole work, she was naturally very active in the story. She served as the commander in the battle to conquer the Golden Land, and the entire battle process was recorded in the City of Books, making it convenient for later people to review it.

Problem Description

The battle situation at that time was as follows. The Golden Land can be viewed as a cuboid space. We use $(0,0,0)\sim(n-1,m-1,k-1)$ to represent each unit cell inside it. Erika commanded $t$ warships of different ranks to suddenly appear in $t$ different cells of the Golden Land using magic. After that, goats continuously poured out from the warships. In each unit of time, the goats will expand from their current cell to the adjacent cells in the $6$ directions by one cell (if the neighboring cell has already been occupied, they do not expand into it). If two groups of goats want to occupy the same cell at the same time, the higher-rank goats occupy it first.

Soon, the Golden Land turned into an ocean of goats. But Erika, as the commander, could not find the locations of the warships among the huge number of goats. So she handed the problem to you, Mr. Goat, who was a young general eager to gain military merit and then return to his hometown to find Goat Girl. Naturally, you would not give up this opportunity, so you quickly found the warships’ locations. Your achievement would of course be recorded in the documents of the City of Books.

Input Format

The first line contains an integer $test$, the number of test cases. The following are $test$ test cases.

For each test case, the first line contains three integers $n,m,k$. Then there are $n$ blocks, each block consists of an $m$-row $k$-column character matrix.

The $i$-th block describes the situation in the region $(i,0,0)\sim(i,m-1,k-1)$.

Goats of different ranks are represented by different lowercase English letters. A letter with a smaller lexicographical order means a higher goat rank.

Adjacent blocks are separated by a blank line.

Output Format

Output $test$ parts, separated by a blank line.

For each part, output $t$ lines, where $t$ is the number of warships in this test case. Each line has the format

ch x y z

meaning that the warship with label $ch$ is located at $(x,y,z)$.

The output order of warships does not matter. If there are multiple solutions, output any one.

2
1 2 2
dd
gg

3 3 3
aaa
aaa
baa

aaa
aaa
baa

aaa
aaa
bcc

d 0 0 0
g 0 1 0

a 1 1 1
b 1 2 0
c 2 2 1

Hint

Data Scale and Constraints

Test points $1\sim3$: $n=1$, $n\times m\times k\leqslant10$.

Test points $4\sim6$: $n=1$, $n\times m\times k\leqslant100$.

Test points $7\sim10$: $n=1$, $n\times m\times k\leqslant500$.

Test points $11\sim20$: $n\times m\times k\leqslant1500$.

For all testdata, $test\leqslant10$, $t\leqslant26$.

Translated by ChatGPT 5