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
zarif_2002: 2019-02-07 05:26:34

yeah. got AC in second chance. a good problem for beginners like us to learn lower bound and stl features.

Last edit: 2019-02-07 05:43:49
ducky94tb: 2019-01-01 10:56:08

It's really hard problem:3

shubham_04_04: 2018-09-06 12:26:53

Why am I getting Runtime Error now? I have implemented log N time per query

Last edit: 2018-09-07 10:07:21
rnk20: 2018-07-21 23:45:47

Take care of this test case:-
1
1 1 1
0 0

scooby123: 2018-06-16 14:01:33

can pls someone tell me how to do this question in java
I have tried with collections and binary search but getting tle.

Last edit: 2018-06-16 14:04:16
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


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