Bảo và Lâm là đôi bạn thân. Cả hai bạn rất đam mê đồ công nghệ nên cả hai muốn đến khu mua sắm công nghệ Shiro. Ở con đường Shiro, có \(n\) cửa hàng xếp thành hàng ngang được đánh số từ \(1\) đến \(n\).

Thời nay, việc tìm hiểu một cửa hàng mà không cần vào trực tiếp ở quầy là một điều dễ dàng. Chỉ cần tìm ra page, web của những cửa hàng đó, bạn có thể tìm trước các sản phẩm mà mình muốn mua thay vì đến tận nơi để xem. Do đó, trước khi đến trung tâm công nghệ Shiro đông đúc, Bảo và Lâm sẽ ở nhà tìm hiểu hết \(n\) cửa hàng và sau đó mới đến tại cửa hàng để mang về. Sau khi đã tính toán xong, cả hai bạn đã thống kê lại lượng tiền cần chi ra đối với cửa hàng thứ \(i\) là \(a_i\) đồng. Và với mọi cửa hàng \(i\), Bảo và Lâm cũng thống nhất rằng nếu đã mua thì phải mua đúng \(a_i\) đồng như đã tính toán ở nhà hoặc là không mua gì cả.

Sau khi đã có bản thống kê chi tiêu, cả hai bạn bắt đầu di chuyển đến khu Shiro để mua sắm. Bảo sẽ chọn cửa hàng bắt đầu di chuyển đó là cửa hàng \(l\), nghĩa là sau đó, cả hai bạn trẻ sẽ đến các cửa hàng \(l+1,l+2,\ldots\) tức là cả hai sẽ tới cửa hàng \(i\) rồi mới sang cửa hàng \(i+1\) và bắt đầu từ vị trí \(l\). Tuy nhiên, lâm nhận thấy rằng lúc này cả hai chỉ có trong tay số tiền là \(k\) đồng nên có thể sẽ không chi tiêu được theo dự định tại tất cả các cửa hàng từ vị trí \(l\) đến vị trí \(n\). vì vậy, Lâm quyết định đưa ra hai giá trị \(u,v\) \((u \le v)\) làm tiêu chí mua sắm. Tại cửa hàng \(i\), nếu giá trị \(a_i\) không nằm trong đoạn \([u,v]\) thì Bảo và Lâm sẽ bỏ qua và tiếp tục di chuyển đến cửa hàng thứ \(i+1\) (nếu \(i<n\)). Ngược lại, với \(u \le a_i \le v\), cả hai bạn sẽ bỏ ra \(a_i\) đồng như dự tính nếu như số tiền còn lại vẫn \((a_i \le k)\). Tuy nhiên, nếu số tiền còn lại không đủ để mua như dự định \((a_i > k)\) thì cả hai sẽ rất buồn chán và đi về luôn mà không quan tâm các cửa hàng sau đó nữa. Đương nhiên nếu mua được theo dự tính thì số tiền mà hai bạn còn lại cho chuyến mua sắm lần này sẽ giảm đi \(a_i\) đồng.

Như vậy, số lượng cửa hàng có thể mua sắm được trong chuyến đi lần này phụ thuộc vào việc cả hai bạn chọn \(l,u,v\) và số tiền mà cả hai mang theo \(k\). Bạn hãy giúp hai bạn trẻ tính xem số cửa hàng mà các bạn đi qua là bao nhiêu? Lưu ý rằng, những cửa hàng có giá trị \(a_i\) không nằm trong đoạn \([u,v]\) vẫn xem là đi qua vì sau đó cả hai có thể di chuyển tiếp, còn cửa hàng có giá trị \(a_i\) thuộc đoạn \([u,v]\) nhưng lại có \(a_i > k\) thì xem như không đi qua vì đây là cửa hàng làm cho cả hai bạn thất vọng.

Có \(q\) giả thuyết cho các giá trị \(l,u,v,k\) và vẫn dựa trên \(n\) giá trị \(a_1, a_2, \ldots, a_n\) dự định ban đầu của cả hai bạn. Với mỗi giả thuyết, bạn hãy tính xem cả hai bạn Bảo và Lâm sẽ đi qua được bao nhiêu cửa hàng, bạn cần in ra số lượng đó.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\)) là số lượng cửa hàng.
• 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\)) là \(n\) dự định tương ứng với \(n\) cửa hàng của hai bạn.
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(l\), \(u\), \(v\), và \(k\) (\(1 \leq l \le n\), \(1 \leq u \le v \le 10^9\), \(1 \leq k \le 10^9\)) mô tả một giả thiết.

Output

• Với mỗi giả thuyết, hãy đưa ra số lượng cửa hàng mà cả hai bạn đi qua.

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 \leq 500\) với mọi \(1 \leq i \leq 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.

Example

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

3
7
2