14435번 - 놀이기구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 ≤ N, M, K, Q ≤ 200,000)

둘째 줄에는 놀이기구들의 키제한이 순서대로 주어진다. (1 ≤ 키제한 ≤ 200,000)

셋째 줄에는 각 날에 키가 자라는 아이의 번호가 총 K개 주어진다. (1 ≤ 번호 ≤ N)

그 다음 Q줄에 걸쳐 (i, j, k) 쌍이 주어진다. (1 ≤ i, j ≤ N, 1 ≤ k ≤ M)

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

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

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

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