Data Check

You are given a directed grid graph with $N$ rows and $M$ columns. Its vertices are denoted by $(i,j)$, where $1 \leq i \leq N$ and $1 \leq j \leq M$.

For every pair of orthogonally adjacent vertices, there is exactly one directed edge between them. In other words, exactly one of the two possible directions is chosen for every horizontally or vertically adjacent pair.

For four integers $r_1,c_1,r_2,c_2$ satisfying and , the represented by them is the induced subgraph consisting of the following vertices and all edges between them:

The given graph contains at least one directed cycle. Among all subrectangles containing a directed cycle, find one minimizing the area

If several subrectangles have the minimum area, choose the one for which $(r_1,c_1,r_2,c_2)$ is lexicographically smallest.

The input is given from Standard Input in the following format:

$T$ case$_1$ case$_2$ $$

For each test case, print four integers $r_1,c_1,r_2,c_2$ representing the answer on one line.

• $1 \leq T \leq 50$.
• $2 \leq N,M \leq 5\,000$.
• The sum of $$ over all test cases does not exceed .