Given an array of ~n~ integers ~ a_1, a_2, \cdots, a_n ~. Given a value ~ x ~ and ~ q ~ queries of the form ~ S(u, v) ~ with ~ S(u,v)~ is the sum of the values of the elements from ~ u ~ to ~ v ~.

Requirement: Count how many of those ~ q ~ queries have a sum less than ~ x ~.

Input

• The first line contains three positive integers ~ n, x~ and ~ q ~ (~ x \leq 10^9~ and ~n, q \leq 10^5 ~).
• The second line contains ~ a_1, a_2, \cdots, a_n ~ (~ |a_i| \leq 10^9 ~).
• The next ~ q ~ lines each contain two positive integers ~ u ~ and ~ v ~ (~ 1 \leq u \leq v \leq n ~).

Output

• Print a single integer, the number of queries with a sum less than ~ x ~.

Sample Input

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

Sample Output

2