The bubble sort process is defined as follows:

For a sequence $a_1, \dots, a_n$ of length $n$, perform $n-1$ rounds of "bubble" operations. In each "bubble" operation, the following steps are performed:

• If $a_1 > a_2$, swap $a_1, a_2$.
• If $a_2 > a_3$, swap $a_2, a_3$.
• $\dots$
• If $a_{n-1} > a_n$, swap $a_{n-1}, a_n$.

The pseudocode for one round of the "bubble" operation is as follows:

for i = 1 to n-1:
  if a[i] > a[i + 1]:
    swap(a[i], a[i + 1])

Given an array $b_1, b_2, \dots, b_n$.

For each query $(l, r, k, x, y)$, Xiao C extracts the subarray of $b$ from index $l$ to $r$, obtaining a new array $a$ where $[a_1, \dots, a_{r-l+1}] = [b_l, \dots, b_r]$, and performs $k$ "bubble" operations on array $a$.

You need to calculate the value of $\sum_{i=x}^y a_i$ after $k$ "bubble" operations.

Input

The first line contains an integer $id$ representing the subtask number. Specifically, for sample input $1$, $id=0$.

The second line contains two integers $n$ and $q$.

The next line contains $n$ integers $b_1, \dots, b_n$.

The next $q$ lines each contain $5$ integers $l, r, k, x, y$.

Output

Output $q$ lines, each containing an integer representing the answer.

Examples

Input 1

0
4 2
1 3 4 2
2 4 1 2 2
1 4 2 3 4

Output 1

2
7

Note

There are $8$ samples in the provided files, corresponding to the $8$ subtasks.

Constraints

For all data:

• $1 \le n \le 10^6$, $1 \le q \le 5 \times 10^5$
• $0 \le b_i \le 10^9$, $1 \le l < r \le n$, $1 \le k \le r-l$, $1 \le x \le y \le r-l+1$.