Sparse Matrix Triple Multiplication

You are given three sparse matrices \(A\), \(B\), and \(C\) represented in triple format. In each matrix only nonzero entries are provided as triplets \(i, j, a\), meaning that the element at row \(i\) and column \(j\) is \(a\), and all other entries are zero. The triplets are given in row‑major order (i.e. by increasing row number, and within the same row by increasing column number).

Matrix multiplication is defined when the number of columns of the left matrix equals the number of rows of the right matrix. In particular, if \(A\) is an \(m\times n\) matrix and \(B\) is an \(n\times p\) matrix, then their product \(D = A\times B\) is an \(m\times p\) matrix whose entries are defined as follows:

\[ d_{i,j}=\sum_{k=1}^{n}a_{i,k}\times b_{k,j} \]

Your task is to compute \(D = A\times B\times C\) using the given sparse matrix triple representations. The input contains three matrices in sequence. For each matrix, the first line gives three integers: the number of rows, the number of columns, and the number of nonzero entries. Then each of the following lines contains a triplet: row index, column index, and the value at that position. Assume that the matrix dimensions are such that the multiplication is valid.

inputFormat

The input consists of three parts corresponding to matrices \(A\), \(B\), and \(C\) respectively. Each part begins with a line containing three integers: r c k, where r is the number of rows, c is the number of columns, and k is the number of nonzero entries. This is followed by k lines, each containing three values: i j a, indicating that the element at row i and column j is a (1-indexed). The triplets are given in row‑major order.

You can assume the dimensions are valid for multiplication, i.e., if \(A\) is \(m\times n\), \(B\) is \(n\times p\), and \(C\) is \(p\times q\), then the product \(A \times B \times C\) is defined and its result is an \(m\times q\) matrix.

outputFormat

Output the sparse triple representation of the resultant matrix \(D = A \times B \times C\). For each nonzero element in \(D\), output a line with three values: the row index, the column index, and the element value. The output must be in row‑major order. If the resulting matrix is a zero matrix, output nothing.

sample

2 3 3
1 1 1
1 3 2
2 2 3
3 2 3
1 1 4
2 2 5
3 1 6
2 2 2
1 1 7
2 2 8

1 1 112
2 2 120

</p>