Add Sparse Matrices

You are given two sparse matrices represented as dictionaries. In each dictionary, a key is a coordinate tuple (i, j) and the associated value is the non-zero element at that coordinate. Your task is to compute the sum of the two matrices. The sum at a given coordinate is defined as the sum of corresponding values from the two matrices. If a coordinate appears in only one matrix, its value in the sum is the same as in that matrix.

Input Format : The input is read from standard input (stdin). The first line contains an integer \(n_1\) representing the number of non-zero elements in the first sparse matrix. The following \(n_1\) lines each contain three integers: \(i\), \(j\), and \(v\), which indicate that the element at row \(i\) and column \(j\) is \(v\). After that, there is an integer \(n_2\) representing the number of non-zero elements in the second sparse matrix, followed by \(n_2\) lines in the same format.

Output Format : Output the summed sparse matrix in the following format: The first line contains an integer \(k\), the number of non-zero elements in the resulting matrix. The next \(k\) lines each contain three integers: \(i\), \(j\), and \(v\). The entries should be output sorted in lexicographical order by the coordinate (first by row, then by column).

inputFormat

The first integer \(n_1\) indicates the number of non-zero elements in the first matrix. Each of the next \(n_1\) lines contains three integers \(i\), \(j\), and \(v\), representing a non-zero entry of the first matrix. This is followed by an integer \(n_2\) indicating the number of non-zero entries in the second matrix, with the next \(n_2\) lines given in the same format.

outputFormat

First, output an integer \(k\) representing the number of non-zero elements in the summed matrix. Then, output \(k\) lines each containing three integers \(i\), \(j\), and \(v\), corresponding to the coordinates and the summed value. The output must be sorted lexicographically, first by the row index \(i\) and then by the column index \(j\).

## sample

3
0 0 1
1 2 3
2 1 4
3
0 0 2
2 1 5
3 3 7

4
0 0 3
1 2 3
2 1 9
3 3 7

</p>