题目描述

徐老师某天一觉醒来，发现自己穿越到了辰辰采药的那天！

他陪着辰辰跟医师来到了一个到处都是草药的山里，山里一共有 $n$ 个草药洞，第 $i$ 个草药洞中只有一株价值为 $w_i$ 的草药，而辰辰采集这株草药需要花费时间为 $v_i$，现在医师要求辰辰在规定的时间内尽可能的采到价值最大的草药，才能让辰辰拜他为师。

作为穿越而来的徐老师，自然决定要帮助辰辰完成这个任务！

众所周知，穿越的时候总是会带着一些金手指，例如各种系统或者老爷爷，然而徐老师的金手指是两个技能——闪现和时间重置！

徐老师发现自己的闪现技能有一定的限制，并不能随意闪烁到任意一个草药洞，也不能无限次数的闪烁

首先，对于徐老师处于第 $i$ 个草药洞时，他只能闪现到他看得见的草药洞，这里我们可以用 $u_i,v_i$ 来表示第 $u_i$ 个草药洞可以看得见第 $v_i$ 个草药洞，根据光路可逆原理， $v_i$ 自然也能看得见 $u_i$，每次闪现消耗 $1$ 单位的时间，并且徐老师采药不花费时间

现在徐老师会选择一个洞穴作为起点，但是被医师发现了徐老师在帮助辰辰

于是医师要求辰辰不许进入山洞，只允许徐老师进入，并且给出的时间要求会发生变化！

而徐老师的第二个技能——时间重置，允许徐老师返回到出发前，并且徐老师一共会使用 $m$ 次

第 $i$ 次出发时徐老师会选择 $x_i$ 作为起点山洞，并且医师给出的时间限制为 $y_i$

请注意，徐老师必须要在规定时间内返回起点才算完成任务，否则草药价值全当 $0$ 算

输入格式

第一行包含一个整数 $n$ 表示有 $n$ 个草药洞

第二行包含 $n$ 个整数 $w_i$ 分别表示每一株草药的价值

接下来 $n$ 行，每行两个整数 $u_i,v_i$ 表示两个洞穴能够互相看见

接下来一行包含一个整数 $m$ 表示徐老师重置了 $m$ 次时间

接下来 $m$ 行每行两个整数 $x_i,y_i$ 表示第 $i$ 个次重置的起点洞穴编号是 $x_i$，此时医师设置的时间限制为 $y_i$

输出格式

输出共 $m$ 行，依次表示每个起点出发徐老师最多能采到的草药价值

数据范围

对于 $20\%$ 的测试数据，满足$1\leq n\leq 6,1\leq m\leq 10$

对于 $40\%$ 的测试数据，满足$1\leq n\leq 8,1\leq m\leq 100$

对于另 $20\%$ 的测试数据，满足$1\leq n\leq 30,1 \leq m \leq 10^5$, 起点 $x_i$ 总是 $1$

对于 $80\%$ 的测试数据，满足$1\leq n\leq 30,1\leq m\leq 10^5$

对于 $100\%$ 的测试数据，满足$1\leq n\leq 100,1\leq m\leq 10^5, 1 \leq y_i,w_i \leq 10^5$

特别的保证：输入数据保证无重边、自环，并且保证每个草药洞都可达。

样例输入

3
1 2 3
1 2
2 3
1 3
4
1 0
1 1
1 2
1 3

样例输出

1
1
4
6

样例解释

以 $1$ 为起点，时间为 $0$ 时，只能采到 $1$ 号草药，价值为 $1$

以 $1$ 为起点，时间为 $1$ 时，时间不够徐老师出去再回来，所以只能采到 $1$ 号草药，价值为 $1$

以 $1$ 为起点，时间为 $2$ 时，徐老师可以从 $1$ 号闪现到 $3$ 号，再回到 $1$ 号，草药价值为 $1+3=4$

以 $1$ 为起点，时间为 $3$ 时，徐老师可以按照 $1->2->3->1$ 的顺序闪现，草药价值为 $1+2+3=6$