짖는 개들!

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

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

$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$가 짖은 초의 개수를 출력합니다.