Chadman wanted to surprise his girlfriend on the occasion of valentine's day. So he decided to give a task to his girlfriend who loved to eat dates. He divided the VNIT campus into n nodes, and kept some amount of dates in every node. Now he takes his girlfriend randomly to any node. VNIT being a very big campus, his girlfriend can go to only those nodes which are atmost k hopcounts away from the node where chadman is standing.Can you tell how many dates will his date be able to get?
INPUT:- The first input line consists of an integer n denoting number of nodes. For next line consist of n space separated integers d1 , d2 , d3 ......... dn where di represents number of dates in ith node.
Next line consist of an integer m representing number of edges. Next m lines consist of 2 integers nodeId1 ,nodeId2 between whom an edge exists. All edges have the same weight.
Next line consist of an integer q representing number of queries. Next q lines consists of two integers x and y where x represent node id and no. of hopcounts respectively.
OUTPUT:- For each query print the total number of dates found .
CONSTRAINTS:-
1<=n<=100
1<= di
1<=q<=n
1<=m<=n*(n-1)/2