Barking Dogs!

You live in a neighbourhood full of dogs. Dogs like dogs, and they like barking even more — but best of all, dogs love to bark when other dogs bark.

Each dog has a set of dogs that can hear it bark. Each dog also has a delay: the time it waits before barking after it hears another dog bark.

Dog $1$ always barks first, and this first bark happens during second $0$.

Assume that sound travels instantly from one dog's mouth to another dog's ear. Your job is to determine how many times each dog barks during seconds $0$ through $T$ inclusive.

In any given second, each dog is doing exactly one of three things: sleeping, waiting, or barking. If dog $i$ hears a bark during a second $n$ while it is sleeping, it wakes up, waits during seconds $n+1$ through $n+w_i-1$ inclusive, barks during second $n+w_i$, and then goes back to sleep from second $n+w_i+1$ onward. If a dog hears a bark during a second in which it is waiting or barking, it ignores that bark.

During second $0$, every dog except Dog $1$ is sleeping.

The first line contains $D$ ($1 \le D \le 1000$), the number of dogs in the neighbourhood.

Each of the next $D$ lines contains an integer $w_i$ ($1 \le w_i \le 1000$), the time in seconds that dog $i$ waits before barking after it hears a bark.

The next line contains $F$ ($1 \le F \le 10000$). Each of the next $F$ lines contains two integers $i$ and $j$, meaning that when dog $i$ barks, dog $j$ hears it. It is never the case that $i = j$.

The last line contains the integer $T$ ($1 \le T \le 1000$), the number of seconds during which you monitor the dogs.

Print one line for each dog, in order from dog $1$ to dog $D$. On line $i$, print the number of seconds $n$ with $0 \le n \le T$ during which dog $i$ barked.