ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

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

Ограничение времени: 3.0 секунды
Ограничение памяти: 256 МБ
Саша играет в новую игру под названием Моё ремесло. В этой игре можно делать всё, о чём только может мечтать ребёнок. Саша собирается в рейд за алмазами, а чтобы не умереть от голода (да, игра очень реалистичная, если не считать пиксельную графику и то, что все объекты в игре — это кубы), она должна запастись хлебом, а чтобы сделать хлеб ей нужно пшено. К счастью, у нее есть огород, на котором как раз поспела пшеница.
Огород представляет из себя прямоугольное поле размером n на m клеток. В каждой клетке огорода растет пшеница, при сборе которой выпадает разное, но известное количество пшена. Саша очень не хочет собирать пшено с каждой клетки, и поэтому она готова вылить воду на одну из клеток, которая затем растечётся и затопит другие клетки. Тогда Саше останется только пробежать по огороду и собрать все пшено, которое выпало с затопленных клеток.
Каждая клетка задается парой координат (x, y), где x — номер строки, y — номер столбца (1 ≤ xn, 1 ≤ ym). Вода, разлитая в клетке (x0, y0), затопит все клетки (x, y), для которых выполняется x0x и y0y (так как в игре дует юго-восточный ветер) и x + yx0 + y0 + k (где k — параметр игры, называемый силой ветра). Помоги Саше для силы ветра из q возможных найти клетку, на которую нужно вылить воду, чтобы с затопленных клеток выпало максимальное количество пшена.

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

Первая строка содержит два натуральных числа n, m (1 ≤ n, m ≤ 500). В каждой из следующих n строк содержится по m чисел aij (0 ≤ aij ≤ 109) — количество пшена в клетке i, j. Можно считать, что клетки, лежащие вне огорода, не содержат пшено.
В (n + 2)-й строке содержится число q (1 ≤ q ≤ 50) — количество возможных сил ветра. В следующей строке содержится q чисел ki (1 ≤ ki ≤ 105) — силы ветра.

Результат

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

Примеры

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