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 nn rows and mm columns. Tom numbers the rows with integers from 11 to nn from top to bottom and the columns with integers from 11 to mm from left to right. He starts from the upper-left cell (1,1)(1,1). Tom can move down if and only if he is in the middle column of the grid (the m+12m+12th column). Otherwise, he can only go left or right. Each movement takes him 11 second. There are kk bottles of milk on the grid. The iith bottle is located in the ririth row and cicith column, and Tom needs titi 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,⋯,k)i(i=1,2,⋯,k) bottles of milk.
Input
The first line contains one integer T(1≤T≤2500)T(1≤T≤2500), the number of test cases. For each test case, the first line contains 33 integers n,m,k(3≤n,m≤109,1≤k≤104,∑k≤6×104)n,m,k(3≤n,m≤109,1≤k≤104,∑k≤6×104), where mm is guaranteed to be an odd number. Each of the next kk lines contains 33 integers ri,ci,ti(1≤ri≤n,1≤ci≤m,ci≠m+12,1≤ti≤109)ri,ci,ti(1≤ri≤n,1≤ci≤m,ci≠m+12,1≤ti≤109), the position of iith bottle of milk and the time it takes Tom to drink.
Output
For each test case, output one line containing kk integers separated by space, the iith of which indicates the minimum time Tom needs to finish exactly ii bottles of milk.