2D Banner - Testing Approx Problems | Repovive

1012A. 2D Banner

1s256 MB

You are given a grid with $n$ rows and $m$ columns. The cell in row $i$ and column $j$ has height $a_{i,j}$ .

You want to place a rectangular banner on the grid. A banner is determined by four integers $r_1, c_1, r_2, c_2$ such that $1 \le r_1 \le r_2 \le n$ and $1 \le c_1 \le c_2 \le m$ .

The score of this banner is:

$\min(a_{i,j}) \times (r_2-r_1+1) \times (c_2-c_1+1)$

where the minimum is taken over all cells $(i,j)$ satisfying $r_1 \le i \le r_2$ and $c_1 \le j \le c_2$ .

Let $OPT$ be the maximum possible score of a banner.

You do not need to find an optimal banner. You only need to output any banner whose score is at least half of $OPT$ .

In other words, if the score of your banner is $S$ , your output is accepted if $2 \times S \ge OPT$ .

Constraints

$1 \le t \le 5$
$1 \le n,m \le 800$
The sum of $n \times m$ over all test cases is at most $500000$
$1 \le a_{i,j} \le 10^6$

Input

t

\left. \begin{array}{l} n \quad m \\ a_{1,1} \quad a_{1,2} \quad \cdots \quad a_{1,m} \\ a_{2,1} \quad a_{2,2} \quad \cdots \quad a_{2,m} \\ \vdots \\ a_{n,1} \quad a_{n,2} \quad \cdots \quad a_{n,m} \end{array} \right\} \times t

Output

For each test case, output four integers $r_1, c_1, r_2, c_2$ , describing the banner you choose.

The output must satisfy $1 \le r_1 \le r_2 \le n$ and $1 \le c_1 \le c_2 \le m$ .

If the score of your banner is $S$ , it must satisfy $2 \times S \ge OPT$ .

The output format is:

\left. \begin{array}{l} r_1 \quad c_1 \quad r_2 \quad c_2 \end{array} \right\} \times t

Samples

Input

Case 1

8 10
3 4 2 5 1 4 3 2 5 1
2 5 20 20 20 20 20 3 4 2
4 1 20 20 20 20 20 5 2 3
5 3 20 20 20 20 20 4 1 5
1 2 20 20 20 20 20 3 5 4
4 5 2 1 3 5 2 4 3 1
2 3 5 4 1 2 5 3 4 2
5 1 4 3 2 1 4 5 2 3

Explanation

The chosen banner covers rows $2$ to $4$ and columns $3$ to $7$ .

All cells inside it have height $20$ , and its area is $3 \times 5 = 15$ , so its score is $20 \times 15 = 300$ .

The rectangle from row $2$ to row $5$ and column $3$ to column $7$ has score $20 \times 20 = 400$ , so the shown output is not optimal. Still, a score of $300$ is enough because it is at least half of the optimal score.

Output

2 3 4 7

You are given a grid with $n$ rows and $m$ columns. The cell in row $i$ and column $j$ has height $a_{i,j}$ .

You want to place a rectangular banner on the grid. A banner is determined by four integers $r_1, c_1, r_2, c_2$ such that $1 \le r_1 \le r_2 \le n$ and $1 \le c_1 \le c_2 \le m$ .

The score of this banner is:

$\min(a_{i,j}) \times (r_2-r_1+1) \times (c_2-c_1+1)$

where the minimum is taken over all cells $(i,j)$ satisfying $r_1 \le i \le r_2$ and $c_1 \le j \le c_2$ .

Let $OPT$ be the maximum possible score of a banner.

You do not need to find an optimal banner. You only need to output any banner whose score is at least half of $OPT$ .

In other words, if the score of your banner is $S$ , your output is accepted if $2 \times S \ge OPT$ .

$1 \le t \le 5$
$1 \le n,m \le 800$
The sum of $n \times m$ over all test cases is at most $500000$
$1 \le a_{i,j} \le 10^6$

t

\left. \begin{array}{l} n \quad m \\ a_{1,1} \quad a_{1,2} \quad \cdots \quad a_{1,m} \\ a_{2,1} \quad a_{2,2} \quad \cdots \quad a_{2,m} \\ \vdots \\ a_{n,1} \quad a_{n,2} \quad \cdots \quad a_{n,m} \end{array} \right\} \times t

For each test case, output four integers $r_1, c_1, r_2, c_2$ , describing the banner you choose.

The output must satisfy $1 \le r_1 \le r_2 \le n$ and $1 \le c_1 \le c_2 \le m$ .

If the score of your banner is $S$ , it must satisfy $2 \times S \ge OPT$ .

The output format is:

\left. \begin{array}{l} r_1 \quad c_1 \quad r_2 \quad c_2 \end{array} \right\} \times t

The chosen banner covers rows $2$ to $4$ and columns $3$ to $7$ .

All cells inside it have height $20$ , and its area is $3 \times 5 = 15$ , so its score is $20 \times 15 = 300$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

1012A. 2D Banner

Constraints

Input

Output

Samples

1012A. 2D Banner

Constraints

Input

Output

Samples