Given a sequence ~A~ with ~n~ positive integers, ~a_1~, ~a_2~, ~\ldots~, ~a_n~, and ~q~ queries. Each query specifies three subarrays ~[L_1, R_1]~, ~[L_2, R_2]~, and ~[L_3, R_3]~. Bob wants to find the value

$$\displaystyle \text{len}(L_1, R_1) + \text{len}(L_2, R_2) + \text{len}(L_3, R_3) - 3 \times \big| a[L_1:R_1] \cap a[L_2:R_2] \cap a[L_3:R_3] \big|$$

where ~\text{len}(L_i, R_i)~ is the length of the subarray ~[L_i, R_i]~ and ~\big| a[L_1:R_1] \cap a[L_2:R_2] \cap a[L_3:R_3] \big|~ represents the number of shared common integers in all three subarrays.

For example, if the ~1~st subarray is ~[1, 2, 2, 3, 3]~, the ~2~nd subarray is ~[3, 2, 3, 1, 1]~, and the ~3~rd subarray is ~[1, 3, 2, 2, 3]~, the shared common integers are ~(1, 2, 3, 3)~, and thus the value Bob wants to find is ~5 + 5 + 5 - 3 \times 4 = 3~.

Input Specification

The first line of input contains two integers ~n~ and ~q~ (~1 \le n, q \le 10^5~), indicating the length of the sequence and the number of queries.

The second line of input contains ~n~ integers ~a_i~ (~1 \le a_i \le 10^9~).

Each of the following ~q~ lines contains six integers, ~L_1~, ~R_1~, ~L_2~, ~R_2~, ~L_3~, ~R_3~ (~1 \le L_i \le R_i \le n~).

Output Specification

Output one integer per line for each query.

Constraints

Subtask	Points	Additional constraints
~1~	~30~	~n, q \le 2000~.
~2~	~70~	No additional constraints.

Sample Input

5 2
1 2 2 3 3
1 2 2 3 3 4
1 5 1 5 1 5

Sample Output

3
0