题目描述

现有一个长度为 $n$ 的数列 $a$（元素编号为 $1$ 到 $n$），与一个询问常数 $k$，你需要支持以下两种操作。

• $1\ p\ x$：将数列 $a$ 中第 $p$ 个元素修改为 $x$

• $2\ l\ r$：询问 $\prod_{i=l}^r a_i!$ 中有多少个因子 $k$

输入格式

第一行三个正整数 $n$ ($1 \leq n \leq 10^5$)，$m$ ($1 \leq m \leq 10^5$) 和 $k$ ($2 \leq k \leq 10^9$)，用一个空格隔开，表示数列的长度，操作的次数，及给定的询问常数。

随后一行 $n$ 个非负整数 $a_i$ ($0 \leq a_i \leq 10^9$)，用一个空格隔开，第 $i$ 个数 $a_i$ 表示数列 $a$ 中第 $i$ 个元素的初始值。

随后 $m$ 行，每行有三个整数，用一个空格隔开，表示一次操作。格式如下：

• $1\ p\ x$ ($1 \leq p \leq n$, $0 \leq x \leq 10^9$)，表示将数列 $a$ 中第 $p$ 个元素修改为 $x$
• $2\ l\ r$ ($1 \leq l \leq r \leq n$)，表示询问 $\prod_{i=l}^r a_i!$ 中有多少个因子 $k$

保证操作 $2$ 在每组数据中至少出现 $1$ 次。

输出格式

对于每次操作 $2$，输出一行一个非负整数 $y$，表示当前 $\prod_{i=l}^r a_i!$ 中有 $y$ 个因子 $k$。

样例

样例输入

3 3 4
2 2 2
2 1 3
1 2 4
2 1 3

样例输出

1
2

数据范围与提示

正整数 $z$ 中因子 $k$ ($k \geq 2$) 的个数 $c$ 定义为：最大的非负整数 $c$ 使得 $z$ 被 $k^c$ 整除。