2D Banner - Weekly Challenge 1: Approximation | Repovive

W1D2B. 2D Banner

2 pts1s256 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$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

W1D2B. 2D Banner

Constraints

Input

Output

Samples

W1D2B. 2D Banner

Constraints

Input

Output

Samples