Traffic

TL : 1s

ML : 1024MB

题目描述

mas在一次社会实践工作中，去到了马路上，承担了维持交通秩序的工作。

mas现在正站在一个十字路口，有一些从南向北的车和一些从西到东的车正朝着这个十字路口方向驶来。

假设这些车都是一个单位时间移动一个单位长度的。

由于拥有高科技，mas预先知道了这些车每辆车的长度，以及距离这个十字路口的距离。

为了维持交通秩序，在每个时刻，mas会让一个方向的车通行，而不让另一方向的车通行(注意，mas可能会保持上一个单位时间的通行状态)。

马路的宽是$W$（即十字路口的中心是一个$W\times W$的正方形），假设马路是足够宽的，即每辆车都在自己的路上行驶，不需要考虑车辆间超车产生的时间花费的情况。

当mas改变车道通行状态的时候，必须保证没有车在十字路口的中心里（即$W\times W$的正方形区域）。

接下来描述一辆车的行驶，假设这辆车长度为$l$，那么在接下来的一个单位时间内，它的移动可以分成几种情况：

1. 如果它还没到十字路口的中心，且距离十字路口还有一段距离，那么向前一个单位长度
2. 如果它刚好在十字路口处（即在正方形的边界上），那么如果接下来的一个单位时间内这条车道是可以通行的，它就会前进一个单位长度，否则停在当前位置
3. 如果不是上面两种情况，它就会前进一个单位长度（显然如果它的车尾也离开了这个正方形区域，那么mas就不再需要关心这辆车了）

接下来，定义“通过十字路口的批次”为每一次mas改变车辆通行状态到下一次改变车辆通行状态之间，通过十字路口的车辆集合。

在指挥交通的过程中，如果存在某个时刻，上个时刻还有车在十字路口中心，而此时刚刚好没有车在十字路口中心，mas就会立刻改变车道的通行状态，让下一个批次的车辆通过。

同时，mas希望每一批次尽量多的让一些车走，具体地说，如果mas在时刻$s$开始让一条车道通行，然后在时刻$t_1$不允许车道通行，然后在时刻$t_2$让另一条车道开始通行，若在$t_1+1$时刻开始不允许通行也可以保证让另一条车道通行的时间是$t_2$，mas就会推迟禁止车道通行的时间$t_1$

然而，mas发现了一个大问题，如果mas改变车道通行状态时做的不好，是会导致一些车的车主心理不平衡，然后投诉mas.

有那么两种情况mas会被投诉：

1. 如果mas的指挥导致某一批次为空，那么所有人都会觉得mas在玩忽职守
2. 有连续两批通过十字路口的车辆是来自同一车道的，这个时候后面一个批次的车辆会觉得mas在搞事情。

现在mas想知道自己有多少种改变车道的方式，使得自己不会被投诉。

两种方式被认为是不同，当且仅当其满足下面两种情况中至少一个：

1. 存在两个同一车道的车$a,b$，使得在一种方式中两者在同一批次通过十字路口，而在另一种方式中两者不在同一批次通过十字路口。
2. 这两个方式的第一批次是不同车道的。

简化题意：

就是mas可以选一些时间点改变车道状态。

改变通行状态有两种，第一种是不让当前通行的方向通行，第二种是让其中一个方向通行。

让其中一个方向通行的时候不能有车在十字路口上面，通行的时间点到不能通行的时间点之间通过的车称为一个批次，一个批次不能为空，两个相邻的批次不能是同一个方向的。

如果一辆车在路口前的时候还没能通行，它就会停下，等待可以通行的时候。

对于一个让当前通行方向不通行的改变通行状态的操作，如果延后这个操作的时间点不会改变这一批次的最晚通过十字路口的时间，mas就会延后这个时间点。

问有多少种不同的通过路口的方案，两个方案不同当且仅当有两辆车在一个方案中在同一个批次，而在另一个方案中不在同一个批次

输入

第一行两个整数$n,m$，分别表示从西到东和从南到北的车的数量

第二行一个整数$W$，表示马路的宽度。

接下来$n$行，其中第$i$行两个整数$x,l$，表示从西到东的第$i$辆车距离十字路口为$x$，这辆车的长度为$l$

接下来$m$行，其中第$i$行两个整数$x,l$，表示从南到北的第$i$辆车距离十字路口为$x$，这辆车的长度为$l$

输出

一行一个整数，表示有多少种改变车道的方式使得自己不会被投诉，由于答案可能很大请将答案对998244353取模后输出。

样例输入1

10 10
2067583
79512261 242548
62774734 2377664
79130739 512231
48268001 1350326
30805356 766211
90373736 2036250
79780264 1097112
87011348 1987562
61153732 845399
83750314 2312730
42115168 1941376
41692409 2400251
89263323 981281
29116943 1179514
10357388 2252337
27812571 699747
90133987 2804500
83848495 2526127
87635327 2068081
67198052 152035

样例输出1

2475

样例输入2

5 5
3
17 3
14 2
14 4
8 5
1 2
5 2
3 4
13 2
7 4
10 5

样例输出2

14

样例解释2

下面的每个区间表示一个批次的对应方向的通行时间区间。 东西方向开始的有八种：

[1,2],[6,7],[14,15],[21,22],[29,30],

[1,2],[6,7],[17,18],[23,24],

[1,2],[7,8],[14,15],[22,23],[30,31],

[1,2],[7,8],[17,18],[23,24],

[1,2],[13,14],[18,19],

[8,9],[16,17],[24,25],

[14,15],[21,22],[29,30],

[17,18],[23,24],

南北方向的有六种：

[5,6],[10,11],[18,19],[26,27],

[5,6],[14,15],[21,22],[29,30],

[5,6],[17,18],[23,24],

[7,8],[14,15],[22,23],[30,31],

[7,8],[17,18],[23,24],

[13,14],[18,19],

数据范围

对于所有数据，保证$n,m\le 500,1\le W,l\le 10^9,0\le x\le 10^9$

1. (30pts) $n,m\le 10$
2. (40pts) $n,m\le 100$
3. (30pts) $n,m\le 500$