题目描述

有 $n$ 个整数 $x_1,x_2,\cdots,x_n$，其中 $a_i \le x_i \le b_i$。

还有 $m$ 个整数 $y_1,y_2,\cdots,y_m$，其中 $c_j \le y_j \le d_j$。

给定 $n,m,a,b,c,d$，对于所有二元组 $(n',m') \space (1 \le n' \le n, \space 1 \le m' \le m)$，求有多少种给 $x_1,x_2,\cdots,x_{n'},y_1,y_2,\cdots,y_{m'}$ 赋值的方案满足 $\sum_{i=1}^{n'} x_i=\sum_{j=1}^{m'} y_j$，对 $998244353$ 取模。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，其中第 $i$ 行有两个整数 $a_i,b_i$。

接下来 $m$ 行，其中第 $j$ 行有两个整数 $c_j,d_j$。

输出格式

输出 $n$ 行，每行 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数表示 $n'=i,m'=j$ 的答案。

样例

样例输入

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

样例输出

2 0 0
3 4 4

$n'=1,m'=1$ 时，两种方案为：

1. $x_1=1,y_1=1$
2. $x_1=2,y_1=2$

$n'=2,m'=1$ 时，三种方案为：

1. $x_1=1,x_2=2,y_1=3$
2. $x_1=1,x_2=3,y_1=4$
3. $x_1=2,x_2=2,y_1=4$

数据范围与约定

对于所有数据，有：

• $1 \le n,m \le 500$
• $1 \le a_i \le b_i \le 500$
• $1 \le c_j \le d_j \le 500$