D - Lighting Panels and Picture Frames Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、縦 H 行、横 W 列のマス目からなる照明パネルを持っています。上から r 行目、左から c 列目のマスをマス (r, c) と呼びます。

はじめ、すべてのマスの照明は消灯しています。高橋君は N 回の操作を順に行います。

i 回目の操作では、行が A_i 以上 B_i 以下、かつ列が C_i 以上 D_i 以下であるすべてのマスの状態を反転します。すなわち、点灯しているマスは消灯し、消灯しているマスは点灯します。

すべての操作が終わった後の照明パネルの状態を最終状態と呼びます。

最終状態において、点灯しているマスどうしの辺を共有する上下左右 4 方向の隣接関係による連結成分を、それぞれ島と呼びます。点灯しているマスが 1 つも存在しない場合、島の数は 0 です。

青木君は最終状態に対して M 個の質問をします。高橋君は各質問に答えなければなりません。

j 個目の質問では、行が P_j 以上 Q_j 以下、かつ列が R_j 以上 S_j 以下である長方形の領域を指定します。

各質問について、以下の 2 つの値を求めてください。

  1. 指定された領域内にある、点灯しているマスの個数
  2. 最終状態の島のうち、指定された領域内に完全に収まっているものの個数

ここで、ある島が領域内に完全に収まっているとは、その島に属するすべてのマスが指定された領域内にあることをいいます。

注意： 島は最終状態のパネル全体で定義されたものです。質問で指定された領域内だけで改めて連結成分を求め直すわけではありません。

制約

  • 1 \leq H \leq 1000
  • 1 \leq W \leq 1000
  • 0 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • N + M \leq 10^5
  • M \times H \times W \leq 5 \times 10^7
  • 1 \leq A_i \leq B_i \leq H (1 \leq i \leq N)
  • 1 \leq C_i \leq D_i \leq W (1 \leq i \leq N)
  • 1 \leq P_j \leq Q_j \leq H (1 \leq j \leq M)
  • 1 \leq R_j \leq S_j \leq W (1 \leq j \leq M)
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

H W N
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
\vdots
A_N B_N C_N D_N
M
P_1 Q_1 R_1 S_1
P_2 Q_2 R_2 S_2
\vdots
P_M Q_M R_M S_M

出力

M 行出力せよ。

j 行目には、j 個目の質問に対する、領域内の点灯しているマスの個数と、領域内に完全に収まっている島の個数を、この順にスペース区切りで出力せよ。

入力例 1

4 5 3
1 2 1 3
2 4 2 5
3 3 1 5
4
1 4 1 5
1 2 1 3
3 4 1 5
2 3 2 4

出力例 1

11 3
4 0
5 1
1 0

入力例 2

3 3 2
1 3 1 3
1 3 1 3
3
1 3 1 3
1 1 1 1
2 3 2 3

出力例 2

0 0
0 0
0 0

入力例 3

8 10 8
1 3 1 4
2 6 3 8
5 8 1 5
4 4 6 10
1 8 10 10
7 8 7 9
3 5 2 2
6 6 4 10
8
1 8 1 10
1 4 1 5
5 8 1 6
2 7 3 8
1 8 10 10
4 6 6 10
3 3 1 10
7 8 7 9

出力例 3

51 8
13 1
16 1
21 1
6 2
6 3
6 0
6 0

入力例 4

30 40 20
1 10 1 15
5 20 10 30
12 30 5 25
3 3 1 40
1 30 20 20
8 18 18 35
22 30 30 40
15 25 1 8
2 28 38 40
10 12 12 28
6 24 6 24
1 1 1 40
30 30 1 40
1 30 1 1
1 30 40 40
14 17 14 17
19 21 19 21
4 9 26 33
23 27 12 18
11 29 32 37
15
1 30 1 40
1 10 1 15
5 20 10 30
12 30 5 25
1 30 20 20
8 18 18 35
22 30 30 40
15 25 1 8
2 28 38 40
10 12 12 28
1 5 1 5
26 30 36 40
14 17 14 17
19 21 19 21
7 24 7 34

出力例 4

591 48
84 5
170 16
210 15
18 7
70 8
26 4
63 2
46 2
27 4
14 2
6 2
0 0
4 2
231 16

