D. Моё ремесло @ Вузовско-академическая олимпиада по информатике 2019 @ Timus Online Judge

D. Моё ремесло

Ограничение времени: 3.0 секунды
Ограничение памяти: 256 МБ

Саша играет в новую игру под названием Моё ремесло. В этой игре можно делать всё, о чём только может мечтать ребёнок. Саша собирается в рейд за алмазами, а чтобы не умереть от голода (да, игра очень реалистичная, если не считать пиксельную графику и то, что все объекты в игре — это кубы), она должна запастись хлебом, а чтобы сделать хлеб ей нужно пшено. К счастью, у нее есть огород, на котором как раз поспела пшеница.

Огород представляет из себя прямоугольное поле размером n на m клеток. В каждой клетке огорода растет пшеница, при сборе которой выпадает разное, но известное количество пшена. Саша очень не хочет собирать пшено с каждой клетки, и поэтому она готова вылить воду на одну из клеток, которая затем растечётся и затопит другие клетки. Тогда Саше останется только пробежать по огороду и собрать все пшено, которое выпало с затопленных клеток.

Каждая клетка задается парой координат (x, y), где x — номер строки, y — номер столбца (1 ≤ x ≤ n, 1 ≤ y ≤ m). Вода, разлитая в клетке (x₀, y₀), затопит все клетки (x, y), для которых выполняется x₀ ≤ x и y₀ ≤ y (так как в игре дует юго-восточный ветер) и x + y ≤ x₀ + y₀ + k (где k — параметр игры, называемый силой ветра). Помоги Саше для силы ветра из q возможных найти клетку, на которую нужно вылить воду, чтобы с затопленных клеток выпало максимальное количество пшена.

Исходные данные

Первая строка содержит два натуральных числа n, m (1 ≤ n, m ≤ 500). В каждой из следующих n строк содержится по m чисел a_ij (0 ≤ a_ij ≤ 10⁹) — количество пшена в клетке i, j. Можно считать, что клетки, лежащие вне огорода, не содержат пшено.

В (n + 2)-й строке содержится число q (1 ≤ q ≤ 50) — количество возможных сил ветра. В следующей строке содержится q чисел k_i (1 ≤ k_i ≤ 10⁵) — силы ветра.

Результат

Выведите q строк, в каждой их которых содержится 3 числа через пробел: наибольшее количество пшена, которое может выпасть, если вылить воду в одну из клеток при силе ветра k_i, и координаты этой клетки x_i, y_i. Если возможных решений несколько, выведите любое.

Примеры

исходные данные	результат
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

Автор задачи: Валентин Зуев
Источник задачи: Вузовско-академическая олимпиада по информатике 2019