403549: GYM101192 K Problem

Memory Limit:64 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Problemtime limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

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 ai, bi, ci, di, such that ai ≤ bi, ci ≤ di. For every quadruple compute and print value ansi that is equal to the number of ordered pairs (u, v), such that ai ≤ u ≤ bi, ci ≤ v ≤ di and Fu = Fv.

Input

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 Fi. Each of next m lines contains four integers — ai, bi, ci and di.

1 ≤ n ≤ 2 × 105
1 ≤ m ≤ 3 × 104
0 ≤ Fi ≤ 105
1 ≤ ai ≤ bi ≤ n
1 ≤ ci ≤ di ≤ n
Output

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

ExamplesInput
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
Output
5
3
13
5
6
Input
5 3
2 1 3 3 2
3 3 2 5
3 4 3 4
4 5 2 2
Output
2
4
0

加入题单

上一题 下一题 算法标签: