You're visiting a friend's house. Her grade-three daughter asks, “Do you know your multiplications?” You answer, “Ah! I do. Anything I can help you with?”
“Oh, yes! Thank you. I am having trouble with my sparse multiplications.”
“Sparse multiplication?”
“We just learned how to do matrix multiplication, you know? Like,”
\[ \left( \begin{array}{cc} 1 & 2 \\ 3 & 4 \\ 5 & 6 \\ \end{array} \right) \left( \begin{array}{ccc} 7 & 8 & 9 \\ 10 & 11 & 12 \\ \end{array} \right) = \left( \begin{array}{ccc} 27 & 30 & 33 \\ 61 & 68 & 75 \\ 95 & 106 & 117 \\ \end{array} \right) \]She continues, “So generally, given an \(r\times s\) matrix \(\matrix{M}\) — \(r\) rows and \(s\) columns — an \(s\times t\) matrix \(\matrix{N}\), and letting \(\matrix{P} = \matrix{M}\matrix{N}\), then \(\matrix{P}\) is a \(r\times t\) matrix with \(\matrix{P}_{i,j} = \sum_{k=0}^{s-1}\matrix{M}_{i,k}\matrix{N}_{k,j}\).”
“Look, I do know what matrix multiplication is. Wait, you're in grade three?!”
“Yes, I am. Good, now pay attention. I know how to do all that. But our teacher told us to consider when the matrices are really big, but almost all the numbers are zero. Can you figure out the answer quickly still?”
“So you mean multiply sparse matrices efficently? Like,”
\[ \left( \begin{array}{ccc} 0 & 0 & 0 \\ 3 & 0 & 0 \\ 0 & 7 & 0 \\ \end{array} \right) \left( \begin{array}{ccc} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{array} \right) = \left( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 3 \\ 0 & 7 & 0 \\ \end{array} \right) \]“ Whoa! That was neat! Yes, that is what I mean. My mom tells me you are a programmer. You are going to write me a program to do it!”
“You're an awfully bossy kid, you know?”
The first line of input will consist of one integer, \(t\), that indicates the number of trials. \(0 \lt t \lt 1,000\). For each trial, two sparse matrices, \(\matrix{M}\) and \(\matrix{N}\), are given.
Each matrix is given on input as follows. A line of three integers: \(r\), the number of rows in the matrix; \(s\), the number of columns of the matrix; and \(n\), the number of non-zero entries in the matrix. Both \(r\) and \(s\) will be between 1 and 100,000, inclusive, and \(1 \le n \lt 10(r + s)\). Then \(n\) lines of input follow, one for each of the non-zero entries, consisting of three integers: \(i\), the row of the entry (\(0 \le i \lt r\)); \(j\), the column of the entry (\(0 \le j \lt s\)); and \(v\), the value of the entry. There is no particular order of the lines for the values.
You are assured every value in \(\matrix{M}\), \(\matrix{N}\), and the result \(\matrix{M}\matrix{N}\) fits as a regular integer (as do the intermediate results in any reasonable computation). No \(i, j\) will be given twice for a matrix. Each \(\matrix{M}\matrix{N}\) will have at least one non-empty entry. You are guaranteed the dimensions of the matrices to multiple align correctly.
3 2 2 3 0 1 3 1 0 5 0 0 7 2 2 2 0 0 1 1 1 1 3 3 2 1 0 3 2 1 7 3 3 3 0 2 1 1 1 1 2 0 1 10000 20000 1 7621 2558 7 20000 30000 1 2558 12974 3
For each trial, list the non-zero entries of \(\matrix{M}\matrix{N}\). List them in ascending order by row, and within a row, ascending by column. Print an empty line between trials.
0 0 7 0 1 3 1 0 5 1 2 3 2 1 7 7621 12974 21