Description

在某一个平行宇宙中，特朗普成了最受欢迎的总统，底特律成了美国最宜居的城市，纽约重修了地铁，怀俄明成了美国人口密度最高的州，然而更重要的是：旧金山到波士顿通了高铁，由美国联合铁道公司运行。

你喜欢上了坐高铁，从旧金山到波士顿的路上有很多城市，这些城市可以看成一个长度为$n$的序列，每一个数表示经过城市能给你带来的愉悦值。

你希望找一段区间，使得经过这些区间中的城市，能给你带来的愉悦值的平均值尽量大。

同时，美国联合铁道公司有一个特殊活动，某一些城市是这个公司的枢纽，如果你的区间中包含了至少两个枢纽，你可以获得奖励。你当然想获得奖励。

有$m$次询问，每次询问给定一段区间$[l, r]$，下标从1开始，保证$l < r$且城市$l$和城市$r$都是枢纽。你想知道如果你选择$[l, r]$的一个至少包含两个枢纽的子区间（可以等于询问区间），愉悦值的平均值最大能是多少。你选择的区间的端点不一定是枢纽。

Task

Input

第一行一个正整数$n$，表示城市的个数。

接下来一行$n$个正整数，表示每个城市的愉悦值。

接下来一行一个长度为$n$的01串，第$i$个字符为1表示第$i$个城市有枢纽，否则表示没有。

接下来一行一个正整数$m$，表示询问次数。

接下来$m$行，每行两个数$l, r$，表示询问的区间为$[l, r]$，保证$l < r$且城市$l$和城市$r$都是枢纽。

Output

输出$m$行，表示每个询问的答案。你的答案和标准答案的相对误差和绝对误差的较小值不能超过$10 ^ {-9}$。

Sample 1

5
5 4 3 4 5
10101
2
1 3
1 5

4
4.2

Explanation

对于第一个询问，答案区间为$[1, 3]$，虽然$[1, 5]$更优但是它们不被询问区间$[1, 3]$包含。

对于第二个询问，答案区间为$[1, 5]$，注意答案区间可以包含多于两个枢纽。

Sample 2

见样例数据下载，注意你的答案区间的端点可以不是枢纽。

Constraint

对于 $10\%$ 的数据，$1 \le n, m \le 300$。

对于 $30\%$ 的数据，$1 \le n \le 5,000$。

对于另外 $20\%$ 的数据，$1 \le m \le 100$。

对于另外 $20\%$ 的数据，枢纽的数目不超过10。

对于 $100\%$ 的数据，$1 \le n, m \le 500,000$，愉悦值为1到$10 ^ 9$之间的整数。

时间限制3s，空间限制2G。