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
morass: 2016-11-17 16:22:53

mahmud2690: Good day to you!
I) I'm not sure whether your program can handle "duplicate queries" correctly <boundaries inclusive>
II) I think you "swaped" width/heigth!

Good Luck & Have nice day! :)

mahmud2690: 2016-11-16 18:02:20

The same problem as Codeforces 527-C, but getting Runtime Error here
re @morass: thank you, i found my mistake.

Last edit: 2016-11-25 17:20:25
Abhishek Sehgal: 2016-10-13 17:37:28

@morass: can you tell me if my code is failing any corner case? Submission id: 17926018

morass: 2016-10-10 00:39:05

@aitya: Glad you figured it out! ^_^

aitya: 2016-10-09 23:05:40

Finally AC.Thanks for your guidance.Was also doing the blunder of using ios_base::sync_with_stdio(false) and "scanf("%d",&T) together in another question. corrected them and got AC there aswell

aitya: 2016-10-09 22:57:28

As of what i can make out,my code too has logarithmic complexity,not sure of correctness though.Is there a more optimal solution or does it require a more optimal implementation?

morass: 2016-10-09 18:53:20

@aitya: Hello, logarithmic complexity is enough :)

aitya: 2016-10-09 18:29:54

Now getting TLE.is the expected time per query O(1)?

morass: 2016-10-08 21:10:36

aitya: Good day to you, well - not saying that "rest" is good, yet I see a big problem in usage of "ios_base::sync_with_stdio(false) ;"and "scanf("%d",&T) ;" together! ;-) - so well, at least this is causing big troubles

aitya: 2016-10-08 06:19:30

Can you tell me whether my solution is failing all the test cases or am i missing a corner case?Submission ID
17881261


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