SP1963 IMGPROJ - Image Projections

Given an image _I_ with _N_ columns and _M_ rows, a diagonal projection is the vector (_d $ _{1} $_ , _d $ _{2} $_ , ..., _d $ _{M+N-1} $_ ) where _d $ _{i} $_ = Σ _$ _{x+y-1=i} $ I(x,y)_. Here _I(x,y)_, _1_ ≤ _x_ ≤ _N_, _1_ ≤ _y_ ≤ _M_, is the image intensity (a non-negative integer less than 256) at column _x_ and row _y_. You are given a set of images and you are asked to find the diagonal projection for each of them.

The first line of input contains a positive number, the number of images that follow. For each image there is a line with _N_ and _M_. The following _M_ lines describe one row each starting from row 1. A row is described in run-length encoding by pairs of numbers separated by spaces. The first number in each pair is the length of the run and the second number is the image intensity. Obviously, for each row, the run lengths add up to _N_. As in the example input, there is a blank line between each two consecutive images and before the first one. The number of test cases is at most 10. The width of each image is less than _10 $ ^{9} $_ and the height is less than _10 $ ^{3} $_ . Additionally, the total size of the input does not exceed 4 MB.

For each image you should output one line, the diagonal projection for the image in run length encoding. The number of output lines should be the same as the number of images in the input. All the numbers on a line should be separated by exactly one space. When encoding the output in run-length encoding, the runs should be as long as possible, i.e. no two consecutive runs should have the same intensity value.