D - Equal Shopping Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君と青木君がお土産を買いに行きます。お店は N 軒あり、1 から N までの番号が付けられています。i 番目のお店では、L_i 以上 R_i 以下の任意の整数金額で買い物ができます。

買い物計画とは、各お店に対して次のいずれか 1 つの状態を定めたものです。

  • 誰も買い物をしない。
  • 高橋君のみが買い物をし、そのお店で選べる範囲内の整数金額を 1 つ決める。
  • 青木君のみが買い物をし、そのお店で選べる範囲内の整数金額を 1 つ決める。

すなわち、同じお店で 2 人が同時に買い物をすることはできません。

買い物計画が以下の条件をすべて満たすとき、これを均等な買い物計画と呼びます。

  • 高橋君が買い物をするお店がちょうど P 軒である。
  • 青木君が買い物をするお店がちょうど Q 軒である。
  • 高橋君の合計購入金額と青木君の合計購入金額が等しい。

2 つの買い物計画が異なるとは、少なくとも 1 つのお店について以下のいずれかが成り立つことをいいます。

  • そのお店の状態（誰も買い物をしない・高橋君が買い物をする・青木君が買い物をする）が異なる。
  • そのお店で同じ人が買い物をしているが、選んだ購入金額が異なる。

これから M 回、お店の購入金額範囲の変更が順に行われます。j 回目の変更では、X_j 番目のお店で選べる購入金額の範囲が A_j 以上 B_j 以下に置き換わります。変更は累積的に適用されます（過去の変更の結果は保持されたまま、新たな変更が適用されます）。

各変更の直後における、均等な買い物計画の個数を 998244353 で割った余りを求めてください。

制約

  • 1 \leq N \leq 2000
  • 1 \leq P \leq 3
  • 1 \leq Q \leq 3
  • P + Q \leq N
  • 1 \leq M \leq 1000
  • N \times M \leq 2000
  • 1 \leq L_i \leq R_i \leq 20
  • 1 \leq X_j \leq N
  • 1 \leq A_j \leq B_j \leq 20
  • 入力はすべて整数である。

入力

N P Q M
L_1 R_1
L_2 R_2
\vdots
L_N R_N
X_1 A_1 B_1
X_2 A_2 B_2
\vdots
X_M A_M B_M
  • 1 行目には、お店の数 N、高橋君が買い物をするお店の数 P、青木君が買い物をするお店の数 Q、変更の回数 M が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目には、i 番目のお店で初期状態において選べる最小金額 L_i と最大金額 R_i が、スペース区切りで与えられる。
  • 続く M 行のうち j 行目には、j 回目の変更対象のお店の番号 X_j、新しい範囲の下限 A_j、上限 B_j が、スペース区切りで与えられる。この変更により、X_j 番目のお店で選べる購入金額の範囲は A_j 以上 B_j 以下に置き換わる。

出力

M 行出力せよ。j 行目には、j 回目の変更の直後における均等な買い物計画の個数を 998244353 で割った余りを出力せよ。

入力例 1

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

出力例 1

8
2
4

入力例 2

4 1 2 4
1 1
5 5
10 10
20 20
2 1 1
3 1 1
4 1 1
1 20 20

出力例 2

0
0
0
0

入力例 3

10 2 2 8
1 4
2 6
3 3
5 9
1 10
7 12
4 8
10 15
6 20
2 18
5 4 4
1 8 10
9 1 5
3 12 14
7 6 6
10 1 20
2 15 20
6 3 11

出力例 3

58626
58604
33564
40804
26694
28676
27074
32802

入力例 4

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

出力例 4

586595877
942372918
579114555
997055541
62766897
228561487
737641552
569025555
799703660
310240660
505106216
453250441
1642223
794936913
499146615
907897333
840661572
153445870
328766284
813065985
685097138
576425377
624407125
471934618
513206521
723008427
498607051
586470327
544572328
634348848
570879877
724161105
607411726
45822022
104394718
355056473
247078346
800758824
885959660
712159957
229413569
837315444
177045917
213802551
570276218
366827555
172791020
488664059
538446562
541285489

