题目描述

给定一个初始值全为 $3$ 的序列 $a_{1\cdots n}$，要求支持以下两种操作：

• 0 l r，询问 $\varphi(\prod_{i=l}^r a_i)$；
• 1 x y，$a_x\gets y$。

在本题中，$n=10^5$，$y$ 的质因子只可能包含 $60$ 个质数。

输入格式

第一行一个整数 $q$ 表示操作次数。

接下来 $q$ 行，每行三个数表示一次操作，格式见题目描述。

输出格式

对于每次询问，输出一行一个整数表示答案对 $19961993$ 取模后的值。

6
0 1 3
1 1 5
0 1 3
1 1 7
0 1 3
0 2 3

18
24
36
6

数据规模与约定

对于 $100\%$ 的数据，$1\leq q\leq 10^5$，$n=10^5$，$y$ 的质因子只可能包含前 $60$ 个质数，$1\leq x\leq n$，$1\leq l\leq r\leq n$。

来源

$2015$ 年国家集训队测试。