F-D 与 R_牛客练习赛92

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

许久以前，R 曾问了 D 一个问题：

给定一个 $(n+2)\times (m+2)$ 的网格和两个序列 $a_{1\sim n},b_{1\sim m}$ 。 $a_0=b_0=a_{n+1}=b_{m+1}=10^{18}$ 。 $(i,j)$ 是黑的当且仅当 $a_i+b_j\le x$ ， $(i,j)$ 是白的当且仅当 $a_i+b_j>x$ （其中 $0\le i\le n+1,0\le j\le m+1$ ）。称此时黑色联通块数量与白色联通块数量之差为此时的答案。

但是因为过去太久，D 已经记不得 $a$ 和 $b$ 了。因此现在，他给出 $n,m,K,x$ ，请帮他求出当 $a_1\sim a_n$ 、 $b_1\sim b_m$ 在 $[1,K]$ 取值得到的 $K^{n+m}$ 种以上问题的输入中，答案的和，模 $998244353$ 。

输入描述:

第一行一个正整数 ，为数据组数（）。

接下来  行，每行四个正整数 （）。

输出描述:

输出  行，每行一个非负整数，为本次询问答案模  的值。

示例1

输入

复制

5
2 2 2 2
1 5 3 4
114514 1919810 19260817 23333333
283 439 122 39
402 355 294 933

输出

复制

说明

为了节约篇幅，这里只解释第一组数据。

第一组数据中，一共有  种情况，如下图所示，有九种情况答案为 ，七种情况答案为 ，所以和为 ，对  取模得到 ：