Xiao A and Xiao B decide to go on a trip during their vacation. They number the cities they want to visit from $1$ to $N$, where cities with smaller numbers are located to the west of cities with larger numbers. It is known that the altitudes of all cities are distinct. Let $H_i$ be the altitude of city $i$. The distance $d[i,j]$ between city $i$ and city $j$ is exactly the absolute difference of their altitudes, i.e., $d[i,j]=|H_i-H_j|$.

During the trip, Xiao A and Xiao B take turns driving, with Xiao A driving on the first day, and then alternating each day. They plan to choose a city $S$ as the starting point and travel eastward, ending the trip after traveling at most $X$ kilometers. Xiao A and Xiao B have different driving styles: Xiao B always chooses the nearest city in the forward direction as the destination, while Xiao A always chooses the second-nearest city in the forward direction as the destination (Note: in this problem, if the distances from the current city to two other cities are the same, the city with the lower altitude is considered closer). If, on any day, choosing a destination according to their respective principles would result in a total distance traveled exceeding $X$ kilometers, they end the trip.

Before setting off, Xiao A wants to know two things:

1. For a given $X=X_0$, from which city should they start so that the ratio of the total distance driven by Xiao A to the total distance driven by Xiao B is minimized (if Xiao B's total distance is 0, the ratio is considered infinite, and two infinities are considered equal). If there are multiple such cities, output the one with the highest altitude.
2. For any given $X=X_i$ and starting city $S_i$, the total distance driven by Xiao A and the total distance driven by Xiao B.

Input

The first line contains an integer $N$, representing the number of cities.

The second line contains $N$ integers, separated by spaces, representing the altitudes of cities 1 to $N$, i.e., $H_1, H_2, \ldots, H_n$, where each $H_i$ is distinct.

The third line contains an integer $X_0$.

The fourth line contains an integer $M$, representing the number of pairs of $S_i$ and $X_i$.

The next $M$ lines each contain 2 integers $S_i$ and $X_i$, representing a trip starting from city $S_i$ with a maximum travel distance of $X_i$.

Output

The output consists of $M+1$ lines.

The first line contains an integer $S_0$, representing the starting city that minimizes the ratio of Xiao A's total distance to Xiao B's total distance for the given $X_0$.

The next $M$ lines each contain 2 integers, separated by a space, representing the total distance driven by Xiao A and the total distance driven by Xiao B for the given $S_i$ and $X_i$.

Examples

Examples 1 Input

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

Examples 1 Output

1
1 1
2 0
0 0
0 0

Examples 1 Note

The altitudes of the cities and the distances between them are shown in the figure above.

If starting from city 1, the reachable cities are 2, 3, and 4. The distances from city 1 to these cities are 1, 1, and 2, respectively. Since the altitude of city 3 is lower than that of city 2, city 3 is considered closer to city 1 than city 2. Thus, city 2 is the second-nearest, and Xiao A will drive to city 2. After arriving at city 2, the reachable cities are 3 and 4, with distances 2 and 1, respectively. City 4 is the nearest to city 2, so Xiao B will drive to city 4. After arriving at city 4, there are no more reachable cities, so the trip ends.

If starting from city 2, the reachable cities are 3 and 4, with distances 2 and 1, respectively. Since city 3 is the second-nearest to city 2, Xiao A will drive to city 3. After arriving at city 3, the only remaining city is 4, which is the nearest to city 3. However, the total distance would be $2+3=5 > 3$, so Xiao B ends the trip at city 3.

If starting from city 3, the only reachable city is 4. Since there is no second-nearest city, the trip ends before it begins.

If starting from city 4, there are no reachable cities, so the trip ends before it begins.

Examples 2 Input

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

Examples 2 Output

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

Examples 2 Note

When $X=7$:

• If starting from city 1, the route is $1 \to 2 \to 3 \to 8 \to 9$. Xiao A's distance is $1+2=3$, and Xiao B's distance is $1+1=2$. (At city 1, the nearest cities are 2 and 6, but city 2 has a higher altitude, so it is considered the second-nearest, thus Xiao A chooses city 2; after reaching 9, Xiao A only has city 10 to go to, but no second choice, so the trip ends.)
• If starting from city 2, the route is $2 \to 6 \to 7$. Xiao A's distance is 2, and Xiao B's distance is 4.
• If starting from city 3, the route is $3 \to 8 \to 9$. Xiao A's distance is 2, and Xiao B's distance is 1.
• If starting from city 4, the route is $4 \to 6 \to 7$. Xiao A's distance is 2, and Xiao B's distance is 4.
• If starting from city 5, the route is $5 \to 7 \to 8$. Xiao A's distance is 5, and Xiao B's distance is 1.
• If starting from city 6, the route is $6 \to 8 \to 9$. Xiao A's distance is 5, and Xiao B's distance is 1.
• If starting from city 7, the route is $7 \to 9 \to 10$. Xiao A's distance is 2, and Xiao B's distance is 1.
• If starting from city 8, the route is $8 \to 10$. Xiao A's distance is 2, and Xiao B's distance is 0.
• If starting from city 9, the route is 9. Xiao A's distance is 0, and Xiao B's distance is 0.
• If starting from city 10, the route is 10. Xiao A's distance is 0, and Xiao B's distance is 0.

Starting from city 2 or city 4 minimizes the ratio, but city 2 has a higher altitude, so the first line of output is 2.

Constraints

For 30% of the data, $1 \le N \le 20$, $1 \le M \le 20$;

For 40% of the data, $1 \le N \le 100$, $1 \le M \le 100$;

For 50% of the data, $1 \le N \le 100$, $1 \le M \le 1,000$;

For 70% of the data, $1 \le N \le 1,000$, $1 \le M \le 10,000$;

For 100% of the data, $1 \le N \le 100,000$, $1 \le M \le 100,000$, $-1,000,000,000 \le H_i \le 1,000,000,000$, $0 \le X_0 \le 1,000,000,000$, $1 \le S_i \le N$, $0 \le X_i \le 1,000,000,000$. It is guaranteed that all $H_i$ are distinct.