Cho một bảng $A$ kích cỡ $n\times n$ chứa các số nguyên từ $1$ đến $1000$. Gọi $f(i,j)$ là tổng lớn nhất trên đường đi từ ô $(1,1)$ đến ô $(i,j)$ nếu chỉ được đi sang ngang hoặc đi xuống dưới một ô. Có $n$ truy vấn, mỗi truy vấn dạng $(v,x,y)$, tăng giá trị $A_{x,y}$ lên $v$ trong đó $v$ là $1$ hoặc $-1$. Hãy tính tổng của $f$ với mọi $(i,j)$ sau mỗi truy vấn.
### Input
- Dòng đầu tiên gồm số nguyên $n \le 1500$.
- $n$ dòng tiếp theo, mỗi dòng gồm $n$ số nguyên $A_{i,j}$
### Output
- Dòng đầu tiên là tổng $f$ ban đầu.
- $n$ dòng tiếp theo là tổng $f$ sau các truy vấn.
### Ví dụ
Input:
```
5
3 3 5 0 5
4 4 2 4 3
4 4 2 1 3
4 3 2 4 2
2 3 3 2 4
1 1 1
1 1 3
-1 5 2
-1 4 3
-1 2 4
```
Output:
```
420
445
453
451
448
442
```
