| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 512 MB | 4 | 1 | 1 | 100.000% |
There are $n \times n$ cells on a grid, the top-left cell is at $(1,1)$ while the bottom-right cell is at $(n,n)$. In the cell $(i,j)$ which is at row $i$ and column $j$, there are $\left(n^2\right)^{a_{i,j}}$ diamonds.
You start at $(1,1)$ and move to $(n,n)$. At any cell $(i,j)$, you can move to $(i+1,j)$ or $(i,j+1)$, provided that you don't move out of the grid. Clearly, you will make exactly $2n-2$ steps. When you are at a cell, you can take all the diamonds at this cell, including the starting point $(1,1)$ and the destination $(n,n)$.
However, some cells are blocked, but you don't know which cells are blocked. Please write a program to answer $q$ queries. In each query, you will be given four integers $r_1$, $r_2$, $c_1$, $c_2$, and you need to report the maximum number of diamonds that you can take without passing the cells $(i,j)$ such that $r_1 \leq i \leq r_2$ and $c_1 \leq j \leq c_2$.
The first line contains a single integer $T$ ($1 \leq T \leq 5$), the number of test cases. For each test case:
The first line contains two integers $n$ and $q$ ($2 \leq n \leq 400$, $1 \leq q \leq 200\,000$) denoting the size of the grid and the number of queries.
Each of the following $n$ lines contains $n$ integers, the $i$-th line contains $a_{i,1},a_{i,2},\dots,a_{i,n}$ ($1\leq a_{i,j}\leq n^2$) denoting the number of diamonds in each cell.
Each of the following $q$ lines contains four integers $r_1$, $r_2$, $c_1$, $c_2$ ($1 \leq r_1 \leq r_2 \leq n$, $1 \leq c_1 \leq c_2 \leq n$) describing a query. It is guaranteed that you can find at least one valid path in each query.
For each query, print a single line containing an integer: the maximum number of diamonds that you can take. Note that the answer may be extremely large, so please print it modulo $10^9+7$ instead.
1 2 2 2 3 1 4 1 1 2 2 2 2 1 1
276 336