题目描述

Radomir 决定体验一种全新生活——去海边当酒保。

作为酒保，需要一眼判断：收银机里现有的钞票，是否能够恰好找出某个金额的零钱。这个问题对他来说太简单了，于是他把问题加难了。

现在有 $n$ 张钞票，面值分别为 $x_1,x_2,\dots,x_n$。你需要回答 $q$ 个询问，每个询问由四个参数 $(l,r,a,b)$ 描述。

对于一个询问，你需要求出有多少个自然数 $K$ 满足 $a \le K \le b$，并且可以只使用钞票 $x_l,x_{l+1},\dots,x_r$ 中的某个子集，使这些钞票的和恰好等于 $K$。

形式化地说，要求统计区间 $[a,b]$ 中有多少个整数 $K$，满足存在 $\{x_l,x_{l+1},\dots,x_r\}$ 的一个子集，其元素和为 $K$。

各个询问相互独立。在同一个询问中，每张钞票最多只能使用一次。

请编写程序 sums，完成全部询问。

输入格式

第一行输入两个整数 $n,q$，分别表示钞票数量和询问数量。

第二行输入 $n$ 个整数，表示各张钞票的面值。

接下来 $q$ 行，每行输入四个整数 $(l,r,a,b)$，表示一个询问。

输出格式

输出 $q$ 行。

对于每个询问，输出一个整数，表示答案。

数据范围

• $1 \le n \le 500$
• $1 \le q \le 1\,500\,000$
• $x_i > 0$
• $S=x_1+x_2+\cdots+x_n \le 250\,000$
• $1 \le l \le r \le n$
• $1 \le a \le b \le 1\,000\,000$

子任务

只有通过某个子任务中的全部测试点，才能获得该子任务的全部分数。

样例输入 #1

5 2
12 3 4 6 8
2 4 6 15
1 5 1 1000

样例输出 #1

5
27