Trò chơi tâm lý

Bạn được cung cấp điểm số của \(n\) khán giả trong một buổi trắc nghiệm tâm lí.
Có \(m\) người chơi trên sân khấu. Với người chơi thứ \(i\), chương trình đưa ra hai số nguyên
\(s_i\) và \(f_i\) với ý nghĩa rằng những khán giả có tổng điểm nằm trong đoạn \([s_i, f_i]\)
được xem là phù hợp nhất với người chơi đó.

Yêu cầu: Với mỗi người chơi, hãy đếm xem có bao nhiêu khán giả phù hợp.

Input

• Dòng đầu chứa hai số nguyên \(n, m\) \((1 \le n, m \le 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^5)\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(s_i, f_i\) \((1 \le s_i \le f_i \le 10^5)\).

Output

In ra \(m\) dòng, dòng thứ \(i\) ghi số lượng khán giả có điểm nằm trong đoạn \([s_i, f_i]\).

Scoring

• Có \(50\%\) số điểm ứng với \(n, m \le 5000\).

Sample Input 1

5 2
7 2 4 5 3
1 4
3 10

Sample Output 1

3
4