购买商品

莫队 前缀和[[

题目背景

渴鹅村附近建了一个大商场——Haokee Mall。这个商场非常的大，并且各种商品与店铺数不胜数。好渴鹅十分兴奋，跟你一起跑到了这个大商场里面买东西。

题目描述

商场里面卖 $n$ 件物品，第 $i$ 件物品要 $a_i$ 元才可以购买。不幸的是，好渴鹅今天出门只带了 $k$ 元钱，并且好渴鹅还有强迫症，买的商品的价值之和必须正好为 $k$。

现在好渴鹅给你抛出了 $m$ 个询问，每一个询问都是 $(l,r)$ 的形式。表示好渴鹅如果打算逛 $[l,r]$ 之内的商品，并且连续购买其中的任意部分商品，的价值之和能够正好达到 $k$ 的方案数。

你能够从容地回答出好渴鹅给你的问题吗？

输入格式

• 第一行：$n$ 和 $m$ 两个整数；
• 第二行：一共 $n$ 个数，第 $i$ 个数为 $a_i$；
• 接下来 $m$ 行：一行一个形如 $(l,r)$ 的询问。

输出格式

• 一共 $m$ 行，表示方案数。

提示说明

数据百分比	$n$	$m$	$\max (\sum _{i=1}^n{a}_i,k)$
$20\%$	$\le 100$	$\le 100$	$\le 1000$
$40\%$	$\le 1000$	$\le 1000$	$\le 10^4$
$60\%$	$\le 1000$	$\le 1000$	$\le 10^5$
$100\%$	$\le 2\times 10^5$	$\le 2\times 10^5$	$\le 10^6$