Sequence Insertion and Recursive Query

You are given three integers n, m and A. We maintain n sequences a1, a2, …, an. Initially, for each 1 ≤ i ≤ n, the sequence ai contains a single element A+1.

Then, you are given m operations. There are two types of operations:

• Update Operation: Given four integers 1 l r x. For every i such that l ≤ i ≤ r, insert the integer x at the beginning of sequence ai.
• Query Operation: Given three integers 2 l r. Compute and output the value $$\sum_{i=l}^{r} F(a_i, A),$$ where the function F is defined recursively as follows:</p>

  $$ \begin{aligned} F((x_1, x_2, \dots, x_t), 0)&=0,\\ F((x_1, x_2, \dots, x_t), k)&=F((x_2, \dots, x_t), \lfloor \frac{k}{x_1} \rfloor)+1 \quad \text{for } k>0. \end{aligned} $$

  For each sequence, you process the elements from the beginning until the current value of k becomes 0.

Note: It is guaranteed that the sequences are maintained properly and every query operation should output the sum of the computed values for all sequences from index l to r.

inputFormat

The first line contains three integers n m A separated by spaces.

The following m lines each represent an operation. An operation is given in one of the two formats:

• 1 l r x: An update operation which prepends x to every sequence a_i for l ≤ i ≤ r.
• 2 l r: A query operation. For each query, output the sum of F(a_i, A) for l ≤ i ≤ r.

All numbers are separated by spaces.

outputFormat

For each query operation in the input, print a line containing the corresponding answer.

sample

3 5 10
2 1 3
1 1 2 5
2 1 3
1 2 3 2
2 2 3

3
5
5