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
cjn2007: 2021-09-27 12:56:11

A good problem.
I get Runtime Error at frist.
If you also get Runtime Error,try this:
1
1 1 4
1 0
0 1
1 1
0 0
The answer is:
1
1
1
1
This is because:if x=0 or y=0 or x=n or y=m,the line is on the border,and you don't need to do anything.But set or multiset will do something wrong!

Last edit: 2021-09-27 13:06:41
im__skp: 2021-08-15 12:47:52

Hint: Use the ordered map and ordered set. This way you can use binary search.

miraz173: 2021-07-31 23:33:17

Got TLE at first. But after modifying the code, I'm getting WA despite the code giving right answers to given test cases. Any test cases I should particularly look after?

Last edit: 2021-07-31 23:34:24
shinigami_: 2021-01-21 20:59:23

@morass : can you tell me why I m getting runtime error.
Solution ID : 27317345

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


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