P6129 [JSOI2012] Iron Fist

After the terrible Third World War, national governments collapsed, and major financial groups took the chance to seize control of the world. After years of war, eight major groups survived and each occupied a region. The strongest of them was Iron Fist, which controlled North America. In the civilized area maintained by the Iron Fist group, there is a most glorious and important tournament—`Iron Fist`, also known as the Iron Fist Tournament. $IF$ brings together top fighters from all over the world, heavily sponsored by various groups, all aiming to win `IF Champion` and gain supreme honor, and of course the power that comes with it. Everything was orderly at first, but a boy from the slums, Kazama Jin, unexpectedly defeated an official $IF$ competitor in the preliminary round and obtained a place in the finals. From then on, the situation was disrupted... To deal with this sudden variable, the $IF$ management decided to evaluate all players in the league first, so as to better control the overall situation.

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.

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$).

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.

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