A matrix is a rectangular array of elements, most commonly numbers. A matrix with m rows and n columns is said to be an m-by-n matrix. For example, above is: 1005 AT=3 4 0 −2 2 −1 0 11 132 0 4 −1 A=000 5 −2 11 is a 4-by-3 matrix of integers. The individual elements of a matrix are usually given lowercase symbols and are distinguished by subscripts. The ith row and jth column of matrix A is usually referred to as aij. For example, a23 = −1. Matrix subscripts are 1-based. The transpose of a matrix M , denoted M T , is formed by interchanging the rows and columns of M . That is, the ij-th element of MT is the ji-th element of M. For example, the transpose of matrix A A matrix is said to be sparse if there are relatively few non-zero elements. As a m-by-n matrix has mn number of elements, storing all elements of a large sparse matrix may be inefficient as there would be many zeroes. There are a number of ways to represent sparse matrices, but essentially they are all the same: store only the non-zero elements of the matrix along with their row and column. You are to write a program to output the transpose of a sparse matrix of integers. Input You are given several sparse matrix in a row, each of them described as follows. The first line of the input corresponds to the dimension of the matrix, m and n (which are the number of rows and columns, respectively, of the matrix). You are then given m sets of numbers, which represent the rows of the matrix. Each set consists of two lines which represents a row of the matrix. The first line of a set starts with the number r, which is the number of non-zero elements in that row, followed by r numbers which correspond to the column indices of the non-zero elements in that row, in ascending order; the second line has r integers which are the matrix elements of that row. For example, matrix A above would have the following representation: 43 3123 132 223 4 -1 0 3123 5 -2 11 Note that for a row with all zero elements, the corresponding set would just be one number, ‘0’, in the first line, followed by a blank line. You may assume:
2/2 • the dimension of the sparse matrix would not exceed 10000-by-10000, • the number of non-zero element would be no more than 1000, • each element of the matrix would be in the range of -10000 to 10000, and • each line has no more than 79 characters. Output For each input case, the transpose of the given matrix in the same representation. Sample Input 43 3123 132 223 4 -1 0 3123 5 -2 11 Sample Output 34 214 15 3124 3 4 -2 3124 2 -1 11