题目描述

城市从西到东编号1..N，海拔H_i互不相同，距离d(i,j)=|H_i-H_j|。从某城市出发，小A先开车，小A、小B交替各走一段。每次只能选择编号严格大于当前位置的城市。

在所有东部城市中，按距离从小到大排序；距离相等时，海拔较低的城市排在前面。小A必须选择第二近的城市，小B必须选择最近的城市。若当前司机没有所需名次的城市，旅行立即结束；不能用最近城市替代第二近城市。若按该规则选定的下一段会使两人累计行驶距离超过预算X，也立即结束，不尝试其他目的地；恰好用尽预算可完成该段。

给定X0，找一个出发城市，使按上述规则旅行时小A总路程与小B总路程之比最小。小B路程为0时，比值定义为正无穷（包括两人均为0的情形）。比值相同选择海拔更高的出发城市。另有M组起点及预算，分别求两人的路程。

输入

第一行N，第二行N个互异海拔H_i。第三行X0，第四行M，随后M行S_i、X_i。

输出

第一行最优起点编号。随后M行每行小A、小B行驶路程，先A后B。

数据范围

1≤N≤100000，1≤M≤10000，-10^9≤H_i≤10^9；0≤X0,X_i≤10^9，1≤S_i≤N，海拔互不相同。距离及累计路程使用64位整数。

输入样例 1

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

输出样例 1

1
1 1
2 0
0 0
0 0

输入样例 2

10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7

输出样例 2

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