Islands after each new piece of land

Problem

Ishaan plays a mobile game about building land in the sea. The map is a grid of r rows and c columns, and at the start every cell is water.

Each move raises one cell into land. Land cells that touch up, down, left or right belong to the same island. Cells that touch only at a corner do not. A move on a cell that is already land changes nothing.

After every move, print the number of islands.

Input, output and limits

Input: The first line has two integers r and c. The second line has one integer q. Each of the next q lines has two integers row and col (1-based): the cell raised by that move.
Output: One line with q integers separated by single spaces: the number of islands after each move.
Constraints: 1 ≤ r, c ≤ 1000
1 ≤ q ≤ 10^5
1 ≤ row ≤ r, 1 ≤ col ≤ c

Examples

Example

Input

Output

1 1 2 1

Cell (2, 3) starts a second island. Cell (2, 2) touches both islands and joins them into one.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Counting islands from scratch after every move is too slow for 10^5 moves. Think about how one move changes the count.

Hint 2

A new land cell adds one island. Then, for each land neighbour that is in a different island, the two islands join and the count drops by one.

Hint 3

You need two fast steps: find which island a cell belongs to, and join two islands into one.

Hint 4

Use union-find (disjoint set union) over the cells, with path compression. Skip a move on a cell that is already land.

Write your Java code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Mixed DSA problems

Problem

Input, output and limits

Examples

Hints

More Mixed DSA problems