Нанами — эксперт в видеоиграх. Сегодня хороший друг Нанами, Хаджиме, пригласил ее посмотреть бейсбольный матч. Скрепя сердце девушка пошла с ним на стадион. Матч был не интересен Нанами, и она смотрела по сторонам в поисках чего-нибудь интересного. Внезапно она заметила цифровую таблицу в одном из концов стадиона.
Цифровая таблица имеет размер n пикселей в высоту и m пикселей в ширину, каждый пиксель таблицы либо светится, либо — нет. Пиксели описываются их координатами. Будем обозначать j-й пиксель в i-й строке таблицы записью (i, j). Во время матча электронная таблица отображает сообщения путем подсвечивания некоторой комбинации пикселей. Нанами заметила, что состояние пикселей на доске время от времени меняется. В определенное время определенные пиксели на доске могут переключаться со светящегося на не светящийся и наоборот.
Нанами интересно, какова площадь наибольшего светящегося подпрямоугольника таблицы, такого, что на его стороне есть определенный пиксель. Пиксель (i, j) принадлежит стороне подпрямоугольника, левый верхний и правый нижний углы которого находятся в (x1, y1) и (x2, y2), тогда и только тогда, когда выполняется следующее логическое условие:
((i = x1 или i = x2) и (y1 ≤ j ≤ y2)) или ((j = y1 или j = y2) и (x1 ≤ i ≤ x2)).Нанами записала, как менялась доска во время матча, также у нее есть несколько вопросов описанного выше типа, можете ли вы ответить на все ее вопросы?
Выходные данные
Для каждого вопроса выведите единственную строку, содержащую целое число — ответ на вопрос Нанами.
Примечание
Рассмотрим первый пример.
В первом вопросе подпрямоугольник должен содержать пиксель (2, 2) на стороне, но этот пиксель не светится, поэтому подходящих светящихся прямоугольников нет, и ответ равняется 0.
В втором вопросе подпрямоугольник должен содержать пиксель (1, 2) на стороне. Самый большой такой подпрямоугольник — это подпрямоугольник с левым верхним углом в (1, 2) и правым нижним углом в (1, 3).
В последнем вопросе подпрямоугольник должен содержать пиксель (2, 2) на стороне, который засветился после третьего события. Самый большой светящийся подпрямоугольник — это подпрямоугольник с верхним левым углом в (1, 2) и правым нижним углом в (3, 3).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 5
0 1 1 0
1 0 0 1
0 1 1 0
2 2 2
2 1 2
1 2 2
1 2 3
2 2 2
|
0
2
6
|
|
2
|
3 3 4
1 1 1
1 1 1
1 1 1
2 2 2
1 2 2
2 1 1
2 2 1
|
6
3
3
|