入力例 5

1 1 0
1
1 1 1 1

出力例 5

0 0

Score : 400 pts

Problem Statement

Takahashi has a lighting panel consisting of a grid with H rows and W columns. The cell at the r-th row from the top and the c-th column from the left is called cell (r, c).

Initially, all cells are turned off. Takahashi performs N operations in order.

In the i-th operation, he toggles the state of all cells whose row is between A_i and B_i (inclusive) and whose column is between C_i and D_i (inclusive). That is, cells that are on are turned off, and cells that are off are turned on.

The state of the lighting panel after all operations are completed is called the final state.

In the final state, each connected component of lit cells under the 4-directional (up, down, left, right) adjacency relation (sharing an edge) is called an island. If there are no lit cells at all, the number of islands is 0.

Aoki asks M questions about the final state. Takahashi must answer each question.

In the j-th question, a rectangular region is specified where the row is between P_j and Q_j (inclusive) and the column is between R_j and S_j (inclusive).

For each question, find the following two values:

  1. The number of lit cells within the specified region.
  2. The number of islands in the final state that are completely contained within the specified region.

Here, an island is completely contained within a region if all cells belonging to that island are within the specified region.

Note: Islands are defined with respect to the entire panel in the final state. We do NOT recompute connected components within only the region specified by each question.

Constraints

  • 1 \leq H \leq 1000
  • 1 \leq W \leq 1000
  • 0 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • N + M \leq 10^5
  • M \times H \times W \leq 5 \times 10^7
  • 1 \leq A_i \leq B_i \leq H (1 \leq i \leq N)
  • 1 \leq C_i \leq D_i \leq W (1 \leq i \leq N)
  • 1 \leq P_j \leq Q_j \leq H (1 \leq j \leq M)
  • 1 \leq R_j \leq S_j \leq W (1 \leq j \leq M)
  • All inputs are integers.

Input

The input is given from standard input in the following format:

H W N
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
\vdots
A_N B_N C_N D_N
M
P_1 Q_1 R_1 S_1
P_2 Q_2 R_2 S_2
\vdots
P_M Q_M R_M S_M

Output

Output M lines.

On the j-th line, print the number of lit cells within the region and the number of islands completely contained within the region for the j-th question, separated by a space, in this order.

Sample Input 1

4 5 3
1 2 1 3
2 4 2 5
3 3 1 5
4
1 4 1 5
1 2 1 3
3 4 1 5
2 3 2 4

Sample Output 1

11 3
4 0
5 1
1 0

Sample Input 2

3 3 2
1 3 1 3
1 3 1 3
3
1 3 1 3
1 1 1 1
2 3 2 3

Sample Output 2

0 0
0 0
0 0

Sample Input 3

8 10 8
1 3 1 4
2 6 3 8
5 8 1 5
4 4 6 10
1 8 10 10
7 8 7 9
3 5 2 2
6 6 4 10
8
1 8 1 10
1 4 1 5
5 8 1 6
2 7 3 8
1 8 10 10
4 6 6 10
3 3 1 10
7 8 7 9

Sample Output 3

51 8
13 1
16 1
21 1
6 2
6 3
6 0
6 0

Sample Input 4

30 40 20
1 10 1 15
5 20 10 30
12 30 5 25
3 3 1 40
1 30 20 20
8 18 18 35
22 30 30 40
15 25 1 8
2 28 38 40
10 12 12 28
6 24 6 24
1 1 1 40
30 30 1 40
1 30 1 1
1 30 40 40
14 17 14 17
19 21 19 21
4 9 26 33
23 27 12 18
11 29 32 37
15
1 30 1 40
1 10 1 15
5 20 10 30
12 30 5 25
1 30 20 20
8 18 18 35
22 30 30 40
15 25 1 8
2 28 38 40
10 12 12 28
1 5 1 5
26 30 36 40
14 17 14 17
19 21 19 21
7 24 7 34

Sample Output 4

591 48
84 5
170 16
210 15
18 7
70 8
26 4
63 2
46 2
27 4
14 2
6 2
0 0
4 2
231 16

Sample Input 5

1 1 0
1
1 1 1 1

Sample Output 5

0 0