给定一个长度为 n 的数列 a ，请回答 q 次询问，每次给定 l, r ，请求出 \prod\limits_{i = l}^r a_i \bmod p 的值，其中 p = 1,145,141 。
第一行是两个整数，依次表示数列长度 n 和询问次数 q 。
第二行有 n 个整数，第 i 个整数表示 a_i 。
接下来 q 行，每行两个整数 l, r ，表示一次询问。
为了避免大量数据输出导致超时，请输出一行一个整数表示所有询问的答案的按位异或和。
5 3 1 2 3 4 5 2 3 3 4 2 4
18
三次询问的答案依次为 6, 12, 24 ，按位异或和为 18 。
对于全部的测试点，保证 1 \leq n, q \leq 10^6 ， 1 \leq l \leq r \leq n ， 1 \leq a_i < p 。