题目描述

给定一个长度为 n 的非负整数序列 a1,a2,...,an。有 q 次询问，每次询问给定 l,r。

对区间 [l,r] 中的所有数，将它们划分成若干个非空组。每个数必须恰好属于一个组，组内元素不要求在原序列中连续。一个组的权值定义为组内所有数的按位异或和。

若一次划分得到的各组权值为 b1,b2,...,bk，则这次划分的价值为 b1×b2×...×bk。

请对每次询问求出可能的最大价值。由于答案可能很大，只需要输出最大价值对 998244353 取模后的结果。

输入格式

第一行两个整数 n,q。

第二行 n 个整数 a1,a2,...,an。

接下来 q 行，每行两个整数 l,r，表示一次询问。

输出格式

输出 q 行，第 i 行包含一个整数，表示第 i 次询问的答案。

样例 1

输入：

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

输出：

9
6
12

样例 2

输入：

4 2
0 0 0 0
1 1
1 4

输出：

0
0

数据范围

对于所有测试数据，1≤n,q≤5×10^5，0≤ai<2^30，1≤l≤r≤n。

本题采用捆绑测试，包含多种子任务。

样例解释

样例 1 第一次询问中，区间为 1,2,3，可划分为 {1,2} 和 {3}，价值为 (1⊕2)×3=3×3=9。第二次区间为 2,3,0，可划分为 {2,0} 和 {3}，价值为 2×3=6。第三次区间为 3,0,4，可划分为 {3,0} 和 {4}，价值为 3×4=12。