L. Extended Modulo Queries
time limit per test
8 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$A$$$ of length $$$N$$$.

We define the function: $$$$$$f(l, r, x) = \sum_{i=l}^{r} (A_i \bmod x),$$$$$$ where $$$A_i \bmod x$$$ denotes the remainder when $$$A_i$$$ is divided by $$$x$$$.

You will be given $$$Q$$$ queries. Each query is described by four integers $$$l, r, x_l, x_r$$$ ($$$1 \le l \le r \le N$$$, $$$1 \le x_l \le x_r \le 5 \cdot 10^4$$$).

For each query, compute: $$$$$$\sum_{x=x_l}^{x_r} f(l, r, x).$$$$$$

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N, Q \le 5 \cdot 10^4$$$) — the length of the array and the number of queries.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \le A_i \le 5 \cdot 10^4$$$) — the elements of the array.

Each of the next $$$Q$$$ lines contains four integers $$$l, r, x_l, x_r$$$.

Output

Print $$$Q$$$ integers — the answers to the queries in the same order as they are given.

Examples
Input
4 1
5 2 8 3
1 3 2 4
Output
10
Input
5 2
10 4 1 7 3
1 5 5 5
2 4 1 3
Output
10
5