The sparse matrix can be stored in a compressed manner, that is, a matrix of n rows and 3 columns is used to store only non-zero elements. Each row stores a non-zero element, the first of each row is the non-zero element row index; the second is the non-zero element column index; the third is the non-zero element itself. As shown below, the left side is a sparse matrix, and the right side is its storage form. Write a program to realize the multiplication of the sparse matrix input by the above-mentioned compressed storage method, and the maximum sparse matrix is 9*9. Output the result matrix in compressed mode. Both row and column labels start counting from 0.
0 0 0 10 0 3 10
2 0 0 0 1 0 2
0 0 3 1 2 2 3
1 0 0 0 2 3 1
3 0 1
[Input form]
First input the number of non-zero elements of the first matrix from the console, and then input the elements of the first matrix in a compressed manner, that is: input the row labels, column labels and non-zero element data itself of the non-zero elements in a row by one Spaces separate row labels, column labels, and non-zero elements. Then enter the second matrix in the same way.
【Output form】
The result matrix is output in compressed rows on the standard output, that is: each row outputs the row labels, column labels and non-zero element data itself of the non-zero elements in the result matrix, with a row label, column label, and non-zero data. Space separated, but there is no space after the last data in each line. The element with the smaller row size is output first. If the row labels are the same, the element with the smaller column size is output first. If there are no non-zero elements, no information is output.
【Input sample】
5
0 3 10
1 0 2
2 2 3
2 3 1
3 0 1
2
0 1 200
2 2 -5
[Sample output]
1 1 400
2 2 -15
3 1 200
[Sample description]
The maximum subscripts of the rows and columns of the two input matrices are 3, so it can be regarded as a 4*4 matrix, that is, the two input matrices are:
0 0 0 10
2 0 0 0
0 0 3 1
1 0 0 0
0 200 0 0
0 0 0 0
0 0 -5 0
0 0 0 0
The result of multiplying the two matrices is:
0 0 0 0
0 400 0 0
0 0 -15 0
0 200 0 0