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 testcases.
Then T testcases follow, each beginning with three integers 1 ≤ N,M ≤ 2*10^{9}, 1 ≤ Q ≤ 10^{5}, 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 testcases won't exceed 10^{6}
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:
20190207 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: 20190207 05:43:49 

ducky94tb:
20190101 10:56:08
It's really hard problem:3 

shubham_04_04:
20180906 12:26:53
Why am I getting Runtime Error now? I have implemented log N time per query Last edit: 20180907 10:07:21 

rnk20:
20180721 23:45:47
Take care of this test case:


scooby123:
20180616 14:01:33
can pls someone tell me how to do this question in java


excel_blaze:
20180522 22:49:11
NICE ONE !!


rollicks_7:
20180501 23:18:03
How on Earth did she divide the field 10^5 times! 

Vipul Srivastava:
20170612 15:45:33
@morass I don't know why I am getting WA can you please give some hint? 

sucide:
20170522 21:16:52
I found a strange thing


pranav0123:
20170522 16:15:25
@morass: can you please check my submission once. I have submitted a qlog(n) solution but still getting TLE.

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