Equal Sums
Little Cyan Fish 学习了使用生成函数解决组合计数问题的方法,现在想解决下面的问题。
有两组尚未确定取值的整数,分别为 x1,…,xn 和 y1,…,ym。它们需要满足
li(x)≤xi≤ri(x)(1≤i≤n),
lj(y)≤yj≤rj(y)(1≤j≤m).
对于每一对整数 a,b(1≤a≤n、1≤b≤m),请计算给 x1,…,xa 和 y1,…,yb 赋值,使得
i=1∑axi=j=1∑byj
的方案数。当前两个前缀以外的变量不参与这一对 (a,b) 的计数。答案对 998244353 取模。
输入格式
第一行包含两个整数 n,m,满足 1≤n,m≤500。
接下来 n 行,每行两个整数 li(x),ri(x),满足 1≤li(x)≤ri(x)≤500。
再接下来 m 行,每行两个整数 lj(y),rj(y),满足 1≤lj(y)≤rj(y)≤500。
本题输入只有一个测试用例,没有测试用例数 T。
输出格式
输出 n 行,每行 m 个整数。第 a 行第 b 个整数表示所求的两个前缀赋值方案数模 998244353 的结果。
原样例
输入:
2 3
1 2
2 3
1 4
2 2
1 3
输出:
2 0 0
3 4 4
原样例说明
当 a=1,b=1 时有两种方案:
当 a=2,b=1 时有三种方案:
| x1 |
x2 |
y1 |
| 1 |
2 |
3 |
| 3 |
4 |
| 2 |
当 a=2,b=2 时有四种方案:
| x1 |
x2 |
y1 |
y2 |
| 1 |
2 |
1 |
2 |
| 3 |
2 |
| 2 |
2 |
| 3 |
当 a=2,b=3 时有四种方案:
| x1 |
x2 |
y1 |
y2 |
y3 |
| 1 |
3 |
1 |
2 |
1 |
| 2 |
2 |
| 3 |
2 |
| 2 |
1 |