Frequency Dot Product Queries

You are given a sequence \(a_1, a_2, \dots, a_N\) of length \(N\) and \(q\) queries. For each query you are given four integers \(l_1, r_1, l_2, r_2\). For each query, you need to compute:

[ \sum_{x=0}^{\infty} \text{get}(l_1, r_1, x) \times \text{get}(l_2, r_2, x), ]

where \(\text{get}(l, r, x)\) denotes the number of times the integer \(x\) appears in the subarray \(a_l, a_{l+1}, \dots, a_r\). In other words, for each query, you are to calculate the dot product of the frequency vectors of the two subarrays.

Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(N\) and \(q\) separated by a space.

The second line contains \(N\) integers \(a_1, a_2, \dots, a_N\) separated by spaces.

Each of the following \(q\) lines contains four integers \(l_1, r_1, l_2, r_2\), representing a query.

Indices are 1-indexed.

outputFormat

For each query, output a single integer representing the computed dot product of the frequency counts in the two specified subarrays. Each answer should be printed on a new line.

sample

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

4
9