Given an image I with N columns and M rows, a diagonal projection is the vector (d₁, d₂, ..., 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.

Input

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⁹ and the height is less than 10³. Additionally, the total size of the input does not exceed 4 MB.

Output

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.

Example

Input:
2

3 3
1 1 1 2 1 3
1 1 1 2 1 3
1 3 1 2 1 1

3 2
3 1
3 1

Output:
1 1 1 3 1 8 1 5 1 1
1 1 2 2 1 1