Ada the Ladybug owns a beautiful field where she grows vegetables. She often visits local Farmers Market, where she buys new seeds. Since two types of vegetable can‘t share same field, she always divide the field, by either vertical or horizontal line (she is very precise, so the width of line is negligible). Since she visits Farmers Market almost every day, she has already made a lot of such lines, so she needs your help with finding out the area of biggest field.

Input

The first line will contain 0 < T ≤ 200, the number of test-cases.

Then T test-cases follow, each beginning with three integers 1 ≤ N,M ≤ 2*109, 1 ≤ Q ≤ 105, top right corner of field (field goes from [0,0] to [N,M]) and number of field divisions.

Afterward Q lines follows:

0 x (0 ≤ x ≤ N), meaning that line was made vertically, on coordinate x

1 y (0 ≤ y ≤ M), meaning that line was made horizontally, on coordinate y

Sum of Q over all test-cases won‘t exceed 106

Output

Print Q lines, the area of biggest field after each line was made.

Example Input

2
10 10 5
0 5
0 8
1 1
1 9
1 5
10 10 5
0 5
1 4
1 6
1 8
0 5

Example Output

50
50
45
40
20
50
30
20
20
20

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <queue>
 8 #include <set>
 9 #include <map>
10 #include <list>
11 #include <stack>
12 #define mp make_pair
13 typedef long long ll;
14 typedef unsigned long long ull;
15 const int MAX=1e6+5;
16 const int INF=-1e9;
17 using namespace std;
18 typedef pair<int,int> pii;
19 int t;
20 int n,m,Q;
21 int zuo,you,len;
22 set <int> hang,lie;//记录行列位置
23 multiset <int> hlen,llen;//记录行列距离
24 ll an;
25 int opt,x;
26 void init()
27 {
28     hang.clear();lie.clear();hlen.clear();llen.clear();
29     hang.insert(0);hang.insert(n);hlen.insert(n);
30     lie.insert(0);lie.insert(m);llen.insert(m);
31 }
32 int main()
33 {
34     scanf("%d",&t);
35     set<int>::iterator p;
36     multiset<int>::iterator q;
37     while(t--)
38     {
39         scanf("%d%d%d",&n,&m,&Q);
40         init();
41         while(Q--)
42         {
43             scanf("%d%d",&opt,&x);
44             if(opt)
45             {
46                 if(lie.find(x)==lie.end())
47                 {
48                     p=lie.lower_bound(x);
49                     you=*p;
50                     p--;
51                     zuo=*p;
52                     q=llen.find(you-zuo);
53                     llen.erase(q);
54                     len=you-x;
55                     llen.insert(len);
56                     len=x-zuo;
57                     llen.insert(len);
58                     lie.insert(x);
59                 }
60 
61             }
62             else
63             {
64                 if(hang.find(x)==hang.end())
65                 {
66                     p=hang.lower_bound(x);
67                     you=*p;
68                     p--;
69                     zuo=*p;
70                     q=hlen.find(you-zuo);
71                     hlen.erase(q);
72                     len=you-x;
73                     hlen.insert(len);
74                     len=x-zuo;
75                     hlen.insert(len);
76                     hang.insert(x);
77                 }
78             }
79                 q=llen.end();q--;
80                 an=(ll)(*q);
81                 q=hlen.end();q--;
82                 an=(ll)(*q)*an;
83                 printf("%lld\n",an);
84         }
85     }
86 
87 }