#P18513. Equal Sums

Equal Sums

Equal Sums

Little Cyan Fish 学习了使用生成函数解决组合计数问题的方法,现在想解决下面的问题。

有两组尚未确定取值的整数,分别为 x1,…,xnx_1,\ldots,x_n 和 y1,…,ymy_1,\ldots,y_m。它们需要满足

li(x)≤xi≤ri(x)(1≤i≤n),l_i^{(x)}\le x_i\le r_i^{(x)}\quad(1\le i\le n), lj(y)≤yj≤rj(y)(1≤j≤m).l_j^{(y)}\le y_j\le r_j^{(y)}\quad(1\le j\le m).

对于每一对整数 a,ba,b(1≤a≤n1\le a\le n、1≤b≤m1\le b\le m),请计算给 x1,…,xax_1,\ldots,x_a 和 y1,…,yby_1,\ldots,y_b 赋值,使得

∑i=1axi=∑j=1byj\sum_{i=1}^{a}x_i=\sum_{j=1}^{b}y_j

的方案数。当前两个前缀以外的变量不参与这一对 (a,b)(a,b) 的计数。答案对 998244353998244353 取模。

输入格式

第一行包含两个整数 n,mn,m,满足 1≤n,m≤5001\le n,m\le500。

接下来 nn 行,每行两个整数 li(x),ri(x)l_i^{(x)},r_i^{(x)},满足 1≤li(x)≤ri(x)≤5001\le l_i^{(x)}\le r_i^{(x)}\le500。

再接下来 mm 行,每行两个整数 lj(y),rj(y)l_j^{(y)},r_j^{(y)},满足 1≤lj(y)≤rj(y)≤5001\le l_j^{(y)}\le r_j^{(y)}\le500。

本题输入只有一个测试用例,没有测试用例数 TT。

输出格式

输出 nn 行,每行 mm 个整数。第 aa 行第 bb 个整数表示所求的两个前缀赋值方案数模 998244353998244353 的结果。

原样例

输入:

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

输出:

2 0 0
3 4 4

原样例说明

当 a=1,b=1a=1,b=1 时有两种方案:

x1x_1 y1y_1
1
2

当 a=2,b=1a=2,b=1 时有三种方案:

x1x_1 x2x_2 y1y_1
1 2 3
3 4
2

当 a=2,b=2a=2,b=2 时有四种方案:

x1x_1 x2x_2 y1y_1 y2y_2
1 2 1 2
3 2
2 2
3

当 a=2,b=3a=2,b=3 时有四种方案:

x1x_1 x2x_2 y1y_1 y2y_2 y3y_3
1 3 1 2 1
2 2
3 2
2 1