2114. My craft @ Timus Online Judge

2114. 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 ≤ x ≤ n, 1 ≤ y ≤ m). Water, spilled in the cell (x₀, y₀), floods all the cells (x, y), for which x₀ ≤ x and y₀ ≤ y (as in the game the southeast wind blows) and x + y ≤ x₀ + y₀ + 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 a_ij (0 ≤ a_ij ≤ 10⁹) — 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 k_i (1 ≤ k_i ≤ 10⁵) — 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 k_i, and the coordinates x_i, y_i of an optimal cell to spill water in. If there are several possible answers, you may output any of them.

Samples

input	output
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