As we all know, Tom loves milk very much, but he never manages to finish a bottle of milk by himself, cause Jerry always swallows at least half of it!
But now, he is alone in the Wonderland of Milk! The Wonderland can be seen as a grid with $n$ rows and $m$ columns. Tom numbers the rows with integers from $1$ to $n$ from top to bottom and the columns with integers from $1$ to $m$ from left to right. He starts from the upper-left cell $(1, 1)$.
Tom can move down if and only if he is in the middle column of the grid (the $\frac{m+1}{2}$th column). Otherwise, he can only go left or right. Each movement takes him $1$ second.
There are $k$ bottles of milk on the grid. The $i$th bottle is located in the $r_i$th row and $c_i$th column, and Tom needs $t_i$ seconds to finish it.
In order to enjoy the milk alone, he wants to do it as fast as possible. So he wants to know the minimum time he needs to finish $i(i=1,2,\cdots,k)$ bottles of milk.

The first line contains one integer $T(1\le T\le 2500)$, the number of test cases.
For each test case, the first line contains $3$ integers $n,m,k(3\le n,m\le 10^9,1\le k\le 10^4,\sum k\le 6\times 10^4)$, where $m$ is guaranteed to be an odd number.
Each of the next $k$ lines contains $3$ integers $r_i,c_i,t_i(1\le r_i\le n,1\le c_i\le m,c_i\ne\frac{m+1}{2},1\le t_i\le 10^9)$, the position of $i$th bottle of milk and the time it takes Tom to drink.

For each test case, output one line containing $k$ integers separated by space, the $i$th of which indicates the minimum time Tom needs to finish exactly $i$ bottles of milk.