E-牵一半_牛客练习赛102

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

这生命无常又孤单
你的存在是我唯一依赖
失去的梦伤过的心
该怎么去补完
有些困惑这一生我们都不知道答案
我错过太多美满
留过太多遗憾
而在这一次我想要抓住

那份期盼

————《牵一半》阿良良木健（侵删）

定义函数 $f(x,p)$ （p为质数）为，当 $x$ 不是 $p$ 的倍数时， $f(x,p)$ 为 $x$ 在模 $p$ 意义下的乘法逆元(即 $f(x,p) 为最小的y使得 xy \equiv 1\pmod p$ )， $x$ 是 $p$ 的倍数时 $f(x,p) = 0$ 。

阿良良木健现在有一个序列长度为 $n$ 的序列 $a_i$ ，和 $m$ 个操作。

操作有两种：

$1\text{ } x \text{ } y$ 将 $a_x$ 更改为 $y$

$2\text{ }\ l\text{ } r\text{ } p$ ，求 $max(f(a_i,p))$ 其中 $l \le i \le r$

保证数据随机

随机方式如下：

$a_i,x,y$ 在 $[1,n]$ 中的正整数中等概率随机生成

$opt(指操作序号)$ 在 ${1,2}$ 中随机生成

$l,r$ 在 $[1,n]$ 中的正整数中等概率随机生成生成后若 $l > r$ 则交换 $l,r$

$p$ 在 $[1,n]$ 的质数中等概率随机生成一个

输入描述:

第一行，两个正整数 。

后面一行，每行  个数，表示序列 

后面  行，每行三个或四个数，表示一次操作

输出描述:

对于每个操作2，输出一行一个非负整数，表示这一询问的答案。

示例1

输入

复制

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

输出

复制