题目描述

最近陶陶在研究树的结构，某天他想出了一个看似简单的问题：

给出一颗 $n$ 个结点的树，树中每个结点有四个正实数参数值，第 $i$ 个结点的参数值分别用 $x_i,y_i,p_i,q_i$ 表示。

给出 $m$ 次询问，每次询问给出两个点 $a,b$ ，设 $i,j$ 为 $a,b$ 两点的树上路径上的任意两点（可以相同），要求回答 $\frac{y_i + q_j}{x_i + p_j}$ 的最大值。

输入格式

第一行包含一个正整数 $n$ ，表示树中结点的个数。

第二行包含 $n$ 个正实数，第 $i$ 个数表示 $x_i$ 。

第三行包含 $n$ 个正实数，第 $i$ 个数表示 $y_i$ 。

第四行包含 $n$ 个正实数，第 $i$ 个数表示 $p_i$ 。

第五行包含 $n$ 个正实数，第 $i$ 个数表示 $q_i$ 。

接下来有 $n-1$行，每行包含两个正整数 $a,b$ ，表示结点 $a,b$ 之间有一条边。

第 $n+5$ 行包含一个正整数 $m$ ，表示询问次数。

最后 $m$ 行，每行包含正整数 $a,b$ ，表示一次询问。

输出格式

共 $m$ 行，每行一个实数，第 $i$ 行的数表示第 $i$ 次询问的答案。

只要你的输出和标准输出相差不超过 $10^{-3}$ 即认为正确。

5
3.0 1.0 2.0 5.0 4.0
5.0 2.0 4.0 3.0 1.0
1.0 3.0 2.0 4.0 5.0
3.0 4.0 2.0 1.0 4.0
1 2
1 3
2 4
2 5
4
2 3
4 5
2 4
3 5

2.5000
1.5000
1.5000
2.5000

数据规模与约定

对于 $100\%$ 的数据 ，$n,m \le 3\times 10^4 , 1\le x_i,y_i,p_i,q_i\le 10^8 , 1\le a,b\le n$ 。