ADAFIELD - Ada and Field


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

hide comments
excel_blaze: 2018-05-22 22:49:11

NICE ONE !!
if you consider using multiset of ll then take care of pointers

rollicks_7: 2018-05-01 23:18:03

How on Earth did she divide the field 10^5 times!

Vipul Srivastava: 2017-06-12 15:45:33

@morass I don't know why I am getting WA can you please give some hint?

sucide: 2017-05-22 21:16:52

I found a strange thing
i used auto it2 = upper_bound(py.begin() , py.end() , x );
and got tle
but when i used
auto it2 = py.upper_bound( x );
the solution passed

pranav0123: 2017-05-22 16:15:25

@morass: can you please check my submission once. I have submitted a qlog(n) solution but still getting TLE.
Submission id: 19457227

morass: 2017-04-05 04:03:40

@anonymous: Thanx ^_^ (hope its ok now)

anonymous: 2017-04-05 00:02:14

There is a small typo in description: s/se/she/.

r_ash: 2017-02-28 09:35:41

Hi! this similar problem got accepted on (527C)codeforces, but it says wrong answer in here, what problem could it be?
edit: Found my mistake.

Last edit: 2017-02-28 14:21:09
morass: 2017-01-28 23:54:57

@muneebaadil: Good day to you - well it is meant "grid lines" not "grid fields", so grid from [0,0] to [1][1] is 1x1 grid (i.e. the area of it is 1). Hope it is more clear! Good Luck & Have nice day!

muneebaadil: 2017-01-28 19:15:51

I don't understand indexing. It's stated that "field goes from [0,0] to [N,M]." That means there are total of ((N+1) x (M+1)) entries in the field, right? But if so, after the first query of first testcase, shouldn't the answer be 55 instead of 50?
@morass Kindly clarify, thanks!


Added by:Morass
Date:2016-09-12
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU