Problem Description

Given $n, m, A$, maintain a sequence of sequences $a_1, \dots, a_n$. Initially, each $a_i$ contains one element $A + 1$.

There are $m$ operations in total:

• Modification: given $l, r, x$, for all $l \le i \le r$, insert the element $x$ to the front of sequence $a_i$.
• Query: given $l, r$, query $\sum\limits_{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((x_2, \dots, x_n), \lfloor \frac{k}{x_1} \rfloor) + 1$.

Input Format

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

The next $m$ lines each describe an operation: $1, l, r, x$ denotes a modification operation, and $2, l, r$ denotes a query operation.

Output Format

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

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

4
5
2
3
3
4
2
5
2
2
8

Hint

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

Constraints: for $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^5$, $1 \le A, x \le 10^9$, and $1 \le l \le r \le n$.

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

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

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

For the remaining $25\%$ of the testdata, there are no special restrictions.

Translated by ChatGPT 5