给你一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$。

回答 $Q$ 个询问。在第 $i$ 个询问中，给定整数 $L_i, R_i$。令 $B = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$。对于该序列 $B$，解决以下问题并输出答案。

给定一个正整数序列 $B = (B_1, B_2, \dots, B_{|B|})$。一个正整数序列 $C = (C_1, C_2, \dots, C_k)$ 被称为好序列，如果它作为 $B$ 的非空子序列至少出现两次。形式化地，这意味着存在一个正整数 $k$ 和两个下标序列 $(i_1, i_2, \dots, i_k)$ 与 $(j_1, j_2, \dots, j_k)$，满足以下所有条件：

• $1 \le i_1 < i_2 < \dots < i_k \le |B|$
• $1 \le j_1 < j_2 < \dots < j_k \le |B|$
• 对于所有 $p = 1, 2, \dots, k$，有 $B_{i_p} = B_{j_p} = C_p$
• 存在至少一个 $p$ ($1 \le p \le k$) 使得 $i_p \neq j_p$

确定是否存在好序列。如果存在，输出字典序最大的好序列的滚动哈希（rolling hash）值。否则，输出 $-1$。

一个正整数序列 $a = (a_1, a_2, \dots, a_n)$ 的滚动哈希定义为：

$$\left(\sum_{i=1}^{n} a_i 3^{i-1}\right) \bmod 998244353$$

输入格式

输入按以下格式给出：

N Q
A1 A2 ... AN
L1 R1
L2 R2
:
LQ RQ

• 所有输入值均为整数。
• $1 \le N, Q \le 3 \times 10^5$
• $1 \le A_i \le N$ ($1 \le i \le N$)
• $1 \le L_i \le R_i \le N$ ($1 \le i \le Q$)

输出格式

输出 $Q$ 行。对于每个 $i = 1, 2, \dots, Q$，输出序列 $B = (A_{L_i}, A_{L_i+1}, \dots, A_{R_i})$ 对应的答案。

样例

输入样例 1

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

输出样例 1

36
-1
2
11

输入样例 2

5 1
3 2 1 4 1
1 5

输出样例 2

18

输入样例 3

10 10
1 4 5 2 5 3 4 2 5 4
1 10
1 9
2 10
1 8
2 9
3 10
1 7
2 8
3 9
4 10

输出样例 3

56
20
56
35
20
56
17
35
20
17

说明

在第一个样例中，具体情况如下：

• 对于第 $1$ 个询问，$B = (3, 2, 1, 2, 3)$。在所有出现至少两次的非空子序列中，字典序最大的是 $(3, 2, 3)$。产生该子序列的两个有效下标序列为 $(1, 2, 5)$ 和 $(1, 4, 5)$。
• 对于第 $2$ 个询问，$B = (3, 2, 1)$。不存在出现至少两次的非空子序列。
• 对于第 $3$ 个询问，$B = (2, 1, 2)$。在所有出现至少两次的非空子序列中，字典序最大的是 $(2)$。
• 对于第 $4$ 个询问，$B = (2, 1, 2, 3)$。在所有出现至少两次的非空子序列中，字典序最大的是 $(2, 3)$。