살구 씨앗

Sam은 살구 씨앗 여러 개를 가지고 있고, 크기 순으로 비내림차순이 되도록 정렬하려고 한다. 그는 다음 방법을 사용한다.

$n$개의 씨앗에 대해 Sam은 총 $n - 1$단계를 수행한다. $1$부터 $n - 1$까지 각 단계 $k$에서 다음을 수행한다.

• 첫 번째 씨앗과 두 번째 씨앗을 비교한다. 두 번째 씨앗이 더 작으면 자리를 바꾼다.
• 두 번째 씨앗과 세 번째 씨앗을 비교한다. 세 번째 씨앗이 더 작으면 자리를 바꾼다.
• 이 과정을 $(n - k)$번째 씨앗과 $(n - k + 1)$번째 씨앗의 비교까지 이어 가며, $(n - k + 1)$번째 씨앗이 더 작으면 자리를 바꾼다.

Tom은 이것이 유명한 버블 정렬이라는 것을 알아본다. Sam에게 이 방법이 얼마나 비효율적인지 보여 주려고, Tom은 $q$개의 질문을 한다. 각 질문은 $(s, e, m, l, r)$ 튜플로 표현된다. 주어진 $n$개의 씨앗 수열에 대해, 질문은 초기 수열의 $s$번째부터 $e$번째까지의 부분 수열에 Sam의 방법을 처음 $m$단계 적용한 뒤, 그 (부분적으로) 정렬된 부분 수열의 $l$번째부터 $r$번째 씨앗 크기의 합을 묻는다.

예를 들어 씨앗 크기가 $(1,3,4,2)$인 4개의 씨앗과 질문 $(2,4,1,2,2)$, $(1,4,2,3,4)$가 있다고 하자. 첫 번째 질문에서 2번째부터 4번째까지의 부분 수열은 $(3,4,2)$이다. 1단계 후에는 $(3,2,4)$가 된다. 2번째부터 2번째까지의 합은 $2$이다. 두 번째 질문에서 부분 수열은 $(1,3,4,2)$이다. 2단계 후에는 $(1,2,3,4)$가 된다. 3번째부터 4번째까지의 합은 $3 + 4 = 7$이다.

$n$개의 씨앗과 $q$개의 질문이 주어졌을 때, 각 질문의 답을 구하라.

첫 줄에 두 정수 $n$과 $q$가 주어진다 ($2 \le n \le 10^6$, $1 \le q \le 5 \times 10^5$). 둘째 줄에는 초기 순서대로 씨앗 크기 $n$개가 공백으로 구분되어 주어진다. 각 크기는 $1$ 이상 $10^9$ 이하이다. 이어지는 $q$개의 줄에는 질문 하나씩이 양의 정수 다섯 개 $s$, $e$, $m$, $l$, $r$로 공백을 두고 주어진다. 제약은 $1 \le s < e \le n$, $1 \le m \le e - s$, $1 \le l \le r \le e - s + 1$이다.

각 질문에 대해 한 줄에 답을 출력한다. 답은 $s$번째부터 $e$번째까지의 부분 수열에 Sam의 방법을 처음 $m$단계 적용한 뒤, $l$번째부터 $r$번째까지 씨앗 크기의 합이다.