School Pairing

The school of Auckbury admits a very large class every year. In one year the intake came close to a million students. The school cares about how well its students do in programming contests, so every student receives a skill grade on admission. A grade is an integer between $-10^9$ and $10^9$.

Each year the new students are numbered from $1$ to $N$, where $N$ is that year's intake. The numbers identify students in the freshman contests. Those contests are held often during the year and are open only to the newest class.

When a contest starts, the staff computer picks two numbers between $1$ and $N$. The students standing between those two numbers, both ends included, pair up into teams of two and compete against other teams. The principal cares about fairness, so he allows a team to compete only when the two skill grades add up to $K$, the value he fixes at the start of the day.

The $M$ contests held in one year are given. For each contest, find how many teams can be formed inside the range the computer picked. A team is an unordered pair of two students, two teams are different when their pairs of student numbers differ, and a student who belongs to several teams is counted once for each of them.

The input holds several test cases.

The first line of each test case has three integers $N$, $M$ and $K$ ($1 \le N \le 10^5$, $1 \le M \le 10^5$, $1 \le K \le 10^6$).

The second line has the skill grades of the $N$ students, listed in order from student $1$. Each grade is an integer between $-10^9$ and $10^9$.

Each of the next $M$ lines has two numbers $i$ and $j$ picked by the computer ($1 \le i, j \le N$). The numbers appear in the order they were picked, so $i$ may be larger than $j$. The range runs from the smaller of the two numbers to the larger one.

A line whose $N$, $M$ and $K$ are all $0$ ends the input. That line is not a test case.

There are at most $20$ test cases. The sum of $N$ over all test cases and the sum of $M$ over all test cases are each at most $2 \times 10^5$.

For each test case print one line per contest, in the order the contests are given, holding the number of teams that can be formed in that range. Print one blank line after each test case.

In the first example four students stand in a line and the principal fixes the sum at $5$. In the first contest the computer picks $1$ and $4$, so all four students fall inside the range. Only one team in that range has a combined skill of $5$, the one made of the first two students. In the second contest the computer picks $3$ and $4$, and those two grades do not add up to $5$, so no team can be formed.