B - Deconstruct Chocolate 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

H 行 W 列のブロックからなる長方形状のチョコレートがあります。

Q 個のクエリが与えられるので、順に処理したときの各クエリの答えを求めてください。各クエリは、以下のいずれかの形式です。

  • タイプ 1 : 整数 R が与えられる。下 R 行のチョコレートのブロックの個数を求め、それらを食べる。

  • タイプ 2 : 整数 C が与えられる。右 C 列のチョコレートのブロックの個数を求め、それらを食べる。

なお、クエリを順に処理したとき、各クエリを処理した後もチョコレートは長方形状であり、タイプ 1 のクエリを処理する直前の時点でチョコレートは R + 1 行以上存在し、タイプ 2 のクエリを処理する直前の時点でチョコレートは C + 1 列以上存在します。

制約

  • 2 \leq H, W \leq 100
  • 1 \leq Q \leq 100
  • タイプ 1 のクエリについて、1 \leq R
  • クエリを順に処理したとき、タイプ 1 のクエリを処理する直前にチョコレートは R + 1 行以上存在する
  • タイプ 2 のクエリについて、1 \leq C
  • クエリを順に処理したとき、タイプ 2 のクエリを処理する直前にチョコレートは C + 1 列以上存在する
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

H W Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

ただし、\text{query}_i は i 番目のクエリであり、以下のいずれかの形式で与えられる。

1 R

2 C

出力

Q 行出力せよ。 i (1 \leq i \leq Q) 行目には i 番目のクエリに対する答えを出力せよ。

入力例 1

7 9 5
2 4
1 3
2 1
2 1
1 3

出力例 1

28
15
4
4
9

はじめ、チョコレートは 7 行 9 列の長方形状です。

1 番目のクエリでは、右 4 列のチョコレートの個数は 28 個であるため 28 を出力します。チョコレートは 7 行 5 列となります。

2 番目のクエリでは、下 3 行のチョコレートの個数は 15 個であるため 15 を出力します。チョコレートは 4 行 5 列となります。

3 番目のクエリでは、右 1 列のチョコレートの個数は 4 個であるため 4 を出力します。チョコレートは 4 行 4 列となります。

4 番目のクエリでは、右 1 列のチョコレートの個数は 4 個であるため 4 を出力します。チョコレートは 4 行 3 列となります。

5 番目のクエリでは、下 3 行のチョコレートの個数は 9 個であるため 9 を出力します。チョコレートは 1 行 3 列となります。

Score : 200 points

Problem Statement

There is a rectangular chocolate consisting of H rows and W columns of blocks.

You are given Q queries; process them in order and find the answer to each query. Each query is in one of the following formats:

  • Type 1: An integer R is given. Find the number of chocolate blocks in the bottom R rows, then eat them.

  • Type 2: An integer C is given. Find the number of chocolate blocks in the rightmost C columns, then eat them.

When the queries are processed in order, the chocolate remains rectangular after each query is processed, and it has at least R + 1 rows immediately before processing a type 1 query and has at least C + 1 columns immediately before processing a type 2 query.

Constraints

  • 2 \leq H, W \leq 100
  • 1 \leq Q \leq 100
  • For type 1 queries, 1 \leq R.
  • When the queries are processed in order, the chocolate has at least R + 1 rows immediately before processing a type 1 query.
  • For type 2 queries, 1 \leq C.
  • When the queries are processed in order, the chocolate has at least C + 1 columns immediately before processing a type 2 query.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

H W Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Here, \text{query}_i is the i-th query, given in one of the following formats:

1 R

2 C

Output

Output Q lines. The i-th line (1 \leq i \leq Q) should contain the answer to the i-th query.

Sample Input 1

7 9 5
2 4
1 3
2 1
2 1
1 3

Sample Output 1

28
15
4
4
9

Initially, the chocolate is a rectangle with 7 rows and 9 columns.

For the first query, the number of chocolate blocks in the rightmost 4 columns is 28, so output 28. The chocolate becomes 7 rows and 5 columns.

For the second query, the number of chocolate blocks in the bottom 3 rows is 15, so output 15. The chocolate becomes 4 rows and 5 columns.

For the third query, the number of chocolate blocks in the rightmost 1 column is 4, so output 4. The chocolate becomes 4 rows and 4 columns.

For the fourth query, the number of chocolate blocks in the rightmost 1 column is 4, so output 4. The chocolate becomes 4 rows and 3 columns.

For the fifth query, the number of chocolate blocks in the bottom 3 rows is 9, so output 9. The chocolate becomes 1 row and 3 columns.