beecrowd | 2102

Counting in Chinese

By XIII Maratona de Programação IME-USP, 2009 Brazil

Timelimit: 1

China is one of the biggest countries in the world and the most populous. To do a census in the country is almost a war effort. The government sends to each canton a huge matrix which must be filled with every citizen’s characteristics. Each one of these matrixes has the same size: on the lines there are the various ethnicities (there are thousands) and on the columns the characteristics that you want to measure (it could get to millions). We know that few elements of each of these matrixes are in fact filled with values different than zero.

The work of the government company that does the census is, then, to receive the P matrixes M × N (1 ≤ N ≤ 100), each one given through its non-null elements and calculate the sum matrix of the various matrixes.

Input

The input is composed by various instances. The first line of the input has a whole number T indicating the number of instances.

The first line of each instance has two integers, N and L representing respectively the size of the matrices and the total amount of non-null inputs. The following L lines contain four integers Pk, lk, ck and vk indicating that the matrix Pk has value vk at the position in line lk and collum ck

Output

For each instance print the non-null inputs of the matrix addition. For each non-null imput of the matrix, print its line, column and value correspondent, separated by a space. The output need to be sorted

Between two instances print a blank line.

 Sample Input Sample Output 3 1000 4 1 1 1 1 2 1 1 2 3 1 2 100 1 1 2 1 2 2 1000 2 2 1 500 2 2 1 50 4 1 50 1 1 2 48 1 2 3 50 1 100 1 49 2 1 1 1 3 1 2 101 2 2 2 48 1 2 49 2 1 50 1 101