놀이기구 2

1번부터 N번까지 번호가 붙은 아이 N명이 있다. 아이들은 놀이공원에 가는 것을 좋아하지만 키 제한 때문에 놀이기구를 타지 못하는 일이 잦다. 놀이기구는 1번부터 M번까지 M개가 있고, 모든 놀이기구의 정원은 2명이다.

아이 i와 아이 j가 함께 놀이기구 k를 타려면 (아이 i의 키) + (아이 j의 키) ≥ (놀이기구 k의 키 제한)이 성립해야 한다.

(i, j, k) 쌍이 Q개 주어진다. 각 쌍은 아이 i와 아이 j가 매일 놀이기구 k를 타려고 시도한다는 뜻이다. 처음에는 모든 아이의 키가 0cm라서 아무도 놀이기구를 타지 못하지만, 아이들은 성장기라서 키가 쑥쑥 자란다. 구체적으로, 첫날부터 K번째 날까지 매일 한 명의 키가 1씩 자란다.

그런데 이 문제에서는 아이들의 성장세가 무섭다! 전날 아이들이 놀이기구를 탄 횟수가 전전날 아이들이 놀이기구를 탄 횟수보다 많으면, 그날 키가 1이 아니라 2만큼 자란다. 단, 첫째 날과 둘째 날에는 이 규칙을 적용하지 않는다.

매일 누구의 키가 자라는지 주어질 때, 첫날부터 K번째 날까지 날마다 아이들이 놀이기구를 모두 몇 번 타는지 출력하는 프로그램을 작성하시오. 하루 안에서는 키가 자라는 일이 놀이기구를 타는 일보다 먼저 일어난다.

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

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

셋째 줄에 첫날부터 K번째 날까지 그날 키가 자라는 아이의 번호가 K개 주어진다. ($1 \le$ 번호 $\le N$)

다음 Q개의 줄에 (i, j, k) 쌍이 한 줄에 하나씩 주어진다. ($1 \le i, j \le N$, $1 \le k \le M$) i와 j는 같을 수도 있으며, 이때 조건은 (아이 i의 키) + (아이 i의 키) ≥ (놀이기구 k의 키 제한)이다.

K개의 줄에 걸쳐 날마다 아이들이 놀이기구를 모두 몇 번 타는지 출력한다.

둘째 날까지 아이들은 놀이기구를 타지 못한다.

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

넷째 날에는 아이 3과 아이 5가 놀이기구 3을 탈 수 있고, 아이 1과 아이 2가 놀이기구 1과 2를 탈 수 있고, 아이 1과 아이 5가 놀이기구 2를 탈 수 있다. 셋째 날의 횟수 1이 둘째 날의 횟수 0보다 많으므로 넷째 날에는 아이 1의 키가 2만큼 자란다.