# Staircases solution codeforces

## Staircases solution codeforces

You are given a matrix, consisting of 𝑛n rows and 𝑚m columns.

Each cell of the matrix can be either free or locked.

Let’s call a path in the matrix a staircase if it:

• starts and ends in the free cell;
• visits only free cells;
• has one of the two following structures:
1. the second cell is 11 to the right from the first one, the third cell is 11 to the bottom from the second one, the fourth cell is 11 to the right from the third one, and so on;
2. the second cell is 11 to the bottom from the first one, the third cell is 11 to the right from the second one, the fourth cell is 11 to the bottom from the third one, and so on.

In particular, a path, consisting of a single cell, is considered to be a staircase.

Here are some examples of staircases:

Initially all the cells of the matrix are free.

You have to process 𝑞q queries, each of them flips the state of a single cell. So, if a cell is currently free, it makes it locked, and if a cell is currently locked, it makes it free.

Print the number of different staircases after each query. Two staircases are considered different if there exists such a cell that appears in one path and doesn’t appear in the other path.

Input

The first line contains three integers 𝑛n, 𝑚m and 𝑞q (1𝑛,𝑚10001≤n,m≤1000; 1𝑞1041≤q≤104) — the sizes of the matrix and the number of queries.

Each of the next 𝑞q lines contains two integers 𝑥x and 𝑦y (1𝑥𝑛1≤x≤n; 1𝑦𝑚1≤y≤m) — the description of each query.

Output

Print 𝑞q integers — the 𝑖i-th value should be equal to the number of different staircases after 𝑖i queries. Two staircases are considered different if there exists such a cell that appears in one path and doesn’t appear in the other path.

Examples
input

Copy
2 2 8
1 1
1 1
1 1
2 2
1 1
1 2
2 1
1 1

output

Copy
5
10
5
2
5
3
1
0

input

Copy
3 4 10
1 4
1 2
2 3
1 2
2 3
3 2
1 3
3 4
1 3
3 1

output

Copy
49
35
24
29
49
39
31
23
29
27

input

Copy
1000 1000 2
239 634
239 634

output

Copy
1332632508
1333333000