顾名思义，这是一道既和数据结构有关，也和数论有关的题目。
九条可怜有一个 $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分）：无特殊限制。