Cho một mảng \(x\) gồm \(n\) số nguyên, nhiệm vụ của bạn là xử lý \(q\) truy vấn dạng: có bao nhiêu số nguyên \(i\) thỏa mãn \(a \le i \le b\) và \(c \le x_i \le d\)?

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\): số lượng giá trị và số truy vấn.

Dòng thứ hai chứa \(n\) số nguyên \(x_1,x_2,\dots,x_n\): các giá trị của mảng.

Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng chứa bốn số nguyên \(a\), \(b\), \(c\) và \(d\): hỏi có bao nhiêu số nguyên \(i\) thỏa mãn \(a \le i \le b\) và \(c \le x_i \le d\).

Output

In kết quả của mỗi truy vấn.

Constraints

• \(1 \le n,q \le 2 \cdot 10^5\)

• \(1 \le x_i \le 10^9\)

• \(1 \le a \le b \le n\)

• \(1 \le c \le d \le 10^9\)

Example

8 4
3 2 4 5 1 1 5 3
2 4 2 4
5 6 2 9
1 8 1 5
3 3 4 4

2
0
8
1