Description

Bingbing has three toys: Pikachu, Weini Sun Wukong, and a Barbie doll. She does not know their exact weights (in NOI units), but she knows an approximate range for each toy, as shown below:

Table 1. Toys and their minimum and maximum possible weights|Pikachu|Weini Sun Wukong|Barbie doll :-:|:-:|:-:|:-: Minimum possible weight|$1$|$2$|$3$ Maximum possible weight|$3$|$4$|$5$

These ranges are too coarse, and Bingbing wants to narrow them down.

Jiajia happens to have a digital balance. It can tell not only whether the two sides are equal in weight, but also by how much the left side is heavier (or lighter) than the right. The balance is large; either side can hold any number of toys.

Bingbing borrows the balance and hopes to determine the exact weight of each toy. To test her, Jiajia allows her to place any toy on the left side and on the right side at most once each. For example, if she has ever placed Pikachu on the left side, she cannot place Pikachu on the left side again. Bingbing agrees. She performs two weighings, and the results are as follows (the number indicates how much heavier the left side is than the right):

From the results and Table 1, it can be determined that the weights of the three toys must be $3, 4, 3$. That is, the updated ranges obtained from the weighings are:

Bingbing will buy many more toys in the future and does not want to compute the weight of each toy by hand every time. She needs a program to compute the most precise lower and upper bounds of each toy’s weight. Can you help her?

Input Format

The first line contains two integers $n$ and $m$, the number of toys and the number of weighings.

The second line contains $2n$ numbers. For each $i$, the $(2i-1)$-th and $2i$-th numbers are the initial lower bound and upper bound of the weight of toy $i$.

Each of the following $m$ lines starts with three numbers $L, R, D$, denoting the number of toys on the left, the number of toys on the right, and the weight difference between the two sides (left minus right, with $L, R \ge 0$). The next $L$ numbers are the indices of the toys on the left side of the balance, followed by $R$ numbers for the right side. The input guarantees that each toy appears on each side of the balance at most once in total.

Output Format

Output $2n$ integers. For each $i$, the $(2i-1)$-th and $2i$-th numbers are the lower and upper bounds of toy $i$’s weight, i.e., the minimum possible integer weight and the maximum possible integer weight. If there is no solution (the balance might be broken), output only $-1$.

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

3 3 4 4 3 3

3 1
1 5 2 5 1 3
2 1 1 1 2 3

1 2 2 3 2 3

Hint

Sample explanation:

Sample $1$ corresponds to the example in the problem statement.

In sample $2$, Bingbing has three toys with initial ranges $1 \sim 5$, $2 \sim 5$, and $1 \sim 3$. There is only one weighing: the left side has toys $1$ and $2$, and the right side has toy $3$. The left side is heavier by $1$ unit. From this, the ranges can be determined to be $1 \sim 2$, $2 \sim 3$, and $2 \sim 3$.

Constraints:

$3 \le n \le 200$, $1 \le m \le 100$, and all upper bounds of weights are at most $20000$.

$50\%$ of the testdata satisfies $3 \le n \le 10$, $1 \le m \le 5$.

Translated by ChatGPT 5