小重有一个长度为 $n$ 的序列 $a_1, \dots, a_n$，小庆对小重的序列颇感好奇，于是进行了 $q$ 次询问。

每次询问时，小庆会选定一个下标区间 $\{l,l+1, \dots, r\}$ ($1\le l\le r\le n$)，然后让小重去枚举每一个 $\{l, l+1, \dots, r\}$ 的子集 $S$，数一数有多少个子集 $S$ 满足 \begin{equation} |\{a_i \mid i \in S\}| = |\{a_i \mid i \in \{l,l+1,\dots,r\}\setminus S \}| \end{equation} 即，在 $S$ 里出现的不同元素组成的不可重集合与在区间里 $S$ 外出现的不同元素组成的不可重集合大小一致。

小庆问了太多次问题之后，小重不堪重负，于是请求你的帮助。由于每次询问的答案可能很大，小庆只想知道答案对 $2^{64}$ 取模之后得到的结果。

输入格式

第一行 $2$ 个正整数 $n,q$。

第二行 $n$ 个正整数 $a_1, \dots, a_n$。

接下来 $q$ 行，每行 $2$ 个正整数 $l,r$，表示一组询问。

输出格式

共 $q$ 行 $q$ 个非负整数表示答案。

样例一

input

12 5
1 1 4 5 1 4 6 6 6 6 6 6
4 7
1 4
2 6
1 9
7 12

output

6
4
8
126
62

explaination

在第一个样例的第一次询问中，合法的集合 $S$ 有 $\{4,5\},\{4,6\},\{4,7\},\{5,6\},\{5,7\},\{6,7\}$。

样例二/三/四/五

见样例下载，它们分别对应子任务 2,3,4,5。

限制与约定

对于全部数据，保证 $1\le n\le 3\times 10^5,1\le q\le 10^5,1\le a_i\le n$。

时间限制：$2\texttt{s}$

空间限制：$1\texttt{GB}$