D. Электронная таблица Нанами
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

Цифровая таблица имеет размер 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)).

Нанами записала, как менялась доска во время матча, также у нее есть несколько вопросов описанного выше типа, можете ли вы ответить на все ее вопросы?

Входные данные

В первой строке записано три целых числа через пробел — n, m и q (1 ≤ n, m, q ≤ 1000) — высота и ширина электронной таблицы и количество операций.

Затем следует n строк, в каждой строке записано по m целых чисел через пробел: j-е целое число в i-й строке равняется ai, j — начальному состоянию пикселя (i, j).

  • Если ai, j = 0, то пиксель (i, j) изначально не светится.
  • Если ai, j = 1, то пиксель (i, j) изначально светится.

Затем следуют q строк, в каждой строке записано по три целых числа через пробел op, x, и y (1 ≤ op ≤ 2; 1 ≤ x ≤ n; 1 ≤ y ≤ m), описывающих события в порядке их возникновения.

  • Если op = 1, то пиксель в (x, y) меняет состояние (если он светился, то теперь он перестает светиться, и наоборот).
  • Если op = 2, то Нанами спрашивает у вас площадь наибольшего светящегося подпрямоугольника с пикселем (x, y) на стороне.
Выходные данные

Для каждого вопроса выведите единственную строку, содержащую целое число — ответ на вопрос Нанами.

Примеры
Входные данные
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
Входные данные
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
Примечание

Рассмотрим первый пример.

В первом вопросе подпрямоугольник должен содержать пиксель (2, 2) на стороне, но этот пиксель не светится, поэтому подходящих светящихся прямоугольников нет, и ответ равняется 0.

В втором вопросе подпрямоугольник должен содержать пиксель (1, 2) на стороне. Самый большой такой подпрямоугольник — это подпрямоугольник с левым верхним углом в (1, 2) и правым нижним углом в (1, 3).

В последнем вопросе подпрямоугольник должен содержать пиксель (2, 2) на стороне, который засветился после третьего события. Самый большой светящийся подпрямоугольник — это подпрямоугольник с верхним левым углом в (1, 2) и правым нижним углом в (3, 3).