Magical Mushrooms

Marisa finds a row of n colorful mushrooms in the forest with colors \(a_1, a_2, \ldots, a_n\). She is very picky and will only pick the "magical mushrooms." A mushroom of a certain color is defined as magical in a given interval \([l, r]\) if and only if, letting \(x\) be the number of mushrooms of that color inside the interval and \(T\) be the total number of mushrooms of that color in the entire row, the following condition holds:

[ \left|2x - T\right| \le k ]

You are given \(m\) queries. Each query provides an interval \([l, r]\) and you are to determine how many distinct colors in that interval correspond to magical mushrooms.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) where \(n\) is the number of mushrooms, \(m\) is the number of queries, and \(k\) is the constant used in the magical condition.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the colors of the mushrooms.

Each of the following \(m\) lines contains two integers \(l\) and \(r\) denoting the inclusive bounds of a query.

outputFormat

For each query, output a single integer on a new line representing the number of distinct colors in the interval \([l, r]\) that satisfy the magical mushroom condition.

sample

5 3 1
1 2 1 2 3
1 3
2 5
1 5

1
2
1