짖는 개들!

면접 대비

시간 제한2초메모리 제한512 MB

요약

각 개가 다른 개의 짖음을 듣고 일정 시간 뒤에 짖는 규칙과 청취 관계 그래프가 주어질 때, 0초부터 T초까지 각 개가 짖은 횟수를 세는 문제입니다.

난이도: 보통10점 중 5점
유형: 시뮬레이션, 그래프, 구현, 큐
정답자: 아직 제출이 없습니다

문제

당신은 개들이 많은 동네에 살고 있습니다. 개는 개를 좋아하고, 짖는 것을 더 좋아하며, 무엇보다 다른 개가 짖을 때 함께 짖는 것을 가장 좋아합니다.

각 개는 자신이 짖는 소리를 들을 수 있는 개들의 목록을 가지고 있습니다. 또한 각 개는 다른 개가 짖는 소리를 들었을 때 자신이 짖기까지 기다리는 지연 시간을 가집니다.

$1$ 번 개가 항상 가장 먼저 짖으며, 이 첫 짖음은 $0$ 초에 일어납니다.

소리는 한 개의 입에서 다른 개의 귀로 즉시 전달된다고 가정합니다. 당신의 임무는 $0$ 초부터 $T$ 초까지(양 끝 포함) 각 개가 몇 번 짖었는지 구하는 것입니다.

각 개는 매 초마다 자고 있거나, 기다리고 있거나, 짖고 있는 세 가지 상태 중 하나입니다. 개 $i$ 가 자고 있는 어떤 초 $n$ 에 짖는 소리를 들으면, 그 개는 깨어나 $n+1$ 초부터 $n+w_i-1$ 초까지(양 끝 포함) 기다린 뒤 $n+w_i$ 초에 짖고, $n+w_i+1$ 초부터 다시 잠듭니다. 만약 개가 기다리거나 짖고 있는 초에 짖는 소리를 들으면 그 소리를 무시합니다.

$0$ 초에는 $1$ 번 개를 제외한 모든 개가 자고 있습니다.

입력

첫 번째 줄에는 동네에 있는 개의 수 $D$ ( $1 \le D \le 1000$ )가 주어집니다.

이어지는 $D$ 개의 줄에는 각각 정수 $w_i$ ( $1 \le w_i \le 1000$ )가 주어지며, 이는 개 $i$ 가 짖는 소리를 들은 뒤 짖기까지 기다리는 시간(초)입니다.

그다음 줄에는 정수 $F$ ( $1 \le F \le 10000$ )가 주어집니다. 이어지는 $F$ 개의 줄에는 각각 두 정수 $i$ 와 $j$ 가 주어지며, 개 $i$ 가 짖으면 개 $j$ 가 그 소리를 듣는다는 뜻입니다. $i = j$ 인 경우는 절대 없습니다.

마지막 줄에는 개들을 관찰할 시간(초)인 정수 $T$ ( $1 \le T \le 1000$ )가 주어집니다.

출력

개 $1$ 번부터 개 $D$ 번까지 순서대로 각 개마다 한 줄씩 출력합니다. $i$ 번째 줄에는 $0 \le n \le T$ 인 초 $n$ 중 개 $i$ 가 짖은 초의 개수를 출력합니다.

예제2

예제 1
입력
```
3
1
1
3
3
1 2
2 3
3 1
10
```
예상 출력
```
3
2
2
```
예제 2
입력
```
3
3
1
3
3
1 2
2 3
3 1
10
```
예상 출력
```
2
2
1
```