The famous astro-botanist Mateja Damon successfully grows potatoes on Mars, thanks to the students from the informatics competitions.

This year, he decided to open a new potato farm on Mars and he needs your help. Mateja has a fertile piece of land of dimensions \(N\times M\) divided into \(N\cdot M\) unit squares. He can plant an arbitrary number of potatoes on a square under the constraint that \(i\)-th row contains at least \(a_i\) and at most \(b_i\) potatoes (for \(i=1, 2, \ldots, N\)). Furthermore, \(j\)-th column must contain at least \(c_j\) and at most \(d_j\) potatoes (for \(j=1, 2, \dots, M\)).

Help our dear friend Mateja determine the layout of potatoes which will maximize his earnings. In other words, help him plan as many potatoes as possible.

Input format

The first line of the standard input contain two positive integers \(N\) and \(M\), the dimensions of Mateja’s piece of land.

Each of the next \(N\) lines contains two integers, \(a_i\) and \(b_i\), representing the constraints of the \(i\)-th row.

Each of the next \(M\) lines contains two integers, \(c_j\) and \(d_j\), representing the constraints of the \(j\)-th column.

Output format

Your program should print the maximal number of potatoes Mateja can plant to the first line of the standard output.

Further, it should print \(K\), the number of unit squares containing potatoes, to the second line of the standard output

Finally, to each of the next \(K\) lines, it should print three integers \(x\), \(y\) and \(n\) (\(1 \leq x \leq N\), \(1 \leq y \leq M\), \(n \geq 0\)), meaning that Mateja should plant \(n\) potatoes on the square at the intersection of the \(x\)-th row and \(y\)-th column.

The layout of potatoes must respect all above constraints. If there are multiple valid solutions, print any.

Sample 1

Input

2 2
1 2
1 1
1 3
0 0

Output

3
2
1 1 2
2 1 1

Explanation

One possible profit-maximizing layout of the potatoes is drawn in the table below (the expressions of the form \(x-y\) in the table refer to the lower and upper bounds on the number of potatoes in the given row/column).

Sample 2

Input

2 3
2 2
2 2
1 2
1 2
1 2

Output

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

Explanation

One possible profit-maximizing layout of the potatoes is drawn in the table below.

Constraints

• \(1 \leq N, M \leq 50000\).
• \(0 \leq а_i \leq b_i \leq 10^9\)
• \(0 \leq c_i \leq d_i \leq 10^9\)
• It is guaranteed that there will always be at least one layout of potatoes satisfying all of the constraints.

Testcases are split into six disjoint groups:
- In the test cases worth 10 points, we have additional constraints: \(N=M, a_i \leq c_i \leq b_i \leq d_i\).

• In the test cases worth 10 points, we have additional constraints: \(a_i = b_i, c_i = d_i\).

• In the test cases worth 15 points, we have additional constraints: \(a_i = b_i\).

• In the test cases worth 15 points, we have additional constraints: \(N = 1\).

• In the test cases worth 30 points, we have additional constraints: \(a_i = c_i = 0\).

• In the test cases worth 20 points, we have no additional constraints.