Задача №111802. Битые пикселы
Боксёр Николай очень любит свой ноутбук. Впрочем, бокс он любит больше, в результате чего значительная часть матрицы ноутбука представляет собой битые пикселы.
Для поиска информации Николай использует браузер, которым можно нормально пользоваться, только если он занимает прямоугольную область со сторонами, параллельными границам, из работающих пикселей. Естественно, чем больше эта область, тем удобнее.
Николай готовится к очередной тренировке. Известно, что в результате на мониторе появится ровно один новый битый пиксел. Николай подобрал несколько вариантов положения этого пиксела и просит вас для каждого из них найти максимальную по площади область работающих пикселей, которая будет доступна после его добавления.
В первой строке ввода записаны целые числа W и H "— разрешение матрицы ( 1 ≤ W , H ≤ 3000 ). В следующих H строках записано по W цифр 0 и 1 без пробелов "— 0 для работающего и 1 для битого пиксела.
В следующей строке записано число Q "— количество вариантов расположения нового битого пиксела, подготовленных Николаем ( 1 ≤ Q ≤ 500 000 ).
В следующих Q строках записаны пары целых чисел x i , y i : новый битый пиксел в варианте с номером i расположен на позиции x i в строке y i ( 1 ≤ x i ≤ W , 1 ≤ y i ≤ H ). Гарантируется, что пиксел в запросе не является битым.
Для каждого из вариантов расположения выведите одно целое число "— максимальную площадь прямоугольной области работающих пикселов.
4 3 0010 0001 0000 3 1 1 2 3 1 3
6 4 4