Description

Bobo has n × m points arranged into a matrix with n rows and m columns. The points in the intersection of the i-th row and the j-th column is labeled with (i, j). He is going to perform q operations of the following 2 kinds.

1. Given parameters a, b, add edges between points (i, j) and (i, j + 1) for all a ≤ i ≤ b and 1 ≤ j < m.
2. Given parameters a, b, add edges between points (i, j) and (i + 1, j) for all 1 ≤ i < n and a ≤ j ≤ b.

Bobo would like to know the number of connected components after each operation.

• 1 ≤ n, m ≤ 10⁹
• 1 ≤ q ≤ 10⁵
• t_i ∈ {1, 2}
• If t_i = 1, 1 ≤ a_i ≤ b_i ≤ n. If t_i = 2, 1 ≤ a_i ≤ b_i ≤ m.
• The sum of q does not exceed 5 × 10⁵.

Input

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains three integers n, m and q.

The i-th of the following q lines contains three integers t_i, a_i and b_i where t_i is the kind of the operation i and a_i, b_i are corresponding parameters.

Output

For each test case, print q integers which denote the number of connected components after each operation.

2 3 3
2 1 1
2 3 3
1 1 1
1000000000 1000000000 1
1 1 2

5
4
2
999999998000000002