문제

지훈이는 $N \times N$ 크기의 격자 모양 광장에서 사진을 찍으려 한다. ($1 \le N \le 500$) 격자의 각 칸에는 학생이 한 명씩 서 있다. 지훈이의 카메라는 격자의 일부인 $K \times K$ 크기의 정사각형 구역을 촬영할 수 있다. ($1 \le K \le \min(N, 25)$)

각 학생은 $0$ 이상 $10^6$ 이하의 매력도를 가진다. 사진의 매력 지수는 사진에 포함된 모든 학생의 매력도의 합이다.

처음에 모든 학생의 매력도는 $0$이며, 따라서 초기 상태에서 어떤 사진을 찍어도 매력 지수는 $0$이다.

축제가 진행됨에 따라 총 $Q$번에 걸쳐 학생들의 매력도가 변한다. ($1 \le Q \le 3 \cdot 10^4$) 각 업데이트마다 한 학생의 매력도가 이전보다 큰 값으로 바뀐다. 지훈이는 각 업데이트가 일어날 때마다 찍을 수 있는 사진의 매력 지수의 최댓값을 구하고자 한다.

입력

첫째 줄에 $N$과 $K$가 공백으로 구분되어 주어진다.

둘째 줄에 업데이트 횟수 $Q$가 주어진다.

다음 $Q$개의 줄에는 각 업데이트를 나타내는 세 정수 $r$, $c$, $v$가 공백으로 구분되어 주어진다. ($1 \le r, c \le N$; $1 \le v \le 10^6$) 이는 $r$행 $c$열에 위치한 학생의 매력도가 $v$로 바뀌었음을 의미한다. 매력도는 항상 이전 값보다 큰 값으로 주어진다.

출력

$Q$개의 줄에 걸쳐, 각 업데이트가 끝날 때마다 지훈이가 찍을 수 있는 사진의 매력 지수의 최댓값을 한 줄에 하나씩 출력한다.

예제 입력 1

4 2
3
2 2 11
3 4 3
3 1 100

예제 출력 1

11
11
111

예제 입력 2

3 1
3
2 2 3
2 2 5
2 2 7

예제 출력 2

3
5
7

제약 조건

• 테스트 케이스 3-6: $N \le 50, Q \le 100$
• 테스트 케이스 7-10: $N \le 50$
• 테스트 케이스 11-18: 추가적인 제약 조건이 없다.