Cho dãy số nguyên gồm n phần tử a₁,a₂,…a_n (|a_i|≤10⁹). Cho giá trị x và q câu hỏi có dạng S(u,v). Với S(u,v) là tổng các giá trị của các phần tử từ u đến v.

Yêu cầu: Đếm xem trong q câu hỏi đó có bao câu hỏi có giá trị nhỏ hơn x.

Input

• Dòng đầu tiên chứa ba số nguyên dương n, x, q(x ≤ 10⁹, q ≤ 10⁵).
• Dòng thứ hai chứa a₁,a₂,⋯,a_n (|a_i|≤10⁹).
• q dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u,v(1 ≤ u ≤ v ≤ n).

Output

• In ra một số nguyên là số lượng câu hỏi có giá trị nhỏ hơn x

Scoring

• Subtask 1 (50% số điểm): n ≤ 500
• Subtask 2 (30% số điểm): n ≤ 10⁴
• Subtask 3 (30% số điểm): n ≤ 10⁵