Nhân dịp chuẩn bị cho kỳ thi Memes Tournament, thành viên cộm cán quanghieu18112013 quyết định sắp xếp lại kho lưu trữ gồm \(n\) bức ảnh meme của mình. Các bức ảnh được xếp thành một hàng ngang và được đánh số thứ tự từ \(1\) đến \(n\). Bức ảnh thứ \(i\) sở hữu một chỉ số độ hài hước là số nguyên \(a_i\).

Để đánh giá chất lượng các bộ meme phục vụ cho giải đấu, quanghieu18112013 cần thực hiện \(q\) truy vấn thống kê. Mỗi truy vấn được cho bởi bốn số nguyên \(l, r, x, y\) (\(1 \le l \le r \le n\) và \(x \le y\)). Với mỗi truy vấn, bạn hãy giúp Quang Hiệu đếm xem có bao nhiêu bức ảnh meme nằm trong đoạn vị trí từ \(l\) đến \(r\) (tức là chỉ số \(i\) thoả mãn \(l \le i \le r\)) có độ hài hước \(a_i\) thuộc đoạn \([x, y]\) (nghĩa là \(x \le a_i \le y\)).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\) (\(1 \le n, q \le 2 \times 10^5\)) — số lượng bức ảnh meme và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) — độ hài hước của các bức ảnh meme.
• \(q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(l, r, x, y\) (\(1 \le l \le r \le n, 1 \le x \le y \le 10^9\)) — thông tin của một truy vấn thống kê.

Output

• Gồm \(q\) dòng, mỗi dòng in ra một số nguyên duy nhất là kết quả của truy vấn tương ứng theo thứ tự xuất hiện ở đầu vào.

Example

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

2
6
0
2

Scoring

• Subtask 1 (40 điểm): \(1 \le n, q \le 2000\).
• Subtask 2 (60 điểm): \(1 \le n, q \le 2 \times 10^5\).