학생 짝짓기

오클버리 학교는 해마다 아주 많은 신입생을 받는다. 어떤 해에는 입학생이 백만 명에 가까웠다. 이 학교는 프로그래밍 대회 실력을 중요하게 여겨서, 입학할 때 학생마다 실력 점수를 하나씩 매긴다. 실력 점수는 $-10^9$ 이상 $10^9$ 이하의 정수다.

그해 입학생에게는 $1$번부터 $N$번까지 번호를 붙인다. $N$은 그해 입학생 수다. 이 번호는 신입생 대회에서 학생을 가리키는 데 쓴다. 신입생 대회는 한 해 동안 자주 열리고, 그해 입학생만 나갈 수 있다.

대회가 열릴 때마다 학교 컴퓨터가 $1$ 이상 $N$ 이하의 번호 두 개를 뽑는다. 뽑힌 두 번호 사이에 있는 학생은 양 끝을 포함해서 두 명씩 팀을 이뤄 다른 팀과 겨룬다. 교장은 공정함을 중요하게 여겨서, 두 학생의 실력 점수 합이 그날 정한 값 $K$와 같은 팀만 출전을 허락한다.

한 해에 열린 대회 $M$개가 주어진다. 각 대회마다 뽑힌 두 번호 사이에서 만들 수 있는 팀이 몇 개인지 구하여라. 팀은 학생 두 명을 고른 순서 없는 쌍이고, 학생 번호 쌍이 다르면 서로 다른 팀으로 센다. 한 학생이 여러 팀에 들어가도 각각 따로 센다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에 세 정수 $N$, $M$, $K$가 주어진다. ($1 \le N \le 10^5$, $1 \le M \le 10^5$, $1 \le K \le 10^6$)

둘째 줄에 학생 $N$명의 실력 점수가 $1$번 학생부터 순서대로 주어진다. 각 점수는 $-10^9$ 이상 $10^9$ 이하의 정수다.

다음 $M$개 줄에 컴퓨터가 뽑은 번호 $i$와 $j$가 한 줄에 하나씩 주어진다. ($1 \le i, j \le N$) 두 번호는 뽑힌 순서 그대로 주어지므로 $i$가 $j$보다 클 수도 있다. 이때 구간은 둘 중 작은 번호부터 큰 번호까지다.

$N$, $M$, $K$가 모두 $0$인 줄이 나오면 입력이 끝난다. 이 줄은 테스트 케이스가 아니다.

테스트 케이스는 최대 $20$개이고, 모든 테스트 케이스의 $N$의 합과 $M$의 합은 각각 $2 \times 10^5$ 이하다.

각 테스트 케이스마다 대회가 주어진 순서대로 한 줄에 하나씩, 그 구간에서 만들 수 있는 팀의 개수를 출력한다. 한 테스트 케이스의 출력을 마칠 때마다 빈 줄을 하나 출력한다.

첫 번째 예제에서는 학생 네 명이 줄을 서 있고 교장이 정한 합은 $5$다. 첫 번째 대회에서 컴퓨터가 $1$과 $4$를 뽑아 네 명 모두가 구간에 들어간다. 이 구간에서 합이 $5$인 팀은 앞의 두 학생으로 이루어진 한 팀뿐이다. 두 번째 대회에서는 $3$과 $4$를 뽑는데, 두 학생의 점수 합이 $5$가 아니므로 만들 수 있는 팀이 없다.