Background

Special for beginners, ^_^

Description

小 $\mathrm{A}$ 爰研究一些奇怪的东西。

小A现在有一个函数满足 $f(1)=1, f\left(p^c\right)=\left\{\begin{array}{ll}p^{114514} \\ p^{229028}(p+1)^{1919810(c-2)}, & c=1 \\ c \geq 2\end{array}\right.$ (p 是质数， $\left.c \geq 1\right)$ ，如果 $\operatorname{gcd}(a, b)=1$ ，那么 $f(a b)=f(a) f(b)$ 。

现在小 $\mathrm{A}$ 有一个长度为 $n$ 的序列，第 $i$ 项是 $a_i$ 。小 $\mathrm{A}$ 有 $q$ 次操作，操作分为两种。

1. $x, y$ 表示把 $a_x$ 改成 $y$
2. $x, y$ 表示查询$f\left(\prod_{i=x}^y a_i\right) \bmod 1019260817$

小 $\mathrm{A}$ 有时候会要求你立马给出答案，因此如果 $t=1$ 请将操作中的 $x, y$ 异或上上一次输出的值。第一次询问之前认为上一次输出的值为 0 。

Format

Input

第一行三个整数 $n, q, t$ 。

接下来一行 $n$ 个整数表示初始的 $a_i$ 。

加下来 $q$ 行每行三个整数 $o p t, x, y$ 表示一次操作。如果 $t=1$ 需要把 $x, y$ 异或上一次询问的答案。

Output

对每个询问输出 $f\left(\prod_{i=x}^y a_i\right) \bmod 1019260817$ 后的结果。

Samples

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

517576382
517576382
985590614
517576382
880018717

大样例

Limitation

对于 $100 \%$ 的数据， $n, q \leq 10^5, 1 \leq a_i \leq 10^6$ 。