Farmer John is looking at his cows in a magical field and wants to take pictures of subsets of his cows.
The field can be seen as a N×N grid (1≤N≤500), with a single stationary cow at each location. Farmer John's camera is capable of taking a picture of any K×K square that is part of the field (1≤K≤min(N,25)).
At all times, each cow has a beauty value between 0 and 106 . The attractiveness index of a picture is the sum of the beauty values of the cows contained in the picture.
The beauty value for every cow starts out as 0, so the attractiveness index of any picture in the beginning is 0.
At Q times (1≤Q≤3⋅104), the beauty of a single cow will increase by a positive integer due to eating the magical grass that is planted on Farmer John's field.
Farmer John wants to know the maximum attractiveness index of a picture he can take after each of the Q updates.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains integers N and K.
The following line contains an integer Q.
Each of the following Q lines contains three integers: r, c, and v, which are the row, column, and new beauty value, respectively (1≤r,c≤N,1≤v≤106). It is guaranteed that the new beauty value is greater than the beauty value at that location before.
OUTPUT FORMAT (print output to the terminal / stdout):
Output Q lines, corresponding to the maximum attractiveness index of a picture after each update.
SAMPLE INPUT:
4 2
3
2 2 11
3 4 3
3 1 100
SAMPLE OUTPUT:
11
11
111
After the first update, a picture with the maximum attractiveness index is the picture with upper left corner (2,2) and lower right corner (3,3), which has an attractiveness index of 11+0+0+0=11.
The second update does not affect the maximum attractiveness index.
After the third update, the picture with the maximum attractiveness index changes to the picture with upper left corner (2,1) and lower right corner (3,2), which has an attractiveness index of 0+11+100+0=111.
SAMPLE INPUT:
3 1
3
2 2 3
2 2 5
2 2 7
SAMPLE OUTPUT:
3
5
7
There is only one cow with a positive beauty value, so the maximum attractiveness index will always include that cow.
SCORING:
Inputs 3-6: N≤50,Q≤100
Inputs 7-10: N≤50
Inputs 11-18: No additional constraints.
Problem credits: Brian Law and Cici Liu