Mini March Coding Challenge 2014

Kirito is facing a large field of ~N~ rows by ~M~ columns of monsters to the east. Each monster is either powerful or weak. Things may look grim for the Black Swordsman, but luckily he has the powerful skill «Starburst Stream» — a skill that can instantly kill a rectangle of monsters. However, there is a restriction — Kirito can only use this skill if all monsters in every column of the attack rectangle are all either powerful or weak. Also, since Kirito is on the western side of the field of monsters, one of the sides of the rectangle must be on the first column.

Kirito is watching the monsters for ~Q~ minutes. Every minute, two rows ~i~ and ~j~ catches his eye, and he wants to know the largest number of monsters he can kill if he uses «Starburst Stream» on an attack rectangle that has its top side on row ~i~, its bottom side on row ~j~, and its left side on column ~1~. These are merely queries, and Kirito does not actually kill the monsters in that rectangle. Help Kirito find the answer to his query for every pair of rows ~i~ and ~j~. Additionally, once Kirito learns of the answer, the monsters in rows ~i~ and ~j~ feel uneasy because of a mysterious killing intent, and so will switch places one-for-one (i.e. the rows are swapped). You should consider the new configuration of monsters for subsequent queries.

Input Specification

The first line of input has two integers, ~N~ (~1 \le N \le 2000~), the number of rows of monsters, and ~M~ (~1 \le M \le 5000~), the number of columns of monsters.
The next ~N~ lines will contain ~M~ characters each, each of which is either 0, to denote a weak monster or 1, to denote a powerful monster.
The next line of input has one integer, ~Q~ (~1 \le Q \le 50\,000~), the number of minutes Kirito is observing.
The next ~Q~ lines each contain a pair of integers, ~i~ and ~j~ (~1 \le i \le j \le N~), the pair of rows that catch Kirito's interest.

The following additional constraints will apply.

• At least 5% of the marks will be for test cases where ~N \le 100~, ~M \le 100~, and ~Q \le 100~;
• At least 25% of the marks will be for test cases where ~N \le 2000~, ~M \le 2000~, and ~Q \le 20\,000~;
• The remaining marks will be for test cases where ~N \le 2000~, ~M \le 5000~, and ~Q \le 50\,000~.

Warning: Be careful when reading the input, which may exceed 10 megabytes.

Output Specification

For each of the ~Q~ pairs of rows in the input, output a single integer on a line: the largest number of monsters Kirito could kill while satisfying the constraints as described above, or ~0~ if Kirito cannot use the skill «Starburst Stream».

Sample Input

5 8
01000100
01000100
00100111
00100110
00100000
4
1 2
3 5
3 4
2 2

Sample Output

16
15
10
8

Explanation

For the first pair of rows, ~(1, 2)~, Kirito could use «Starburst Stream» on the entirety of both rows (16 monsters).

01000100
01000100

The configuration is effectively unchanged, because those rows had the same types of monsters in the same positions.
For the second pair of rows, ~(3, 5)~, Kirito could use «Starburst Stream» on a 5 by 3 rectangle (15 monsters).

00100
00100
00100

The configuration changes to:

01000100
01000100
00100000
00100110
00100111

For the third pair of rows, ~(3, 4)~, Kirito could use «Starburst Stream» on a 5 by 2 rectangle (10 monsters).

00100
00100

The configuration changes to:

01000100
01000100
00100110
00100000
00100111

For the last pair of rows, ~(2, 2)~, Kirito could use «Starburst Stream» on the whole row (8 monsters). If there were more queries, this would not change the configuration.

This problem statement is the exclusive and proprietary property of DMOJ. Any unauthorized use or reproduction of this information without the prior written consent of DMOJ is strictly prohibited. (c)2014, DMOJ. All rights reserved.