结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

某无线电监测站正在为一座发射台排定一份信号发射计划。发射台按固定顺序依次发出 $n$ 帧信号，编号为 $1$ 到 $n$。每一帧信号都需要设定一个载波频率：第 $i$ 帧的频率 $f_i$ 必须取整数，且落在管理部门为该帧核发的可用频段 $[l_i, r_i]$ 内（含端点）。各帧的可用频段逐帧给定，彼此之间可以不同。

为抑制邻道干扰，监测站对任意相邻两帧的频率差施加限制：对每一对相邻帧 $i$ 与 $i+1$（$1 \le i \le n-1$），给定两个整数 $dl_i, dr_i$，要求这两帧的频率之差的绝对值不得小于 $dl_i$，也不得大于 $dr_i$，即 $dl_i \le |f_{i+1} - f_i| \le dr_i$。这些限制同样逐对给定，各对之间的取值可以不同。

一份完整的信号序列 $(f_1, f_2, \dots, f_n)$ 若同时满足全部帧的频段限制与全部相邻帧的差值限制，则称为一份合法序列。监测站需要掌握合法序列的总数，以便评估频段规划的宽松程度。请计算合法序列的个数。由于该数目可能很大，输出它对 $998244353$ 取模的结果。

输入格式

从文件 signal.in 中读入数据。

• 第一行一个整数 $n$，表示信号的帧数；
• 第二行 $n$ 个整数 $l_1, l_2, \dots, l_n$；
• 第三行 $n$ 个整数 $r_1, r_2, \dots, r_n$；
• 接下来 $n-1$ 行，第 $i$ 行两个整数 $dl_i, dr_i$，表示第 $i$ 帧与第 $i+1$ 帧之间的差值限制。

输出格式

输出到文件 signal.out 中。

输出一行一个整数，表示合法序列的个数对 $998244353$ 取模的结果。

样例

3
1 1 1
3 3 3
0 1
1 2

14

样例 1 解释

考察序列 $(2, 2, 1)$：第一对帧的差值为 $|2-2|=0$，落在 $[0,1]$ 内；第二对帧的差值为 $|1-2|=1$，落在 $[1,2]$ 内，三帧的频率也都在各自频段内，因此它是一份合法序列。

再考察序列 $(1, 3, 2)$：第一对帧的差值为 $|3-1|=2$，大于该对的上限 $1$，因此它不是合法序列。

逐一核对全部取值组合，合法序列共 $14$ 份。

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

146

5
1 1 1 1 1
1 2 2 2 2
1 1
1 1
1 1
1 1

1

样例 3 解释

第 $1$ 帧的频段只含频率 $1$，故 $f_1=1$。此后每一对与前一帧的差值都必须恰好为 $1$，而每帧可用频率只有 $1$ 与 $2$，于是序列被唯一确定为 $(1, 2, 1, 2, 1)$。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 2000$；
• $1 \le l_i \le r_i \le V$，$0 \le dl_i \le dr_i \le V$，其中 $V$ 为值域上界。

各测试点的约束如下：

• 特殊性质 A：每一帧的可用频段至多包含两种频率，即 $r_i - l_i \le 1$。