Signaux de fumée

Si vous avez lu Lucky Luke lorsque vous étiez petit, vous savez sûrement que les indiens communiquent à l'aide de petits nuages de fumée. Les nuages de fumée se voient de loin (surtout dans les grandes plaines américaines), et en utilisant plusieurs faiseurs de nuages qui reproduisent les signaux qu'ils observent, un message peut parcourir des dizaines de kilomètres en très peu de temps. Quand on y pense, c'était un moyen de communication plutôt efficace (du temps où il fallait choisir entre de la fumée ou des pigeons).

En fait, le seul vrai problème avec les signaux de fumée, c'est le mauvais temps, qui réduit considérablement la visibilité des signaux. Vous êtes le chef de la tribu, et vous souhaitez prévoir précisement le nombre de membres de votre tribu que vous ne pourrez pas joindre les jours de mauvais temps.

Vous disposez d'un plan de la région (une carte 2D) qui indique la position exacte de tous les faiseurs de nuages de votre tribu, dont celui qui se trouve à côté de vous dans le camp principal, et à qui vous dictez les messages à transmettre.

Lorsqu'un faiseur de nuages voit un signal de fumée, il le réémet immédiatement, afin de transmettre le message à d'autres camps.

Grâce aux pouvoirs du grand Chamane de votre tribu, vous disposez de prédictions météo pour les jours qui viennent. Chaque prédiction est donnée sous la forme d'un nombre entier : la distance maximale à laquelle un signal de fumée pourra être vu ce jour là.

Votre objectif est de déterminer, pour chaque jour pour lequel vous disposez de ces prédictions, le nombre de faiseurs de nuages qui ne recevront pas vos messages ce jour là (directement ou indirectement).

Remarque : un faiseur de fumée se trouvant exactement à la distance maximale d'un deuxième, voit les signaux de celui-ci (et réciproquement).

• 2 <= N <= 1 000, où N est le nombre de faiseurs de signaux de fumées.
• -65 000 <= X,Y <= 65 000, où X et Y sont des coordonnées entières.
• 0 <= D <= 200 000, où D est une distance de visibilité.
• 0 <= M <= 10 000, où M est le nombre de jours pour lesquels vous disposez de prédictions météorologiques.

Remarque : dans 50% des tests, on aura N <= 100 et M <= 100.

Remarque : le faiseur de fumée correspondant au camp principal est le premier des faiseurs de fumée que l'on vous donne sur l'entrée standard.

• La première ligne contient un entier N, le nombre de faiseurs de fumée.
• Les N lignes suivantes contiennent deux entiers chacune X et Y décrivant les coordonnées d'un faiseur de fumée.
• La ligne suivante contient un entier M : le nombre de jours considérés.
• Les M lignes suivantes contiennent chacune un entier : la distance D_i de visibilité de chaque jour i.

Vous devez afficher M lignes avec un entier chacune : pour chaque jour dans l'ordre de l'entrée, le nombre de faiseurs de nuages injoignables.

Le premier jour, le ciel est assez nuageux, et les signaux ne peuvent être vus que jusqu'à une distance de 10km. Seul le numéro 2 reçoit le message. Il le réémet, mais personne d'autre que le 1 ne peut voir ses signaux. Il reste donc 4 faiseurs de nuages qui ne reçoivent rien.

Le deuxième jour, le temps est mauvais, et on ne voit les signaux que jusqu'à une distance de 7km. Personne ne voit les signaux émis par le numéro 1. Cinq faiseurs de nuages n'ont donc rien reçu.

Le troisième jour, le ciel est dégagé, et la distance à laquel un signal peut être vu est de 17km. Le message émis par le faiseur de fumée 1 peut être vu directement par les numéros 2 et 3. Le numéro 4 peut voir le message retransmis par le numéro 2. Le numéro 5 voit alors le message retransmis par le 4. Le 3 et le 5 retransmettent aussi leur message, mais ce n'est pas suffisant pour qu'il soit vu par le faiseur de fumée 6. C'est le seul faiseur de nuages qui ne reçoit pas le message.