题目描述

给定一个正整数序列\(\{a_i\}, i = 1,2 \cdots N\)，输入\(K\)次询问，每次询问包含4个参数\(l,r,s,t\)，求子区间\(\{a_l, a_{l+1} \cdots a_{r-1}, a_r\}\)中，所有位于闭区间\([s,t]\)内的值之和。

输入格式

第一行是两个正整数\(N,K\)；
第二行是\(N\)个正整数\(a_1, a_2 \cdots a_N\)；
之后\(K\)行依次给出每次询问，每行包含4个正整数\(l,r,s,t\)，表示该次询问的参数，保证\(1 \le l \le r \le N, \quad s \le t\)。

输出格式

按照输入顺序依次输出各个询问的结果，每次输出一行。

样例

输入

7 4
1 4 3 7 6 2 5
2 5 2 5
1 6 3 7
2 3 4 8
4 7 2 5

输出

7
20
4
7

数据规模及约定

对于所有数据：\(N \le 10^5, \quad K \le 10^5, \quad 1 \le a_i \le 10^5, \quad 1 \le s \le t \le 10^5\)
其中20%的数据满足：\(N, K \le 1000\)
另外40%的数据满足：\(l \in \{1, 2\}, \quad r \in \{N - 1, N\}\)
时间限制1s，空间限制256MB。