数列前缀和 2(Prefix Product Queries)

题目描述

给定一个长度为 $n$ 的数列 $a$，请回答 $q$ 次询问，每次给定 $l, r$，请求出 $\prod\limits_{i = l}^r a_i \bmod p$ 的值，其中 $p = 1054^2 + 185^2$。容易证明这是一个质数。

输入格式

第一行是两个整数，依次表示数列长度 $n$ 和询问次数 $q$。
第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。
接下来 $q$ 行，每行两个整数 $l, r$，表示一次询问。

输出格式

为了避免大量数据输出导致超时，请输出一行一个整数表示所有询问的答案的按位异或和。

样例输入 #1

5 3
1 2 3 4 5
2 3
3 4
2 4

样例输出 #1

18

数据范围

样例 1 解释

三次询问的答案依次为 $6, 12, 24$，按位异或和为 $18$。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n,q \leq 10^3$。
• 对于 $60\%$ 的数据，保证 $n, q \leq 10^5$。

对于全部的测试点，保证 $1 \leq n, q \leq 10^6$，$1 \leq l \leq r \leq n$，$1 \leq a_i < p$。

提示

你可以在这里学习如何线性求逆元，请尽可能做到 $O(1)$ 回答单次询问。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度（CF Rating）：1400。

测试点分布

出处：原题链接