UOJ Logo

NOI.AC

3S 2048MB

#778. 坐火车

统计

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。