硕哥叕要追上出题人了，出题人赶紧再出一个问题来阻挠硕哥。
出题人扔出了n个珠子，每个珠子可能为黑色，也可能为白色。现在他多次询问硕哥某一段区间里黑色珠子的个数。
输入格式
第一行两个正整数n和q，分别表示n个珠子和q个询问
第二行n个正整数，每个数可以为0或者1，其中0表示这个珠子为黑色，1表示白色
第三行到第q+2行，每行两个正整数u和v(u<=v)，表示求区间[u,v]内黑色珠子的数量
输出格式
对于每一个询问
输出一个整数表示这段区间里黑色珠子的数量
每个输出中空一行

输入样例

5 2 
1 0 1 0 0 
2 4
3 5 

输出样例

2
2

输出解释
对于第一个询问，在区间[2,4]内，有两个黑色珠子
对于第二个询问，在区间[3,5]内，有两个黑色珠子
数据范围
对于30%的数据，n<1000，q=1
对于60%的数据，n<100，q<100000
对于100%的数据，n<1000,q<100000