5870.能量共鸣

## 题目描述

魔法师小明在研究一排 $n$ 个魔法水晶的能量流动。每个水晶都有一个初始的能量值。

他发现，如果一段连续的水晶区间 $[i, j]$ 的能量总和是“魔法常数” $k$ 的倍数，这个区间就会产生一次“能量共鸣”。

现在，小明需要处理 $m$ 个事件：

1.  **更换水晶**：格式为 `1 x y`。小明将第 $x$ 个位置的水晶更换为一个能量值为 $y$ 的新水晶。
2.  **查询共鸣**：格式为 `2 l r`。小明想知道，在第 $l$ 个到第 $r$ 个水晶之间（包含两端），总共能产生多少次“能量共鸣”？换句话说，需要你计算有多少对 $(i, j)$ 满足 $l \le i \le j \le r$ 且区间 $[i, j]$ 的能量和是 $k$ 的倍数。

## 输入格式

第一行包含三个整数 $n, m, k$，分别表示水晶的数量，事件的次数和魔法常数。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个水晶的初始能量值。
接下来 $m$ 行，每行包含一个事件，格式如题目描述所示。

## 输出格式

对于每个“查询共鸣”事件，输出一行一个整数，代表答案。

## 样例 #1

### 样例输入 #1

```
5 4 3
1 2 3 1 2
2 1 5
1 3 5
2 2 5
2 1 2
```

### 样例输出 #1

```
7
2
1
```

## 样例 #2
### 样例输入 #2

```
8 10 5
3 7 5 1 9 2 4 6
2 1 8
1 2 3
2 1 8
2 3 6
1 8 4
2 7 8
2 1 1
1 1 10
2 1 3
2 5 8
```

### 样例输出 #2

```
8
7
3
0
0
2
2
```

## 提示

#### 数据范围与约定

*   对于 $20\%$ 的数据，满足 $1 \le n, m \le 100$。
*   对于另外 $20\%$ 的数据，满足 $1 \le k \le 2$。
*   对于另外 $20\%$ 的数据，保证所有操作均为“查询共鸣”事件（即不存在类型为 `1` 的操作）。
*   对于 $100\%$ 的数据，满足 $1 \le n, m \le 10^5$，$1 \le k \le 10$，$1 \le x \le n$，$0 \le a_i, y \le 10^9$，$1 \le l \le r \le n$。