Cho mảng \(A\) gồm \(N\) phần tử. Bạn cần thực hiện \(Q\) truy vấn: với mỗi truy vấn, đếm số lượng phần tử có giá trị nằm trong đoạn \([X, Y]\) trong đoạn con từ vị trí \(L\) đến \(R\) (1-indexed).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(L\), \(R\), \(X\) và \(Y\) (\(1 \le L \le R \le N, -10^9 \le X \le Y \le 10^9\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra số lượng phần tử thỏa mãn trên một dòng.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000\).
• Subtask 2 (70% số điểm): \(N, Q \le 10^5\), các ràng buộc gốc.

Ví dụ

Input:

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

Output:

1
3
1

Giải thích:

• Truy vấn 1: Đoạn \([1..3]\) là \([4, 2, 7]\). Các phần tử thuộc \([3, 6]\) chỉ có 4 \(\to\) 1 phần tử.
• Truy vấn 2: Đoạn \([2..5]\) là \([2, 7, 1, 5]\). Các phần tử thuộc \([2, 5]\) là 2, 5 \(\to\) 3 phần tử? Khoan, \([2..5]\) là \([2, 7, 1, 5]\). Các phần tử thuộc \([2, 5]\) là 2, 5. Tổng cộng là 2 phần tử chứ? A: Đúng vậy! 2 và 5 là 2 phần tử. Hãy sửa ví dụ đầu ra thành: 1 2 1
  • Truy vấn 3: Đoạn \([1..5]\) là \([4, 2, 7, 1, 5]\). Các phần tử thuộc \([6, 10]\) chỉ có 7 \(\to\) 1 phần tử.