顾名思义，这是一道既和数据结构有关，也和数论有关的题目。

九条可怜有一个 $n\times m$ 的表格，初始的时候所有数字的值都是 $0$。

接着，可怜用了 $q_1$ 次操作来将表格初始化。第 $i$ 次操作用四个整数 $s_i,l_i,r_i,x_i$ 描述：在这次操作中，可怜会把所有满足 $a$ 和 $s_i$ 互质，$b \in [l_i,r_i]$ 的格子 $(a,b)$ 加上 $x_i$。

然后，可怜提出了 $q_2$ 次询问。第 $i$ 次询问用三个整数 $s_i,l_i,r_i$ 描述：可怜希望知道所有满足 $a$ 和 $s_i$ 互质，$b \in [l_i,r_i]$ 的格子 $(a,b)$ 上的数的和。

为了降低题目的难度，可怜保证所有的 $s_i$ 都是从 $[1,n]$ 中均匀独立地随机的。

输入格式

第一行输入四个整数 $n,m,q_1,q_2(1 \leq n,m,q_2 \leq 5 \times 10^4, 1 \leq q_1 \leq 10^5)$。

接下来 $q_1$ 行每行描述一个初始化操作，第 $i$ 行包含四个整数 $s_i,l_i,r_i,x_i(1 \leq s_i \leq n, 1 \leq l_i,r_i \leq m, 1 \leq x_i \leq 10^9)$。

接下来 $q_2$ 行每行描述一个询问操作，第 $i$ 行包含三个整数 $s_i,l_i,r_i(1 \leq s_i \leq n, 1\leq l_i,r_i \leq m)$。

输入数据保证所有的 $s_i$ 都是从 $[1,n]$ 的所有整数中等概率随机的。

输出格式

对于每次询问，输出一行一个整数，表示答案。答案可能很大，你只需要输出对 $2^{32}$ 取模后的结果。

样例数据

样例输入

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

样例输出

42
46
55
21

子任务

Subtask1（6分）：$n,m,q_1,q_2 \leq 100$。

Subtask2（13分）：$n,m,q_1,q_2 \leq 5000$。

Subtask3 (19分)：$m=1$

Subtask4（22分）：$n,m,q_1,q_2 \leq 30000$。

Subtask5（30分）：无特殊限制。