As the name suggests, this is a problem involving both data structures and number theory.

Kanan has an $n \times m$ grid, where all numbers are initially $0$.

Then, Kanan performs $q_1$ operations to initialize the grid. The $i$-th operation is described by four integers $s_i, l_i, r_i, x_i$: in this operation, Kanan adds $x_i$ to all cells $(a, b)$ such that $a$ and $s_i$ are coprime and $b \in [l_i, r_i]$.

Afterward, Kanan makes $q_2$ queries. The $i$-th query is described by three integers $s_i, l_i, r_i$: Kanan wants to know the sum of the numbers in all cells $(a, b)$ such that $a$ and $s_i$ are coprime and $b \in [l_i, r_i]$.

To reduce the difficulty of the problem, it is guaranteed that all $s_i$ are chosen uniformly and independently at random from $[1, n]$.

Input

The first line contains four integers $n, m, q_1, q_2$ ($1 \leq n, m, q_2 \leq 5 \times 10^4$, $1 \leq q_1 \leq 10^5$).

The next $q_1$ lines each describe an initialization operation, with the $i$-th line containing four integers $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$).

The next $q_2$ lines each describe a query operation, with the $i$-th line containing three integers $s_i, l_i, r_i$ ($1 \leq s_i \leq n$, $1 \leq l_i, r_i \leq m$).

The input data guarantees that all $s_i$ are chosen with equal probability from all integers in $[1, n]$.

Output

For each query, output a single integer on a new line representing the answer. The answer may be very large; you only need to output the result modulo $2^{32}$.

Examples

Input 1

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

Output 1

42
46
55
21

Subtasks

Subtask 1 (6 points): $n, m, q_1, q_2 \leq 100$.

Subtask 2 (13 points): $n, m, q_1, q_2 \leq 5000$.

Subtask 3 (19 points): $m = 1$.

Subtask 4 (22 points): $n, m, q_1, q_2 \leq 30000$.

Subtask 5 (30 points): No additional constraints.