题目描述

对于任意两个非负整数，定义如下操作：

1. 写出这两个数的二进制表示；
2. 选择一个二进制位位置；
3. 交换这两个数在该位置上的二进制数字。

给定一个非负整数序列。你可以对序列中任意两个数、任意二进制位执行任意多次上述操作。目标是使序列中所有数的平方和尽可能小。

称这个最小可能平方和为该序列的代价。

现在给定一个长度为 $N$ 的序列，以及 $Q$ 次询问。每次询问给出一个区间 $[L,R]$，要求计算子序列

的代价。

每次询问都是基于原始序列独立计算的，不受其它询问中操作结果的影响。

输入格式

第一行包含两个整数 $N,Q$，分别表示序列长度和询问数量。

第二行包含 $N$ 个非负整数，表示序列 $A_1,A_2,\ldots,A_N$。

接下来 $Q$ 行，每行包含两个整数 $L,R$，表示一次询问的区间端点。

输出格式

输出 $Q$ 行。

每行输出一个整数，表示对应询问区间的最小平方和。

数据范围与约定

• $1\le N\le 100\,000$；
• $1\le Q\le 100\,000$；
• $1\le L\le R\le N$；
• $0\le A_i\le 1\,000\,000$；
• 所有询问相互独立，均基于原始序列计算。

样例

输入

6 2
8 10 5 6 0 5
2 5
1 1

输出

125
64

解释

第一组询问的子序列为 $10,5,6,0$，二进制分别为：

1010, 101, 110, 0

把最低位从第 $2$ 个数交换到第 $4$ 个数，可得到：

1010, 100, 110, 1

再把第 $2$ 位从第 $1$ 个数交换到最后一个数，可得到：

1000, 100, 110, 11

即十进制数 $8,4,6,3$，平方和为

可以证明这是最小值。

第二组询问只有一个数 $8$，无法通过交换改变它，因此答案为 $8^2=64$。