Description

It is known that in the most recent $m$ tournaments, there have been $n$ players. Each of them is sponsored by a financial group and has signed a contract. Since this is a top secret of each group, the exact contract details are unknown, but Iron Fist spies have learned each player’s salary range through various channels (clearly, salaries are non-negative).
For the most recent $m$ $IF$ tournaments (numbered from $1$), after each tournament the league will settle accounts and use international financial methods to accurately compute the change in the total value sum of all league players for that tournament. In each tournament, some new players join, and some players lose their fighting ability during the tournament, are kicked out of the league, and exiled to the slums.
Now you are given the value range of each of the $n$ players, as well as the tournament index when they entered the league ($0$ means they were already in the league before tournament $m+1$) and the tournament index when they left the league ($0$ means they are still active). You are also given, for each of the most recent $m$ tournaments, the total value sum of league players in that tournament minus the value from the previous tournament.
Based on the information, please determine as accurately as possible the possible salary range for each player. The salary ranges of different players do not need to be simultaneously achievable. However, for every number within a given player’s range, there must exist at least one valid assignment in which that player can take that salary, and this range should be as wide as possible.
If the input information is wrong, output -1, meaning there is no solution.

Input Format

The first line contains a positive integer $m$, as described above.
The second line contains $m$ integers, where the $i$-th integer represents the change in the total value sum of players in tournament $i$.
The third line contains a positive integer $n$.
The next $n$ lines each contain four integers, representing the value lower bound, value upper bound, debut tournament, and retirement tournament, respectively. See the description for details.
It is guaranteed that the debut time is strictly earlier than the retirement time (except for $0$).

Output Format

If the input information is wrong, output only one line with an integer -1.
Otherwise output $n$ lines, each with two real numbers. The $i$-th line gives the exact possible range of the actual value of the $i$-th player, rounded to two decimal places.

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

1.00 2.00
2.00 3.00
1.00 1.00

Hint

Sample Explanation #1

In the second tournament, only player $3$ left, so we can determine that player $3$’s salary is $1$.
Then the sum of salaries of players $1$ and $2$ is $4$. Therefore, player $1$ can take at least $1$ and at most $2$; player $2$ can take at least $2$ and at most $3$.

Constraints

For $100\%$ of the testdata, $1 \le n \le 200$, $1 \le m \le 100$, and the given salary ranges do not exceed $20000$.

Translated by ChatGPT 5