놀이기구 1

1번부터 $N$번까지 번호가 붙은 아이 $N$명이 있다. 아이들은 놀이공원에 가는 것을 좋아하지만 키 제한 때문에 놀이기구를 타지 못할 때가 많다. 놀이기구는 1번부터 $M$번까지 $M$개가 있고, 모든 놀이기구의 정원은 2명이다. 아이 $i$와 아이 $j$가 함께 놀이기구 $k$를 타려면 (아이 $i$의 키) + (아이 $j$의 키) $\ge$ (놀이기구 $k$의 키 제한)이 성립해야 한다.

$(i, j, k)$ 쌍이 $Q$개 주어진다. 각 쌍은 아이 $i$와 아이 $j$가 매일 놀이기구 $k$를 타려고 시도한다는 뜻이다. $i$와 $j$가 같을 수도 있으며, 이때도 같은 식을 그대로 적용한다. 같은 쌍이 여러 번 주어지면 각각 따로 센다.

처음에는 모든 아이의 키가 0cm라서 아무도 놀이기구를 타지 못한다. 하지만 아이들은 성장기라서 키가 쑥쑥 자란다.

첫째 날부터 $K$번째 날까지 매일 한 명의 키가 1씩 자란다. 날마다 누구의 키가 자라는지 주어질 때, 첫째 날부터 $K$번째 날까지 각 날에 아이들이 놀이기구를 모두 몇 번 타는지 구하는 프로그램을 작성하시오. 하루 안에서는 키가 먼저 자라고, 그다음에 놀이기구를 탄다.

첫째 줄에 아이의 수 $N$, 놀이기구의 수 $M$, 기간 $K$, 쌍의 개수 $Q$가 주어진다. ($1 \le N, M, K, Q \le 200\,000$)

둘째 줄에 1번부터 $M$번까지 놀이기구의 키 제한이 순서대로 주어진다. ($1 \le$ 키 제한 $\le 200\,000$)

셋째 줄에 각 날에 키가 자라는 아이의 번호 $K$개가 날짜 순서대로 주어진다. ($1 \le$ 번호 $\le N$)

다음 $Q$개 줄에 걸쳐 $(i, j, k)$ 쌍이 한 줄에 하나씩 주어진다. ($1 \le i, j \le N$, $1 \le k \le M$)

$K$개 줄에 걸쳐 첫째 날부터 순서대로, 그날 아이들이 놀이기구를 모두 몇 번 타는지 출력한다.

첫 번째 예제에서 둘째 날까지는 아무도 놀이기구를 타지 못한다.

셋째 날에는 아이 3과 아이 5가 놀이기구 3을 탈 수 있다.

넷째 날에는 아이 3과 아이 5가 놀이기구 3을 탈 수 있고, 아이 1과 아이 2가 놀이기구 2를 탈 수 있다.