G - Decomposite or Die

問題

整数 $N$ と長さが $N$ の数列 $A$ が与えられます。
どのような $A$ においても、ある数列 $B$ であって、
$A_i = \sum_{d|i} B_d$ を満たす $B$ がただ1つに定まるので、以下のクエリを順に処理してください。

ただし、$d|i$ とは $d$ が $i$ の約数であることを指します。

クエリ

• $T_i=1$ の場合
  • $\sum_{k=x_i}^{y_i} B_k$ を出力してください。
• $T_i = 2$ の場合
  • $A_{x_i}$ を $y_i$ に置き換えてください。

ただし、この問題では $x, y$ は直接は与えられず、前から順にクエリを処理することで得ることができる形式として与えられます。
具体的には、 $H^x, H^y$ が与えられます。

• $Z_1=0$ を満たす数列 $Z$ を考え、 $x_k = H^x_k \oplus Z_k, y_k = H^y_k \oplus Z_k$ の形で $x, y$ を与えます。
• $T_k = 1$ の場合、クエリ $k$ の答えを $u$ として $Z_{k+1} = Z_k \oplus u$ とします。
  • $u$ が負の場合、64bit 整数における2の補数表現 に従ってください。
• $T_k=2$ の場合、 $Z_{k+1}=Z_k$ とします。

制約

• $1\leq N\leq 5\times 10^5$
• $1\leq Q\leq 2\times 10^5$
• $T_i\in \{0, 1\} (1\leq i\leq Q)$
• $-10^9 \leq A_i \leq 10^9$

小課題

• 小課題1 (160点)
  • $Q=1, T_1 = 1$
• 小課題2 (190点)
  • $T_i = 1 ~ (1\leq i\leq Q)$
• 小課題3 (300点)
  • 追加の制約はありません

入力

$N$

$A_1~A_2~\cdots~A_{N-1}~A_N$

$Q$

$T_1~H^x_1~H^y_1$

$T_2~H^x_2~H^y_2$

$\vdots$

$T_{Q-1}~H^x_{Q-1}~H^y_{Q-1}$

$T_Q~H^x_Q~H^y_Q$

出力

1 行で、すべてを改行区切りで出力してください。

入力例1

6
-1 7 -6 1 -8 3
1
1 2 2
Copy

この入力はすべての小課題の制約を満たします。

出力例1

8
Copy

入力例2

6
-8 -6 7 -3 -5 -7
8
1 1 3
1 13 15
1 -3 -7
1 -5 -5
1 -10 -11
1 12 11
1 -15 -9
1 -26 -28
Copy

この入力は小課題 2, 3 の制約を満たします。

入力例3

6
5 9 1 0 2 -4
8
1 2 5
1 -9 -14
1 17 22
1 -27 -28
1 -28 -29
2 16 -18
1 16 17
2 -2 -5
Copy

この入力は小課題 3 の制約を満たします。

出力例3

-12
-25
-12
0
-13
-18
Copy

これらの入力例の実行結果はジャッジ結果として表示されません。