题目描述

dC 在秒了 BZOJ 上所有的数论题后，感觉萌萌哒，想出了这么一道水题，来拯救日益枯竭的水题资源。

给定一个长度为 $n$ 的正整数序列 $A$，有 $q$ 次询问，每次询问一段区间内所有元素乘积的$\Phi$（$\Phi _n$代表 $1$ 到 $n$ 中与 $n$ 互质的数的个数） 。

由于答案可能很大，所以请对答案 $\bmod 10^6 +777$。 （本题强制在线，所有询问操作的 $l,r$ 都需要 $\oplus$ 上一次询问的答案 $lastans$，初始时，$lastans = 0$。）

输入格式

第一行，两个正整数，$n$，$q$，表示序列的长度和询问的个数。

第二行有 $n$ 个正整数，第 $i$ 个表示 $A_i$。

下面 $q$ 行，每行两个正整数，$l,r$，表示询问 $[l \oplus {lastans},r \oplus {lastans}]$ 内所有元素乘积的$\Phi$。

输出格式

$q$ 行，对于每个询问输出一个整数。

5 10
3 7 10 10 5
3 4
42 44
241 242
14 9
1201 1201
0 6
245 245
7 7
6 1
1203 1203

40
240
12
1200
2
240
4
4
1200
4

数据范围

对于 $100\%$ 的数据，$1\le N\le 50000,1\le Q\le 100000,1\le A_i\le 10^6$。