레이스

Memtendo 회사가 Super Mario Kart의 새 버전을 출시했다. 게임에는 1부터 $n$까지 번호가 붙은 캐릭터 $n$명이 나온다. 설문 조사로 각 캐릭터의 인기도 $b_i$를 정했고, 인기도는 0 이상의 정수다.

게임은 여러 번의 레이스로 이루어지며, 모든 캐릭터가 매 레이스에 참가한다. 레이스가 끝나면 상위 $k$명이 점수를 받는다. 1등은 $a_1$점, 2등은 $a_2$점을 받고, $k$등은 $a_k$점을 받는다. 나머지 캐릭터는 0점을 받는다. 두 캐릭터가 동시에 결승선에 도착하지 않으며, $a_1 > a_2 > \ldots > a_k > 0$을 만족한다.

총점은 다음과 같이 계산한다. 캐릭터가 모든 레이스에서 받은 점수(0점 포함)에서 가장 작은 $s$개를 지운다. 남은 점수의 합을 그 캐릭터의 인기도에 더한다. 예를 들어 인기도가 3인 루이지가 네 레이스에서 2, 1, 3, 0점을 받고 $s = 2$이면, 1점과 0점을 지운다. 따라서 루이지의 총점은 $3 + 2 + 3 = 8$이다. 레이스가 $s$번보다 적은 게임은 총점을 계산하지 않는다.

이미 $m$번의 레이스가 치러졌고 그 결과는 두 사람이 안다. 요시가 서로 다른 두 캐릭터 $u$와 $v$를 말하면, 마리오는 $v$의 총점이 $u$의 총점보다 커지기 위해 필요한 추가 레이스의 최소 수를 답해야 한다. 마리오는 각 추가 레이스의 결과를 자신에게 가장 유리하게 정할 수 있다.

첫 줄에 정수 $n$, $m$, $k$, $s$가 주어진다 ($2 \le n \le 1000$, $1 \le m \le 1000$, $1 \le k \le n$, $0 \le s \le \min(10, m)$). 둘째 줄에는 $a_1, a_2, \ldots, a_k$가 주어진다 ($1 \le a_k < a_{k-1} < \ldots < a_1 \le 10^9$). 셋째 줄에는 $b_1, b_2, \ldots, b_n$이 주어진다 ($0 \le b_i \le 10^9$). 다음 $m$개 줄에는 이미 치른 레이스의 도착 순서로, 1부터 $n$까지의 서로 다른 번호 $n$개가 한 줄에 하나씩 주어진다. 그 다음 줄에 질문 수 $q$ ($1 \le q \le 10^5$)가 주어지고, 이어서 $q$개 줄에 $u$와 $v$가 주어진다 ($1 \le u, v \le n$, $u \neq v$).

각 질문마다 $v$의 총점이 $u$의 총점보다 커질 수 있도록 하는 추가 레이스의 최소 수를 한 줄에 하나씩 출력한다. 추가 레이스가 필요 없으면 0을 출력한다. 모든 질문에 대해 답이 존재함이 보장된다.