入力例 5

2 1 1 1
20 20
1 1
2 20 20

出力例 5

2

Score : 400 pts

Problem Statement

Takahashi and Aoki are going shopping for souvenirs. There are N shops, numbered from 1 to N. At the i-th shop, one can purchase items for any integer amount between L_i and R_i, inclusive.

A shopping plan assigns exactly one of the following states to each shop:

  • Nobody shops there.
  • Only Takahashi shops there, and he chooses one integer amount within the shop's allowed range.
  • Only Aoki shops there, and he chooses one integer amount within the shop's allowed range.

That is, two people cannot shop at the same shop simultaneously.

A shopping plan is called an equal shopping plan if it satisfies all of the following conditions:

  • Takahashi shops at exactly P shops.
  • Aoki shops at exactly Q shops.
  • Takahashi's total purchase amount equals Aoki's total purchase amount.

Two shopping plans are considered different if there exists at least one shop for which one of the following holds:

  • The state of that shop (nobody shops / Takahashi shops / Aoki shops) differs between the two plans.
  • The same person shops at that shop in both plans, but the chosen purchase amount differs.

From now on, M changes to the shops' price ranges will be applied in order. In the j-th change, the allowed purchase amount range at shop X_j is replaced with A_j to B_j, inclusive. Changes are applied cumulatively (the results of past changes are retained, and new changes are applied on top of them).

After each change, find the number of equal shopping plans modulo 998244353.

Constraints

  • 1 \leq N \leq 2000
  • 1 \leq P \leq 3
  • 1 \leq Q \leq 3
  • P + Q \leq N
  • 1 \leq M \leq 1000
  • N \times M \leq 2000
  • 1 \leq L_i \leq R_i \leq 20
  • 1 \leq X_j \leq N
  • 1 \leq A_j \leq B_j \leq 20
  • All input values are integers.

Input

N P Q M
L_1 R_1
L_2 R_2
\vdots
L_N R_N
X_1 A_1 B_1
X_2 A_2 B_2
\vdots
X_M A_M B_M
  • The first line contains the number of shops N, the number of shops where Takahashi shops P, the number of shops where Aoki shops Q, and the number of changes M, separated by spaces.
  • The following N lines, where the i-th line contains the minimum amount L_i and maximum amount R_i available at the i-th shop in the initial state, separated by spaces.
  • The following M lines, where the j-th line contains the shop number X_j targeted by the j-th change, the new lower bound A_j, and upper bound B_j, separated by spaces. This change replaces the allowed purchase amount range at shop X_j with A_j to B_j, inclusive.

Output

Output M lines. The j-th line should contain the number of equal shopping plans immediately after the j-th change, modulo 998244353.

Sample Input 1

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

Sample Output 1

8
2
4

Sample Input 2

4 1 2 4
1 1
5 5
10 10
20 20
2 1 1
3 1 1
4 1 1
1 20 20

Sample Output 2

0
0
0
0

Sample Input 3

10 2 2 8
1 4
2 6
3 3
5 9
1 10
7 12
4 8
10 15
6 20
2 18
5 4 4
1 8 10
9 1 5
3 12 14
7 6 6
10 1 20
2 15 20
6 3 11

Sample Output 3

58626
58604
33564
40804
26694
28676
27074
32802

Sample Input 4

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

Sample Output 4

586595877
942372918
579114555
997055541
62766897
228561487
737641552
569025555
799703660
310240660
505106216
453250441
1642223
794936913
499146615
907897333
840661572
153445870
328766284
813065985
685097138
576425377
624407125
471934618
513206521
723008427
498607051
586470327
544572328
634348848
570879877
724161105
607411726
45822022
104394718
355056473
247078346
800758824
885959660
712159957
229413569
837315444
177045917
213802551
570276218
366827555
172791020
488664059
538446562
541285489

Sample Input 5

2 1 1 1
20 20
1 1
2 20 20

Sample Output 5

2