Problem Description

Xiao A and Xiao B have decided to travel during their vacation. They have numbered the cities they want to visit from 1 to \( n \), with cities having smaller numbers being to the west of those with larger numbers. Each city has a unique altitude, denoted as \( h_i \) for city \( i \). The distance \( d_{i,j} \) between city \( i \) and city \( j \) is exactly the absolute difference in their altitudes, i.e., \( d_{i,j} = |h_i - h_j| \).

During the trip, Xiao A and Xiao B take turns driving, starting with Xiao A on the first day, and alternating each subsequent day. They plan to start from a city \( s \) and travel eastward, ending their 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 chooses the second nearest city in the forward direction (note: if the distances to two cities are the same, the city with the lower altitude is considered closer). If either cannot choose a destination according to their rules, or reaching the destination would exceed the total distance of \( x \) kilometers, they will end the trip.

Before starting, 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 distance is 0, the ratio can be considered infinite, and two infinities are considered equal). If multiple cities result in the same minimum ratio, the city with the highest altitude should be chosen.

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 Format

The first line contains an integer \( n \), the number of cities.

The second line contains \( n \) integers separated by spaces, representing the altitudes \( h_1, h_2, \ldots, h_n \) of the cities, with each \( h_i \) being unique.

The third line contains an integer \( x_0 \).

The fourth line contains an integer \( m \), the number of given \( s_i \) and \( x_i \) pairs.

The next \( m \) lines each contain two integers \( s_i \) and \( x_i \), indicating the starting city and the maximum distance for that trip.

Output Format

The output consists of \( m+1 \) lines.

The first line contains an integer \( s_0 \), indicating the city from which to start for the given \( x_0 \) to minimize the ratio of distances driven by Xiao A and Xiao B.

The next \( m \) lines each contain two integers separated by a space, representing the total distance driven by Xiao A and the total distance driven by Xiao B for each given \( s_i \) and \( x_i \).

Sample Input and Output

Input Sample #1

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

Output Sample #1

1 
1 1 
2 0 
0 0 
0 0 

Input Sample #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

Output Sample #2

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

Notes/Hints

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 1000 \).

For 70% of the data, \( 1 \le n \le 1000, 1 \le m \le 10^4 \).

For 100% of the data, \( 1 \le n, m \le 10^5 \), \( -10^9 \le h_i \le 10^9 \), \( 1 \le s_i \le n \), \( 0 \le x_i \le 10^9 \).

The data guarantees that \( h_i \) are all distinct.

见题面 Input 部分

见题面 Output 部分