403549: GYM101192 K Problem

Tired of long, confusing, boring, tedious fairy-tales and legends in problem statements? All these pathetic authors’ attempts to express their hidden literary talents, which, in fact, they barely have… This inexplicable desire to mangle a crystal clear, orderly and elegant mathematical problem and throw it into our dreary reality… Enough! This problem will be short, clear and unequivocal.

You are given array F, which consists of n integers, and m quadruples a_i, b_i, c_i, d_i, such that a_i ≤ b_i, c_i ≤ d_i. For every quadruple compute and print value ans_i that is equal to the number of ordered pairs (u, v), such that a_i ≤ u ≤ b_i, c_i ≤ v ≤ d_i and F_u = F_v.

The first line of the input contains two integers n and m — length of array F and the number of quadruples. The second line contains n space-separated integers F_i. Each of next m lines contains four integers — a_i, b_i, c_i and d_i.

Print m lines. The i-th line should contain only one integer — ans_i.

10 5
4 1 5 0 1 1 1 0 2 1
7 10 4 6
3 5 3 5
5 10 4 7
9 10 3 10
1 3 2 10

5
3
13
5
6

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

2
4
0