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 \times N$ grid $(1 \leq N \leq 500)$, with a single stationary cow at each location. Farmer John's camera is capable of taking a picture of any $K \times K$ square that is part of the field $(1 \leq K \leq \min(N, 25))$.

At all times, each cow has a beauty value between $0$ and $10^6$. 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 \leq Q \leq 3\cdot 10^{4})$, 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.

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.

Problem credits: Brian Law and Cici Liu