给定 $n,m,A$，维护由序列构成的序列 $a_1,\cdots,a_n$，初始 $a_i$ 包含一个元素 $A$；

共 $m$ 次操作：

• 修改操作：给定 $l,r,x$，对 $l \le i \le r$，在序列 $a-i$ 前面插入元素 $x$；

• 查询操作：给定 $l, r$，查询 $\sum_{i=l}^r F(a_i, A)$；

其中 $F((x_1,\cdots,x_n), 0) = 0$；

对 $k > 0$，$F((x_1,\cdots,x_n), k) = F\left((x_2, \cdots, x_n), \left\lfloor \frac{k}{x_1}\right\rfloor\right) + 1$ 。

输入格式

第一行三个整数 $n, m, A￥；

接下来 $m$ 行，每行 1 l r x 表示一个修改操作，或 2 l r 表示一个查询操作；

输出格式

对每个查询操作，输出一行，表示答案。

样例数据

样例 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

样例 1 输出

4
5
2
3
3
4
2
5
2
2
8

样例 2 ~ 5

见下发文件。

子任务

注意，使用捆绑测试。

对于 $25\%$ 的数据，满足 $n,m \le 100$。

对于 $50\%$ 的数据，满足 $n,m \le 10^5$。

对于另外 $25\%$ 的数据，满足 $x \ne 1$。

对于 $100\%$ 的数据，满足 $1 \le n,m \le 5 \times 10^5$，$1 \le A, x \le 10^9$，$1 \le l \le r \le n$。