問題文

長さ 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_1,B_2,\dots, B_{|B|}) が与えられます。正整数列 C=(C_1,C_2,\dots, C_k) が B の非空な部分列として 2 回以上現れるとき、形式的には、正整数 k と 2 つの添字の列 (i_1,i_2,\dots ,i_k),(j_1,j_2,\dots ,j_k) が存在して以下の条件をすべて満たすとき、 C を良い列とします。

• 1\le i_1\lt i_2\lt \dots \lt i_k\le |B|
• 1\le j_1\lt j_2\lt \dots \lt 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 が成り立つ。

良い列が存在するかどうか判定し、存在する場合は良い列のうち辞書順で最大のものの ローリングハッシュ を答えてください。ただし、正整数列 a=(a_1,\dots, a_n) の ローリングハッシュ は \displaystyle \left(\sum_{i=1}^{n}a_i 3^{i-1}\right)\bmod 998244353 と定義します。存在しない場合は -1 を答えてください。

制約

• 入力はすべて整数
• 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)

入力例 1

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

出力例 1

36
-1
2
11

1 個目のクエリについて説明します。 B=(3,2,1,2,3) の非空な部分列として 2 回以上現れるもののうち辞書順で最大のものは (3,2,3) です。これを与える 2 つの添字の列としては (1,2,5),(1,4,5) を取ることができます。

2 個目のクエリでは B=(3,2,1) で、非空な部分列として 2 回以上現れるものは存在しません。

3 個目のクエリでは B=(2,1,2) で、非空な部分列として 2 回以上現れるもののうち辞書順で最大のものは (2) です。

4 個目のクエリでは B=(2,1,2,3) で、非空な部分列として 2 回以上現れるもののうち辞書順で最大のものは (2,3) です。

入力例 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