Stock Exchange

Professor G. Reedy is writing a program to help him make money buying and selling shares on a stock exchange. He is interested in shares of a company called Noway, and he believes the key to success is a careful study of the exchange's history. He observed share prices for $n$ days; on the $i$-th day a Noway share was worth $p_i$ dollars ($1 \le i \le n$). Assume that all prices are distinct.

The professor wants to run $m$ queries on this data. A query has the form $\langle b, e, l, u \rangle$ and asks: among the days from the $b$-th to the $e$-th (inclusive), how many had a share price between $l$ and $u$ dollars (inclusive)?

The queries are given in an encoded (online) form. For the $i$-th query ($1 \le i \le m$) you are given four integers $b_i$, $e_i$, $l_i$, $u_i$. You must compute $s_i$, the answer to the query $\langle b_i, e_i, l_i + s_{i-1}, u_i + s_{i-1} \rangle$, where $s_{i-1}$ is the answer to the previous query and $s_0 = 0$. Because each query depends on the previous answer, the queries must be processed in order.

Write a program that reads the price history and the queries from standard input, computes each answer, and writes the answers to standard output.

The first line contains two integers $n$ and $m$ ($1 \le n \le 100{,}000$, $1 \le m \le 1{,}000{,}000$) separated by a space. Each of the next $n$ lines contains one integer $p_i$ ($1 \le p_i \le 10^9$), the share price on day $i$. Each of the following $m$ lines contains four integers $b_i$, $e_i$, $l_i$, $u_i$ ($1 \le b_i \le e_i \le n$ and $1 \le l_i + s_{i-1} \le u_i + s_{i-1} \le 10^9$) separated by spaces. The given $l_i$ and $u_i$ may themselves be non-positive; only the decoded bounds $l_i + s_{i-1}$ and $u_i + s_{i-1}$ are guaranteed to lie in $[1, 10^9]$.

Print $m$ lines. The $i$-th line must contain the single integer $s_i$, the answer to the $i$-th (decoded) query.