Tháng tư là lời nói dối của nqson
nqson vừa phát minh ra máy kiểm tra nói dối, kiểm tra mức độ chân thật trong một câu nói. Nếu đó là lời nói thật, máy sẽ cho ra kết quả là 1 số dương, ngược lại nếu đó là lời nói dối, máy sẽ cho ra kết quả là 1 số âm. Kết quả càng lớn thì mức độ chân thật của câu nói ấy càng cao.
Ví dụ: Khi nqson nói "Trái đất hình cầu", máy sẽ cho ra kết quả 12345678 tức câu nói này là 1 câu cực kỳ hiển nhiên. Còn khi nqson nói "I love nqson", máy sẽ ra kết quả -12345 tức nqson có khả năng đang nói dối.
Trong tháng tư, nqson đã nói dối rất nhiều câu để kiểm tra, sửa chữa và nâng cấp máy. Nhằm thuận tiện cho việc nghiên cứu, nqson muốn thống kê xem: Từ câu nói thứ \(x\) đến câu nói thứ \(y\), có bao nhiêu câu nói có mức độ chân thật nằm trong đoạn \([l, r]\).
Đầu vào
Dòng đầu chứa 2 số tự nhiên \(n\) là số câu nói của nqson và \(m\) là số lần nqson thống kê
Dòng thứ hai chứa \(n\) số nguyên \(a_i\) là kết quả từng câu nói mà máy đã kiểm tra
\(m\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(x, y, l, r\)
Đầu ra
\(m\) dòng, mỗi dòng chứa một số nguyên là kết quả của từng lần thống kê
Giới hạn
\(1 \le n,m \le 10^5\)
\(-10^9 \le a_i \le 10^9\)
\(1 \le x \le y \le n\)
\(-10^9 \le l \le r \le 10^9\)
Ví dụ
Đầu vào
8 3
1 5 2 -1 -10 2 -9 0
2 7 -1 1
2 3 0 8
1 8 -20 0Đầu ra
1
2
4
Comments
31/10 vẫn là lời nói đấy
Tháng 5,6,7... cũng thế thôi