该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

魔法数组的奇幻之旅

时间限制：1000ms

空间限制：256MB

题目描述

给定一个数 $A$ 。一个有 $n$ 个元素的数组 $B$ ，每个元素为 $b_i$ 。

保证 $B$ 数组初始时 $b_i$ 各不相同。

有以下两种操作：

$①$ 修改 $:0 \quad l \quad r \quad x$ ，使 $B$ 数组区间 $[\, l$ , $r \,]$ 的每个元素加 $x$ 。

$②$ 查询 $: 1 \quad l \quad r$ ，查询一段区间 $[\, l$ , $r \,]$ 内所有 ( $A$ $mod$ $b_i$ ) 的和。

( $0$ 表示进行操作 $1$ ， $1$ 表示进行操作 $2$ ).

输入格式

第一行输入 $n$ , $m$ , $A$ ( $1≤ n,m,A ≤ 1e5$ ) 表示数组空间大小，操作的次数， $A$ 的值。

接下来一行输入 $n$ 个整数 $b_i$ ( $1≤b_i ≤ 1e5$ ) 表示数组的各个元素值。

接下来 $m$ 行，每行首先输入 $0 \quad l \quad r \quad x$ 进行修改操作或者 $1 \quad l \quad r$ 进行查询操作。( $1\leq l < r \leq n, 1\leq x\leq 1e5$ )

输出格式

输出每次查询操作的结果。

样例输入

4 6 100
10 11 12 13
0 1 4 55
1 1 4
0 1 4 34
1 1 4
0 1 4 1
1 1 4

样例输出

134
201
300