F. Nim
时间限制：6 秒
内存限制：512 MB

回忆游戏“Nim”的规则。有 $n$ 堆石子，第 $i$ 堆初始有若干石子。两名玩家轮流选择非空的一堆，并从中移除任意正数（严格大于 $0$）的石子。无法移动的玩家输掉游戏。

给你一个由 $n$ 个整数组成的数组 $a$。Artem 和 Ruslan 决定在这个数组的区间上玩 Nim 游戏。有 $q$ 轮游戏，每轮由区间 $(l_i, r_i)$ 定义，其中元素 $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$ 代表各堆的石子数。

在游戏开始前，Ruslan 可以从所选区间中移除任意数量的堆。但必须至少保留一堆，因此在一轮中，他最多可以移除 $(r_i - l_i)$ 堆。他也可以不移除任何堆（移除 $0$ 堆）。移除结束后，游戏在区间内剩余的堆上进行。

所有轮次是独立的：某一轮中的更改不会影响原数组或其他轮次。

Ruslan 希望移除尽可能多的堆，使得 Artem（总是先手）输掉游戏。

对于每一轮，求出：

• Ruslan 最多可以移除的堆数；
• 在达到最大移除堆数的条件下，有多少种移除方式。

如果移除方式不同当且仅当存在某个下标 $i$，在其中一种方式中被移除而在另一种中未被移除。由于方式数可能很大，输出结果对 $998244353$ 取模。

如果 Ruslan 无法让 Artem 在这一轮输掉，则输出 -1。

输入
第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^5$）——数组长度和询问的区间数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 50$）——初始数组的元素。

接下来的 $q$ 行，每行包含两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$）——第 $i$ 轮游戏的区间边界。

输出
对于每一轮：

• 如果 Ruslan 能赢，输出两个整数——最多可以移除的堆数，以及达到这个最大值的方式数（对 $998244353$ 取模）；
• 否则输出 -1。

样例
输入

9 5
0 1 2 1 3 4 5 6 0
1 5
2 5
3 5
4 5
1 9

输出

4 1
2 1
0 1
-1
8 2