Nhà thám hiểm Ethan đang chuẩn bị cho một cuộc hành trình đầy mạo hiểm để tìm kiếm những viên bảo vật quý hiếm. Anh ta có một bản đồ, chỉ dẫn về \(n\) hang động xếp thành một dãy, được đánh số từ \(1\) đến \(n\). Tại mỗi hang động thứ \(i\), có một viên bảo vật với giá trị \(a_i\).
Ethan đã tìm hiểu và biết rằng để lấy được bảo vật, anh phải trả đúng giá trị của nó. Nếu không đủ tiền, anh sẽ không thể lấy được và chuyến đi sẽ kết thúc. Tuy nhiên, anh ta cũng có một danh sách ưu tiên. Chỉ những bảo vật có giá trị nằm trong một khoảng nhất định mới được xem xét.
Ethan bắt đầu chuyến đi từ hang động \(l\). Anh ta sẽ đi lần lượt qua các hang động \(l, l+1, \ldots, n\). Số tiền anh ta có ban đầu là \(k\). Ethan chỉ quan tâm đến những bảo vật có giá trị nằm trong khoảng \([u, v]\), tức là \(u \le a_i \le v\).
Tại mỗi hang động \(i\) (\(i \ge l\)):
- Nếu giá trị của bảo vật \(a_i\) không nằm trong khoảng \([u, v]\), Ethan sẽ bỏ qua và tiếp tục di chuyển đến hang động tiếp theo.
-
Ngược lại, nếu \(a_i\) nằm trong khoảng \([u, v]\), Ethan sẽ cố gắng mua nó.
-
Nếu số tiền còn lại của anh ta đủ để mua (\(a_i \le k\)), anh ta sẽ chi \(a_i\) đồng và tiếp tục hành trình.
- Nếu số tiền không đủ (\(a_i > k\)), Ethan sẽ thất vọng và quay về ngay lập tức, không thăm các hang động còn lại.
Ethan muốn biết với mỗi bộ tham số \((l, u, v, k)\), anh ta sẽ đi qua được bao nhiêu hang động. Lưu ý, các hang động mà anh ta bỏ qua vẫn được xem là đã đi qua. Chỉ khi anh ta phải quay về vì không đủ tiền, chuyến đi mới kết thúc.
Có \(q\) giả thuyết khác nhau về các giá trị \(l, u, v, k\). Bạn hãy giúp Ethan trả lời cho mỗi giả thuyết.
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\)).
- Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)).
- Trong \(q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(l, u, v\), và \(k\) (\(1 \le l \le n\), \(1 \le u \le v \le 10^9\), \(1 \le k \le 10^9\)).
Output
- Với mỗi giả thuyết, in ra một số nguyên duy nhất là số lượng hang động mà Ethan đã đi qua.
Example
Test 1
Input
7 3
4 6 8 2 10 5 1
4 1 5 7
1 2 3 5
1 1 10 15
Output
3
7
2
Scoring
- Subtask 1 (20% số điểm): Các giả thuyết có \(k\) bằng nhau và \(u=1, v=10^9\).
- Subtask 2 (20% số điểm): \(a_i \le 500\) với mọi \(1 \le i \le n\).
- Subtask 3 (20% số điểm): Các giả thiết có \(v - u \le 5\).
- Subtask 4 (20% số điểm): Các giả thiết có \(u = 1\).
- Subtask 5 (20% số điểm): Không có ràng buộc gì thêm.
