주식 거래소

G. Reedy 교수는 주식 거래소에서 주식을 사고팔아 돈을 벌기 위한 프로그램을 작성하고 있습니다. 교수는 Noway라는 회사의 주식에 관심이 있으며, 성공의 열쇠는 거래소의 과거 기록을 꼼꼼히 살펴보는 것이라고 믿습니다. 교수는 $n$일 동안 주가를 관찰했고, $i$번째 날 Noway 주식 한 주의 가격은 $p_i$달러였습니다 ($1 \le i \le n$). 모든 가격은 서로 다르다고 가정합니다.

교수는 이 데이터에 대해 $m$개의 질의를 하려고 합니다. 각 질의는 $\langle b, e, l, u \rangle$ 형태이며, $b$번째 날부터 $e$번째 날까지(양 끝 포함) 중에서 주가가 $l$달러 이상 $u$달러 이하였던 날이 며칠인지를 묻습니다.

질의는 인코딩된(온라인) 형태로 주어집니다. $i$번째 질의 ($1 \le i \le m$)에서는 네 정수 $b_i$, $e_i$, $l_i$, $u_i$가 주어집니다. 여러분은 질의 $\langle b_i, e_i, l_i + s_{i-1}, u_i + s_{i-1} \rangle$의 답인 $s_i$를 계산해야 합니다. 여기서 $s_{i-1}$은 바로 앞 질의의 답이며 $s_0 = 0$입니다. 각 질의가 직전 답에 의존하므로, 질의는 반드시 순서대로 처리해야 합니다.

표준 입력에서 주가 기록과 질의를 읽어 각 질의의 답을 계산하고, 표준 출력에 답을 출력하는 프로그램을 작성하세요.

첫째 줄에 두 정수 $n$과 $m$이 공백으로 구분되어 주어집니다 ($1 \le n \le 100{,}000$, $1 \le m \le 1{,}000{,}000$). 이어지는 $n$개의 줄에는 각각 정수 $p_i$가 하나씩 주어지며, 이는 $i$번째 날의 주가입니다 ($1 \le p_i \le 10^9$). 그다음 $m$개의 줄에는 각각 네 정수 $b_i$, $e_i$, $l_i$, $u_i$가 공백으로 구분되어 주어집니다 ($1 \le b_i \le e_i \le n$, $1 \le l_i + s_{i-1} \le u_i + s_{i-1} \le 10^9$). 주어지는 $l_i$와 $u_i$ 자체는 0 이하일 수 있으며, 디코딩된 경계 $l_i + s_{i-1}$과 $u_i + s_{i-1}$만이 $[1, 10^9]$ 범위에 있음이 보장됩니다.

$m$개의 줄을 출력합니다. $i$번째 줄에는 $i$번째(디코딩된) 질의의 답인 정수 $s_i$ 하나를 출력합니다.