Cho dãy số nguyên gồm n phần tử \(a_1,a_2,\cdots,a_n\) \((|a_i| \leq 10^9)\). 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 \leq 10^9,q \leq 10^5)\).
• Dòng thứ hai chứa \(a_1,a_2,\cdots,a_n (|a_i| \leq 10^9)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u,v (1 \leq u \leq v \leq 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 \leq 500\)
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^4\)
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^5\)

Example

5 6 3
7 2 1 6 5
2 3
3 4
5 5 

2