Problem Description

Bingbing has three toys: Pikachu, Vinnie Sun Wukong, and Barbie. She does not know the exact weights of these toys (in NOI units), but she knows the approximate ranges of each toy's weight, as shown in the table below:

Table 1. Toys and their minimum and maximum possible weights
| Pikachu | Vinnie Sun Wukong | Barbie |
| :-: | :-: | :-: |
| Minimum possible weight | 1 | 2 | 3 |
| Maximum possible weight | 3 | 4 | 5 |
These ranges are too broad, and Bingbing hopes to narrow them down.

Fortunately, Jiajia has an electronic scale that can not only tell if both sides are of equal weight but also indicate how much heavier the left side is compared to the right side. The scale is large enough to accommodate any number of toys on both sides.

Bingbing borrows the electronic scale from Jiajia to calculate the exact weights of each toy. Jiajia, to test Bingbing, allows her to place any one toy on the left and right sides of the scale at most once each. For example, if she has placed Pikachu on the left side of the scale, she cannot place it there again. Bingbing agrees. She performs two weighings, with the results as follows (the numbers indicate how much heavier the left side is than the right side):

Based on the results and Table 1, it can be determined that the weights of the three toys must be 3, 4, and 3. That is, the updated weight ranges obtained from the weighing results are:

Table 2. Precise ranges obtained from weighing results
| Pikachu | Vinnie Sun Wukong | Barbie |
| :-: | :-: | :-: |
| Minimum possible weight | 3 | 4 | 3 |
| Maximum possible weight | 3 | 4 | 3 |
Bingbing will buy many more toys in the future and does not want to calculate the weights of each toy every time. She needs a program to calculate the most precise lower and upper bounds of each toy's weight. Can you help her?

Input Format

The first line of the input file contains two integers n and m, representing the number of toys and the number of weighings, respectively. The second line contains 2n numbers, where the (2i-1)-th and 2i-th numbers represent the initial lower and upper bounds of the weight of the i-th toy. The following m lines, each starting with three numbers L, R, and D, indicate the number of toys on the left side, the number of toys on the right side, and the weight difference between the two sides (L, R >= 0). The next L numbers are the toy numbers on the left side of the scale, followed by R numbers representing the toy numbers on the right side of the scale. The input guarantees that each toy appears at most once on each side of the scale.

Output Format

The output file contains 2n integers, where the (2i-1)-th and 2i-th numbers represent the lower and upper bounds of the weight of the i-th toy, i.e., the smallest and largest possible integer weights. If there is no solution (possibly because the scale is broken), output only one number -1.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3 3 4 4 3 3

Input Sample #2

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

Output Sample #2

1 2 2 3 2 3

Notes

Sample Explanation

Sample 1 corresponds to the example in the problem description.

In Sample 2, Bingbing has three toys with initial weight ranges of 1~5, 2~5, and 1~3. There is only one weighing, with toys 1 and 2 on the left side and toy 3 on the right side. The left side is 1 unit heavier than the right side. Based on this result, the weight ranges of the three toys can be determined to be 1~2, 2~3, and 2~3.

Constraints

3 <= n <= 200, 1 <= m <= 100, the weight upper bound does not exceed 20,000.

50% of the data satisfies 3 <= n <= 10, 1 <= m <= 5.

见题面 Input 部分

见题面 Output 部分