该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

inqwq23 学姐原本打算出一道非常复杂的模拟题，但她突然善心大发，把题目换成了这道题。

现在 inqwq23 学姐想和 Handy 学姐乘坐城铁前往 C 城。

题目描述

友情提示：本题若使用枚举，则不能在规定时间内(1000ms)通过评测，详见本题“提示”部分。

假设城铁的线路是一条线段，inqwq23 和 Handy 从位于原点的车站出发，$0$ 号车站之后共有 $n$ 座车站。第 $0$ 号车站到第 $i$ 号车站的距离是 $a_i$ 米，从 $0$ 号车站坐到 $i$ 号车站的票价为（元）：

“ $\left \lfloor \right \rfloor$ ”表示向下取整。 $p$ ， $q$ 为 正实数 ，输入数据保证对于任意 $i$ 有 $S(i)\le 10^9$ 。

inqwq23 和 Handy 希望在编号在区间 $[l,r]$ 内的车站下车，同时因为两位学姐太穷了，所以最高只能接受 $y$ 元的票价。现在请你帮帮两位学姐，判断她们能否买到合适的车票，如果能，最远能坐到哪个车站。

输入格式

第一行一个正整数 $n(1\le n\le 10^6)$ ，表示 $0$ 号车站之后的车站数量；

第二行 $n$ 个正整数 $a_i$ ，用空格隔开，保证 $1\le a_i\le 10^9$ 且 $a_i\le a_{i+1}$ ；

第三行一个正整数 $t(1\le t\le 10^4)$ ，表示接下来有 $t$ 次询问，每次询问单独一行：

• 两个 正实数 $p,q$ （范围见题目描述）和三个正整数 $l,r,y(1\le l\le r\le n,0\le y\le 10^9)$ ，用空格隔开。

输入数据共 $t+3$ 行。

输出格式

对于每次询问，单独输出一行，如果不能买到合适的车票，输出 -1 ，否则输出最远能到达的车站编号。

样例数据

输入 #1

5
2 8 18 21 26
2
0.2 5 2 4 7
1 2 4 5 15

输出 #1

2
-1

解释 #1

对于第一次询问，到 5 个车站的总票价分别为 5，6，8，9，10；

对于第二次询问，到 5 个车站的总票价分别为 4，10，20，23，28。

提示

要做对本题目，你需要学会以下知识：

1. 数组；

2. 二分（OI Wiki）。