数学家的迷题

数学家的迷题

题号：NC222294
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

伟大的数学家费牛于自己的家中过世，桌上的纸笔记录着他生前研究的最后一个问题。

这个问题是这样的，首先给出 $n$ 个数字，第 $i$ 个数字为 $a[i]$ 。接下来进行 $m$ 次操作，每次操作的类型如下：

1：将 $a[id]$ 的值改为 $x$ 。

2：令 $t=a[l]\times a[l+1]\times ...\times a[r-1]\times a[r]$ ，求 $t$ 能被多少个不同的素数整除。

这种问题自然是难不倒费牛，可是他在草稿纸上写着：“我已经想到了一个绝妙的方法，可惜这儿空白太小写不下”。

没办法，现在只能请你代替费牛回答每个 $2$ 类型问题的答案。

输入描述:

第一行两个正整数 $n$ , $m$ ，其中 $n \leq 5\times 10^{4}$ , $m\leq 5 \times 10^{4}$ 。

第二行 $n$ 个正整数 $a[i]$ ， $a[i] \leq 10^{5}$ 。

接下来 $m$ 行，每行第一个数字 $op$ 表示操作类型， $1\leq op \leq 2$ 。

若 $op$ 为 $1$ ，输入正整数 $id$ 与 $x$ ，其中 $id\leq n$ , $x\leq 10^{5}$ 。

若 $op$ 为 $2$ ，输入正整数 $l$ 与 $r$ ，其中 $l\leq r\leq n$ 。

输出描述:

输出每个 $2$ 类型问题的答案。

示例1

输入

复制

输出

复制

2
3