Precise Weight Determination

IceIce has several toys. For each toy, an initial weight range is known. In addition, she performs a series of weighings with an electronic scale. The scale can place any number of toys on its left and right sides and will tell you the difference \(d\) = (sum of weights on the left) \(-\) (sum of weights on the right). However, for each toy, she is only allowed to place it on the left side at most once and on the right side at most once across all weighings.

You are given \(n\) toys. For the \(i\)-th toy, its weight \(x_i\) is an integer satisfying \(L_i \le x_i \le U_i\) (the weights are given in NOI units). There are \(m\) weighings. In the \(j\)-th weighing, a set of toys is placed on the left and another set on the right. The measured result is an integer \(d_j\) which satisfies: \[ \sum_{i \in \text{Left}_j} x_i - \sum_{i \in \text{Right}_j} x_i = d_j. \]

Your task is to determine, for each toy, the updated precise range (i.e. the minimum and maximum possible weight) that can be deduced from the initial ranges and all the weighing results. It is guaranteed that the weighing configurations obey the rule that each toy is placed on each side at most once, and that there is at least one solution.

Input/Output Example:

For example, suppose there are 3 toys with the following initial ranges:

Toy	Minimum	Maximum
1	1	3
2	2	4
3	3	5

IceIce performs 2 weighings with the following configurations and results:

1. First weighing: Toys 1 and 2 on the left, Toy 3 on the right, with \(d_1 = 4\).
2. Second weighing: Toy 2 on the left, Toy 3 on the right, with \(d_2 = 1\).

From these, the only solution is \(x_1=3, x_2=4, x_3=3\), so the updated ranges for each toy are exactly [3,3], [4,4] and [3,3] respectively.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n \le 10, \ 0 \le m \le 2)\), representing the number of toys and the number of weighings.

The next \(n\) lines each contain two integers \(L_i\) and \(U_i\) \((L_i \le U_i)\) representing the initial minimum and maximum possible weight of the \(i\)-th toy.

Then for each weighing, the input contains three parts:

• A line beginning with an integer \(a\) followed by \(a\) space‐separated integers representing the indices (1-indexed) of the toys on the left side.
• A line beginning with an integer \(b\) followed by \(b\) space‐separated integers representing the indices (1-indexed) of the toys on the right side.
• A line with a single integer \(d\), the measured difference (left sum minus right sum).

It is guaranteed that each toy appears at most once on the left side and at most once on the right side across all weighings.

outputFormat

Output \(n\) lines. The \(i\)-th line contains two integers separated by a space: the minimum possible weight and the maximum possible weight for the \(i\)-th toy, based on all weighing results. It is guaranteed that at least one solution exists.

sample

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

3 3
4 4
3 3

</p>