Bingbing has $n$ toys. She does not know the exact weight of each toy (in NOI units), but she knows the approximate range for each toy's weight.

An electronic balance is available that can tell you whether the left side is heavier or lighter than the right side, and by how much. The balance is large, and any number of toys can be placed on either side.

Bingbing wants to calculate the precise weight range for each toy. To test her, she is only allowed to place any given toy on the left side of the balance at most once, and on the right side of the balance at most once.

Bingbing needs to write a program to calculate the most precise lower and upper bounds for the weight of each toy. Can you help her?

Input

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

The second line contains $2n$ integers, where the $(2i-1)$-th number and the $2i$-th number represent the initial lower bound and initial upper bound of the $i$-th toy's weight, respectively.

The following $m$ lines each describe a weighing. Each line starts with three integers $L$, $R$, and $D$, representing the number of toys on the left side, the number of toys on the right side, and the weight difference between the left and right sides ($L, R \ge 0$). The next $L$ integers are the indices of the toys on the left side, and the subsequent $R$ integers are the indices of the toys on the right side. It is guaranteed that each toy appears at most once on each side of the balance for any given weighing.

Output

Output $2n$ integers. The $(2i-1)$-th number and the $2i$-th number represent the lower bound and upper bound of the $i$-th toy's weight, respectively, which are the minimum possible integer weight and the maximum possible integer weight. If there is no solution (e.g., the balance might be broken), output only the number $-1$.

Examples

Input 1

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

Output 1

3 3 4 4 3 3

Input 2

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

Output 2

1 2 2 3 2 3

Note

Example 1 corresponds to the example described in the problem statement.

In Example 2, Bingbing has three toys with initial weight ranges of $1 \sim 5$, $2 \sim 5$, and $1 \sim 3$. There is only one weighing: the left side has toy 1 and toy 2, and the right side has toy 3. The left side is 1 unit heavier than the right side. Based on this result, the weight ranges for the three toys can be determined as $1 \sim 2$, $2 \sim 3$, and $2 \sim 3$.

Constraints

$3 \le n \le 200$, $1 \le m \le 100$. The upper bound of the weight does not exceed $20000$.

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