在学习了 Elegia 关于如何使用生成函数技巧解决组合计数问题的思路后，Little Cyan Fish 想要解决以下问题。

Little Cyan Fish 有 $n+m$ 个整数，分别记为 $x_1, x_2, \dots, x_n$ 和 $y_1, y_2, \dots, y_m$。Little Cyan Fish 已知：

• 对于所有 $1 \le i \le n$，满足 $l_i^{(x)} \le x_i \le r_i^{(x)}$。
• 对于所有 $1 \le j \le m$，满足 $l_j^{(y)} \le y_j \le r_j^{(y)}$。

Little Cyan Fish 尚未确定 $x_i$ 和 $y_j$ 的具体取值。他想知道，对于任意一对整数 $(a, b)$ ($1 \le a \le n, 1 \le b \le m$)，有多少种方式可以设定 $x_i$ ($1 \le i \le a$) 和 $y_j$ ($1 \le j \le b$) 的值，使得 $\sum_{i=1}^a x_i = \sum_{j=1}^b y_j$。由于结果可能非常大，你只需要输出其对 $998\,244\,353$ 取模后的结果。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 500$)。

接下来的 $n$ 行描述数组 $x_1, x_2, \dots, x_n$ 的约束。其中第 $i$ 行包含两个整数 $l_i^{(x)}$ 和 $r_i^{(x)}$ ($1 \le l_i^{(x)} \le r_i^{(x)} \le 500$)，表示一个约束。

接下来的 $m$ 行描述数组 $y_1, y_2, \dots, y_m$ 的约束。其中第 $j$ 行包含两个整数 $l_j^{(y)}$ 和 $r_j^{(y)}$ ($1 \le l_j^{(y)} \le r_j^{(y)} \le 500$)，表示一个约束。

输出格式

输出 $n$ 行，每行包含 $m$ 个整数。第 $a$ 行的第 $b$ 个整数表示设定 $x_1, x_2, \dots, x_a$ 和 $y_1, y_2, \dots, y_b$ 的值使得 $\sum_{i=1}^a x_i = \sum_{j=1}^b y_j$ 的方案数，对 $998\,244\,353$ 取模。

样例

样例输入 1

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

样例输出 1

2 0 0
3 4 4

说明

对于 $a = 1$ 且 $b = 1$，有两种设定值的方式，如下所示：

对于 $a = 2$ 且 $b = 1$，有三种设定值的方式，如下所示：

对于 $a = 2$ 且 $b = 2$，有四种设定值的方式，如下所示：

对于 $a = 2$ 且 $b = 3$，有四种设定值的方式，如下所示：