ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

University academic school olympiad in informatics 2019

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. My craft

Time limit: 3.0 second
Memory limit: 256 MB
Sasha plays a new game called “My Craft”. In this game she can do anything a child may possibly think of. Sasha is planning a trip for diamonds, and in order to not starve (yes, the game is very realistic except for pixel graphics and the fact that all the objects in the game are cubes), she wants to stock up on some bread. And in order to make bread she needs millet. Fortunately, she has a garden, where the millet has already ripened.
The garden is represented as a rectangular grid of size n× m each cell of which contains some amount of millet. Sasha doesn’t really want to collect millet from every cell of the garden. Instead, she wants to spill water in one cell and then wait for it to flood other cells. All she needs to do afterwards is run through the garden and collect the millet which appeared in the flooded cells.
Every cell of the garden is represented by a pair of coordinates (x, y), where x is a row number and y is a column number (1 ≤ xn, 1 ≤ ym). Water, spilled in the cell (x0, y0), floods all the cells (x, y), for which x0x and y0y (as in the game the southeast wind blows) and x + yx0 + y0 + k (where k is a parameter of the game called wind power). Help Sasha find the optimal cell to spill water in for each of q wind powers. A cell is considered optimal to spill water in, if the total amount of millet collected from the flooded cells is maximal.

Input

The first line contains two integer numbers separated with a space n, m (1 ≤ n, m ≤ 500). Each of the next n lines contains m integer numbers separated with a space aij (0 ≤ aij ≤ 109) — the amount of millet in the cell (i, j). You may assume that cells outside of the garden do not contain any millet.
The next line contains a single integer number q (1 ≤ q ≤ 50) — the number of possible wind powers. The next line contains q integer numbers separated with a space ki (1 ≤ ki ≤ 105) — the wind powers.

Output

You should output q lines, each containing 3 numbers separated with a space: the maximum total amount of millet, which may be collected after spilling water in one cell with a given wind power ki, and the coordinates xi, yi of an optimal cell to spill water in. If there are several possible answers, you may output any of them.

Samples

inputoutput
3 5
1 4 7 4 1
4 7 9 7 4
1 4 7 4 1
1
3
50 1 2
3 3
1 2 3
4 5 6
7 8 9
4
2 3 4 5
30 2 1
39 2 1
45 1 1
45 1 1
3 5
3 4 3 2 1
2 3 4 3 2
1 2 3 4 3
2
2 3
18 1 2
25 1 2
9 4
8 1 8 718
88 88 1 8
8 818 1 8
888 8 1 8
1 88 88 8
1 888 8 8
1 8 88 81
1 8 788 1
188 8 8 1
3
3 5 7
2626 1 1
2992 2 1
4001 3 1
15 6
888 88 1 88 8 8
88 88 1 1 88 88
8 8 111 111 8 8
88 11 1 1 11 88
8 1 88 1 881 88
8 1 88 1 88 118
811 88 1 88 1 8
8 1 88 1 88 118
8 111 1 1 111 8
81 8 1 111 8 18
88 88 1 1 88 88
8 1 88 1 88 188
8 8 188 881 8 8
88 88 1 1 88 88
888 88 1 88 8 8
5
7 13 14 8 7
3245 9 1
6371 3 1
6725 2 1
3883 1 1
3245 9 1
Problem Author: Valentin Zuev
Problem Source: University academic school olympiad in informatics 2019
To submit the solution for this problem go to the Problem set: 2114. My craft