题目描述

小 A 和小 B 决定利用假期外出旅行，他们将想去的城市从 $\red 1$ 到 $\red N$ 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 $\red i$ 的海拔高度为 $\red {H_i}$，城市 $\red i$ 和城市 $\red j$ 之间的距离 $\red {d_{i, j}}$ 恰好是这两个城市海拔高度之差的绝对值，即 $\red {d_{i, j} = |H_i - H_j|}$。

旅行过程中，小 A 和小 B 轮流开车，第一天小 A 开车，之后每天轮换一次。他们计划选择一个城市 $\red S$ 作为起点，一直向东行驶，并且最多行驶 $\red X$ 公里就结束旅行。小 A 和小 B 的驾驶风格不同，小 B 总是沿着前进方向选择一个最近的城市作为目的地，而小 A 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 $\red X$ 公里，他们就会结束旅行。

在启程之前，小 A 想知道两个问题：

1. 对于一个给定的 $\red {X = X_0}$，从哪一个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 $\red 0$，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
2. 对任意给定的 $\red {X = X_i}$ 和出发城市 $\red {S_i}$，小 A 开车行驶的路程总数以及小 B 行驶的路程总数。

输入格式

第一行包含一个整数 $\red N$，表示城市的数目。

第二行有 $\red N$ 个整数，每两个整数之间用一个空格隔开，依次表示城市 $\red 1$ 到城市 $\red N$ 的海拔高度，即 $\red {H_1, H_2, \dots, H_n}$，且每个 $\red {H_i}$ 都是不同的。

第三行包含一个整数 $\red {X_0}$。

第四行为一个整数 $\red M$，表示给定 $\red M$ 组 $\red {S_i}$ 和 $\red {X_i}$。

接下来的 $\red M$ 行，每行包含 $\red 2$ 个整数 $\red {S_i}$ 和 $\red {X_i}$，表示从城市 $\red {S_i}$ 出发，最多行驶 $\red {X_i}$ 公里。

输出格式

第一行包含一个整数 $\red {S_0}$，表示对于给定的 $\red {X_0}$，从编号为 $\red {S_0}$ 的城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小。

接下来的 $\red M$ 行，每行包含 $\red 2$ 个整数，之间用一个空格隔开，依次表示在给定的 $\red {S_i}$ 和 $\red {X_i}$ 下小 A 行驶的里程总数和小 B 行驶的里程总数。

样例

样例输入 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

样例 1 解释

各个城市的海拔高度以及两个城市间的距离如上图所示。

• 如果从城市 $\red 1$ 出发，可以到达的城市为 $\red{ 2，3，4}$，这几个城市与城市 $\red 1$ 的距离分别为 $\red {1，1，2}$，但是由于城市 $\red 3$的海拔高度低于城市 $\red 2$，所以我们认为城市 $\red 3$ 离城市 $\red 1$ 最近，城市 $\red 2$ 离城市 $\red 1$ 第二近，所以小 A 会走到城市 $\red 2$。到达城市 $\red 2$ 后，前面可以到达的城市为 $\red {3，4}$，这两个城市与城市 $\red 2$ 的距离分别为 $\red {2，1}$，所以城市 $\red 4$离城市 $\red 2$ 最近，因此小 B 会走到城市 $\red 4$。到达城市 $\red 4$ 后，前面已没有可到达的城市，所以旅行结束。
• 如果从城市 $\red 2$ 出发，可以到达的城市为 $\red {3，4}$，这两个城市与城市 $\red 2$ 的距离分别为 $\red {2，1}$，由于城市 $\red 3$离城市 $\red 2$第二近，所以小 A 会走到城市 $\red 3$。到达城市 $\red 3$后，前面尚未旅行的城市为 $\red 4$，所以城市 $\red 4$离城市 $\red 3$最近，但是如果要到达城市 $\red 4$，则总路程为 $\red {2+3=5>3}$，所以小 B 会直接在城市 $\red 3$ 结束旅行。
• 如果从城市 $\red 3$出发，可以到达的城市为 $\red 4$，由于没有离城市 $\red 3$ 第二近的城市，因此旅行还未开始就结束了。
• 如果从城市 $\red 4$出发，没有可以到达的城市，因此旅行还未开始就结束了。

样例输入 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

样例 2 解释

当 $\red {X = 7}$ 时，

• 如果从城市 $\red {1}$ 出发，则路线为 $\red {1 → 2 → 3 → 8 → 9}$，小 A走的距离为 $\red {1+2=3}$，小 B 走的距离为 $\red {1+1=2}$。（在城市 $\red {1 }$时，距离小 A 最近的城市是 $\red {2 }$和$\red { 6}$，但是城市 $\red {2 }$的海拔更高，视为与城市 $\red {1}$ 第二近的城市，所以小 A 最终选择城市 $\red {2}$;走到 $\red {9}$ 后，小 A 只有城市 $\red {10 }$可以走，没有第 $\red {2 }$选择可以选，所以没法做出选择，结束旅行）
• 如果从城市 $\red {2 }$出发，则路线为 $\red {2 → 6 → 7}$，小 A 和小 B 走的距离分别为 $\red {2，4}$。
• 如果从城市 $\red {3 }$出发，则路线为 $\red {3 → 8 → 9}$，小 A 和小 B 走的距离分别为 $\red {2，1}$。
• 如果从城市 $\red {4 }$出发，则路线为 $\red {4 → 6 → 7}$，小 A 和小 B 走的距离分别为 $\red {2，4}$。
• 如果从城市 $\red {5 }$出发，则路线为 $\red {5 → 7 → 8}$，小 A 和小 B 走的距离分别为 $\red {5，1}$。
• 如果从城市 $\red {6 }$出发，则路线为 $\red {6 → 8 → 9}$，小 A 和小 B 走的距离分别为 $\red {5，1}$。
• 如果从城市 $\red {7 }$出发，则路线为 $\red {7 → 9 → 10}$，小 A 和小 B 走的距离分别为 $\red {2，1}$。
• 如果从城市 $\red {8 }$出发，则路线为 $\red {8 → 10}$，小 A 和小 B 走的距离分别为 $\red {2，0}$。
• 如果从城市 $\red {9 }$出发，则路线为 $\red {9}$，小 A 和小 B 走的距离分别为 $\red {0，0}$（旅行一开始就结束了）。
• 如果从城市 $\red {10}$ 出发，则路线为 $\red {10}$，小 A 和小 B 走的距离分别为 $\red {0，0}$。

从城市 $\red {2 }$或者城市 $\red {4}$ 出发小 A 行驶的路程总数与小 B 行驶的路程总数的比值都最小，但是城市 $\red {2}$ 的海拔更高，所以输出第一行为 $\red {2}$。

数据范围与提示

对于 $\red {30\%}$ 的数据，有 $\red {1 \leq N \leq 20，1 \leq M \leq 20}$；

对于 $\red {40\%}$ 的数据，有 $\red {1 \leq N \leq 100，1 \leq M \leq 100}$；

对于 $\red {50\%}$ 的数据，有 $\red {1 \leq N \leq 100，1 \leq M \leq 1\,000}$；

对于 $\red {70\%}$ 的数据，有 $\red {1 \leq N \leq 1\,000，1 \leq M \leq 10\,000}$；

对于 $\red {100\%}$的数据，有 $\red {1 \leq N \leq 100\,000，1 \leq M \leq 10\,000，|H_i| \leq 10^9，0 \leq X_i \leq 10^9\,\,\forall i \geq 0，1 \leq S_i \leq N\,\,\forall i \geq 1}$，数据保证 $\red {H_i}$ 各不相同。