5739: Inna and Binary Logic
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
E. Inna and Binary Logic
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Inna is fed up with jokes about female logic. So she started using binary logic instead.
Inna has an array of n elements a1[1],a1[2],...,a1[n]. Girl likes to train in her binary logic, so she does an exercise consisting of n stages: on the first stage Inna writes out all numbers from array a1, on the i-th (i≥2) stage girl writes all elements of array ai, which consists of n-i+1 integers; the k-th integer of array ai is defined as follows: ai[k]=ai-1[k]ANDai-1[k+1]. Here AND is bit-wise binary logical operation.
Dima decided to check Inna's skill. He asks Inna to change array, perform the exercise and say the sum of all
elements she wrote out during the current exercise.
Help Inna to answer the questions!
Inna has an array of n elements a1[1],a1[2],...,a1[n]. Girl likes to train in her binary logic, so she does an exercise consisting of n stages: on the first stage Inna writes out all numbers from array a1, on the i-th (i≥2) stage girl writes all elements of array ai, which consists of n-i+1 integers; the k-th integer of array ai is defined as follows: ai[k]=ai-1[k]ANDai-1[k+1]. Here AND is bit-wise binary logical operation.
Dima decided to check Inna's skill. He asks Inna to change array, perform the exercise and say the sum of all
elements she wrote out during the current exercise.
Help Inna to answer the questions!
Input
The first line contains two integers n and m (1≤n,m≤105) − size of array a1 and number of Dima's questions. Next line contains n integers a1[1],a1[2],...,a1[n] (0≤ai≤105) − initial array elements.
Each of next m lines contains two integers − Dima's question desc
Output
For each question print Inna's answer on a single line.
Examples
Input
3 4 1 1 1 1 1 2 2 3 2 1 2
Output
6 4 7 12
输入样例 复制
输出样例 复制