3742: 神奇的变换(第二轮04)

有一天，玥玥在电视上，看到了一种神奇的数字变换。

这种变换是这样的：

首先我们拿到一个正整数，然后对它分别进行以下分解：

1. 分解它的质因数， 数一数其质因数的指数，如果有一个质因数的指数 ≥ 2 ， 写下 0；否则，若有奇数个质因数，写下  −1  ，否则写下  1。

2. 分解其所有正约数，写下其约数个数以及约数总和。

显然，对于每一个数 x，经过变换后将得到  3  个整数。

玥玥试了试，发现他算出了正确的答案，他太开心了！

然而，很不幸，这一切被玥玥的老师看见了。老师总算是找到了给玥玥出题的机 会，于是在第二天，老师给玥玥留了一道《好》题。

老师给玥玥了 n  个正整数，排成一排。老师让玥玥仔细看看这个序列（名字叫 a），然后告诉了玥玥他会问 q  个问题。每一个问题中，老师给出两个数 l, r，让

玥玥算出数字 x  的答案，其中x = Πi(r)=l ai 。

第一行三个整数 n, q, type  ，其中  type   表示询问种类。

第二行 n  个整数，第 i   个整数代表 ai 。

后面 q  行每行两个整数 l′, r′，表示一个询问。

设  last   为上次询问的答案，初始为  0。则询问的区间为  [l  = l ′xor last, r =r ′xor last]，保证  1 ≤ l ≤ r ≤ n  。