该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

你有一个整数序列 $a$，某一天你闲着无聊想对它进行 $m$ 次操作。

操作分为 $4$ 种类型：

• $1\ l\ r : \forall i \in [l,r], a_i \rightarrow \phi(a_i)$
• $2\ l\ r\ x: \forall i \in [l,r], a_i \rightarrow x$
• $3\ l\ r\ x\ y: \forall i \in [l,r], a_i \rightarrow \left( \sum_{i=l}^{r}a_i^x \right) \bmod y$
• $4\ l\ r\ x\ y: 输出 \left( \sum_{i=l}^{r}a_i^x \right) \bmod y$

其中 $\phi(i)$ 指欧拉函数。

Format

Input

第一行为数据组数 $T\ (1 \le T \le 5)$。

对于每组数据，输入四个整数 $n,m,seed,vmax\ (1 \le n,m \le 10^5,1 \le seed,vmax \le 10^7)$。

接下来的数据，按照如下伪代码的方式生成：

def rnd():
    ret = seed 
    seed = (seed * 7 + 13) mod 1000000007 
    return ret 
for i = 1 to n: 
    a[i] = (rnd() mod vmax) + 1 
for i = 1 to m: 
    op = (rnd() mod 4) + 1 
    l = (rnd() mod n) + 1 
    r = (rnd() mod n) + 1 
    if (l > r): 
        swap(l, r) 
    if (op == 2) 
        x = (rnd() mod vmax) + 1 
    if (op == 3) or (op == 4): 
        x = (rnd() mod vmax) + 1 
        y = (rnd() mod vmax) + 1

Output

对于每个类型为 $4$ 的操作，输出一行一个数作为答案。

Samples

1
7 7 7 7

4

Hints

$\phi(i)=\sum_{j=1}^{i-1}[gcd(i,j)=1].\ \phi(0)=0,\ \phi(1)=1,\ \phi(2)=1\dots$

以下是对样例 1 的解释。

Limitation

对于 $20\%$ 的数据，保证 $1 \le n,m \le 1000$。

对于 $100\%$ 的数据，保证 $1 \le n,m \le 10^5,1 \le seed,vmax \le 10^7$。

时空限制：2000ms/256MiB。