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

小C的区间查询

题目描述

小C有一个长为$n$的数组$a$，她会命令小红执行如下两种指令：

● $1$ $x$ $y$:将数组的第$x$位修改为$y$。

● $2$ $l$ $r$:查询在区间$[l,r]$内任取两个元素，其乘积是$495$倍数的方案数。

请你帮帮小红。

这里我们认为 $(a_1,a_2)$ 和 $(a_2,a_1)$ 是一样的，计算答案时只算一次。

输入格式

第一行输入两个整数$n$,$q$($1 \leq n,q \leq 2 \times 10^5$)。

第二行输入$n$个整数 $a_i$($1 \leq a_i \leq 10^9$)。

之后的$q$行，每行输入一条指令$1$ $x$ $y$($1 \leq x \leq n$,$1 \leq y \leq 10^9$)或$2$ $l$ $r$($1 \leq l < r \leq n$)。

特殊的，保证至少会有一次查询指令。

输出格式

对于每次查询指令，新起一行输出一个整数，代表查询结果。

样例

5 3
1 1 1 1 495
2 1 5
1 1 495
2 1 5

4
7

数据范围

前 $30\%$ 的数据，$1\le n,q \le 10^2$

$100\%$ 的数据，见题面。