Given $n, m, A$, maintain a sequence of sequences $a_1, \dots, a_n$, where initially each $a_i$ contains a single element $A$.

There are $m$ operations in total:

• Modification: Given $l, r, x$, for all $l \le i \le r$, insert the element $x$ at the beginning of the sequence $a_i$.
• Query: Given $l, r$, query $\sum_{i=l}^r F(a_i, A)$.

Where $F((x_1, \dots, x_n), 0) = 0$;

For $k > 0$, $F((x_1, \dots, x_n), k) = F\left((x_2, \dots, x_n), \left\lfloor \frac{k}{x_1} \right\rfloor\right) + 1$.

Input

The first line contains three integers $n, m, A$.

The next $m$ lines each contain either 1 l r x representing a modification operation, or 2 l r representing a query operation.

Output

For each query operation, output one line representing the answer.

Examples

Input 1

5 20 10
1 4 4 166348285
2 2 5
2 1 5
1 1 2 10
1 4 4 3
1 4 5 6
2 5 5
1 5 5 1
1 2 3 1
2 5 5
2 5 5
2 3 4
2 3 3
2 4 5
2 4 4
1 2 5 5
1 5 5 9
1 1 4 5
2 5 5
2 1 4

Output 1

4
5
2
3
3
4
2
5
2
2
8

Examples 2 ~ 5

See the provided files.

Subtasks

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078

Note that bundled testing is used.

For $25\%$ of the data, $n, m \le 100$.

For $50\%$ of the data, $n, m \le 10^5$.

For another $25\%$ of the data, $x \ne 1$.

For $100\%$ of the data, $1 \le n, m \le 5 \times 10^5$, $1 \le A, x \le 10^9$, $1 \le l \le r \le n$.