题目描述

在 $N$ 维空间中，给定两点 $x=(x_1, x_2, \dots, x_N)$ 和 $y=(y_1, y_2, \dots, y_N)$，它们的曼哈顿距离 $d(x, y)$ 定义如下：

$$d(x, y) = \sum_{i=1}^N |x_i - y_i|$$

此外，所有坐标分量 $x_1, x_2, \dots, x_N$ 都是整数的点 $x=(x_1, x_2, \dots, x_N)$ 被称为格点。

现在给定 $N$ 维空间中的两个格点 $p=(p_1, p_2, \dots, p_N)$ 和 $q=(q_1, q_2, \dots, q_N)$。
请计算满足 $d(p, r) \leq D$ 且 $d(q, r) \leq D$ 的所有可能格点 $r$ 的个数。请将答案对 $998244353$ 取模后输出。

输入格式

输入通过标准输入给出，格式如下：

$N$ $D$ $p_1$ $p_2$ $\dots$ $p_N$ $q_1$ $q_2$ $\dots$ $q_N$

输出格式

请输出答案。

样例 1

输入

1 5
0
3

输出

8

样例 2

输入

3 10
2 6 5
2 1 2

输出

632

样例 3

输入

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

输出

145428186

说明/提示

限制条件

• $1 \leq N \leq 100$
• $0 \leq D \leq 1000$
• $-1000 \leq p_i, q_i \leq 1000$
• 输入的所有值均为整数

样例解释 1

当 $N=1$ 时，是关于一维空间（即数轴）上的点的问题。满足条件的点有 $-2, -1, 0, 1, 2, 3, 4, 5$ 共 $8$ 个。

由 ChatGPT 4.1 翻译