Determining Maximum Salary Ranges

There are n players who have appeared in the last m competitions. In each competition (numbered from 1 to m), the union performs a financial clearing and obtains the change in the total salary of all players compared with the previous competition. On each competition, some new players join the union and some players lose their fighting ability and are removed.

Each player has a fixed, nonnegative salary. However, the contracts are secret so the only available information is as follows:

• For each player, two numbers are given: the competition in which the player joined the union and the competition in which the player left the union. A value of 0 for the join time indicates that the player was already in the union before the first competition. A value of 0 for the leave time indicates that the player is still in the union (i.e. current).
• For each competition j (from 1 to m), an integer \(\delta_j\) is given which equals the difference between the total salary of the union in the current competition and that in the previous competition.

For a player who joins in competition j (j > 0), his salary appears as a positive term in the equation for competition j. For a player who leaves in competition j (j > 0), his salary appears as a negative term in the equation for competition j. (A player may appear in two competitions if he joins at one and later leaves in another.)

For each competition j, let Aj be the set of players with join time exactly j and Bj be the set of players with leave time exactly j. Then the following equation must hold:

[ \sum_{i \in A_j} x_i - \sum_{i \in B_j} x_i = \delta_j, \quad \text{for } j=1,2,\dots,m. ]

Note that:

• If an event has only joiners (i.e. Bj = \emptyset) then \(\delta_j \ge 0\), and the salaries of players joining in that competition are forced to satisfy \(\sum_{i\in A_j} x_i = \delta_j\). Hence, each such player can get at most \(\delta_j\) (when all the other joiners receive 0) and at least \(0\).
• If an event has only leavers (i.e. Aj = \emptyset) then \(\delta_j \le 0\) and \(\sum_{i\in B_j} x_i = -\delta_j\); thus each such player can receive at most \(-\delta_j\) (when all the other leavers receive 0) and at least \(0\).
• If an event has both joiners and leavers, then the equation has enough degrees of freedom so that no finite bound can be deduced for the players appearing in that event.
• A player that does not appear in any equation (i.e. join time = 0 and leave time = 0) has no constraint apart from nonnegativity, and so his salary can be arbitrarily high.

Your task is to deduce, for each player, the widest possible range \([L_i,R_i]\) (with \(L_i \le x_i \le R_i\)) such that for any \(x_i\) in this range there exists an assignment for the other players (all \(\ge 0\)) satisfying all the equations. In other words, even if the ranges for different players may not be simultaneously achievable, every number in a player’s individual range must be achievable for that player in some valid assignment.

If the input is inconsistent (i.e. no solution exists), output -1.

inputFormat

The first line contains two integers m and n (m, n ≥ 1), representing the number of competitions and the number of players, respectively.

The next n lines each contain two integers ji and li (0 ≤ ji, li ≤ m), where:

• ji is the competition in which player i joined the union (0 means before competition 1),
• li is the competition in which player i left the union (0 means the player is still active).

The last line contains m integers \(\delta_1, \delta_2, \dots, \delta_m\), where \(\delta_j\) is the difference between the total salary in competition j and that in competition j-1.

outputFormat

If the input data is inconsistent (i.e. no valid salary assignment exists), output a single line containing -1. Otherwise, output n lines. The i-th line should contain two space-separated values Li and Ri, representing the widest possible range for the salary of player i. If the upper bound is unbounded, output the word Infinity in its place.

sample

2 3
0 0
1 0
0 2
100 -50

0 Infinity
0 100
0 50

</p>