题目背景

题目描述

happydef正在切题。

每道题都是这样的：

已知函数\(f(x)=\cdots\)。

输入\(n\)，\(m\)，求

\[\sum_{i=1}^{n}\sum_{j=1}^{m}f(\gcd(i,j)) \bmod 998244353\]

现在happydef已经得到了\(f(x)\)的前\(\min(n,m)\)项，定义为\(a\)数组，她希望你能够帮她写一份代码，使得只要给出\(a\),就能解决这个问题。

输入格式

本题有多组数据。

由于本题的数据范围较大，测试点的\(a_i\)以及每组数据的值将在程序内生成。

第一行输入六个数\(n_0,m_0,n_1,m_1,T,\text{seed}\)。

你可以使用如下方式生成\(a\)数组:

定义函数
\[\operatorname{rand}()=((\text{lastret} \times 233+2333)\bmod 998244353)\]
其中\(\text{lastret}\)为上一次的返回值，初始值为\(\text{seed}\)。
则
\[a_i=(\operatorname{rand}() \times \operatorname{rand}()\bmod 998244353)+1\]

提示：必须恰好生成\(\min(n_1,m_1)\)项，否则后面数据会有误。

在生成\(a_i\)之后，每个数据点依次生成方法：
\[n=(\operatorname{rand}() \times \operatorname{rand}()\times \text{lastans} \bmod (n_1-n_0+1))+n_0\]
\[m=(\operatorname{rand}() \times \operatorname{rand}()\times \text{lastans}\bmod (m_1-m_0+1))+m_0\]
其中，\(lastans\)表示上次询问答案，初始值为\(1\)。
注意，此处不需要把seed归位。

输出格式

输出\(T\)行，每行一个整数, 表示答案。

输入输出样例

输入 #1

1 1 4 5 1 4

输出 #1

874978019

样例解释

如果操作正确,生成的数据应为

494960965
953256032
630594112
663796310

\(n,m\)依次为：
```
2 5

```

数据范围

本题采用捆绑测试。

对于每一个Subtask，只有通过其中所有的测试点后才能拿到该Subtask的分数。

Subtask 1:（20 points）\(9\times 10^2 \leq n_0\leq n_1\leq 10^3\)，\(9\times 10^2 \leq m_0\leq m_1\leq 10^3\),时限\(100ms\)

Subtask 2:（20 points）\(9\times 10^4 \leq n_0\leq n_1\leq 10^5\)，\(9\times 10^4 \leq m_0\leq m_1\leq 10^5\),时限\(100ms\)

Subtask 3:（20 points）\(9\times 10^5 \leq n_0\leq n_1\leq 10^6\)，\(9\times 10^5 \leq m_0\leq m_1\leq 10^6\),时限\(100ms\)

Subtask 4:（40 points）\(9\times 10^6 \leq n_0\leq n_1\leq 10^7\)，\(9\times 10^6 \leq m_0\leq m_1\leq 10^7\)，时限\(400ms\)

对于\(100\%\)的数据，\(T\leq 10,\text{seed}\leq 998244353\)。

---

Idea:happydef Solution:happydef std:happydef Data:happydef

来自出题人的友好提醒：如果被卡常请剪枝&多交几次，评测机不稳定

请注意常数因子带来的程序效率上的影响。