#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Gug is drawing rectangles on a piece of paper, for some reason. Every rectangle that he draws has a certain height *H* and a certain width *W*.

Oddly enough, he considers the variation between two different rectangles as *min(|H _{a} - H_{b}|, |W_{a} - W_{b}|)*, if the first rectangle is of dimensions

*H*x

_{a}*W*and the second rectangle is of dimensions

_{a}*H*x

_{b}*W*.

_{b}Gug starts off with an empty piece of paper, and he can, at any time, draw a new rectangle or remove an existing rectangle from the piece of paper. It is guaranteed that no two rectangles on the piece of paper at one time will have the exact same dimensions.

To test you, he also can show you a new rectangle, and ask you to find the rectangle on his piece of paper which it is most similar to (least variation). He then wants you to tell him what is its variation to this new rectangle.

## Implementation Details

This is a function call question. You are to implement these three functions:

void add_rectangle(int H, int W)

This function should add a rectangle with height `H`

and width `W`

. It is guaranteed that no existing rectangle with the same dimensions already exist on the piece of paper, and that the rectangle dimensions will be between 1 and 10^{9} inclusive.

void erase_rectangle(int H, int W)

This function should remove a rectangle of height `H`

and width `W`

from the piece of paper. It is guaranteed that a rectangle with the exact dimensions exist on the piece of paper.

int test_rectangle(int H, int W)

This function should return the minimum variation between this new rectangle of height `H`

and `W`

and any rectangle currently on his piece of paper. It is guranteed that there is at least one rectangle on his piece of paper, and that the query dimensions are between 1 and 10^{9} inclusive.

Under the *Attachments* tab, you are provided with a header file, sample grader, solution template, and a compile command. You are advised to test the solution locally before submission to the judge. A sample testcase simulating the sample interaction below is also included.

## Limits

Subtask 1 (30%): Total number of calls ≤ 3000.

Subtask 2 (32%): Total number of calls ≤ 300000, `erase_rectangle`

will not be called, all calls to `test_rectangle`

will be done after all calls to `add_rectangle`

.

Subtask 3 (38%): Total number of calls ≤ 300000.

Subtask 4 (0%): Sample Testcases.

## Sample Interaction

`add_rectangle(3, 5)`

is called.`add_rectangle(6, 9)`

is called.`test_rectangle(4, 11)`

is called. It should return `1`

.`test_rectangle(1, 3)`

is called. It should return `2`

.`erase_rectangle(3, 5)`

is called.`test_rectangle(4, 11)`

is called. It should return `2`

.
### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 30 | 21 | 2s | 256MB | Minimum |

2 | 32 | 20 | 2s | 256MB | Minimum |

3 | 38 | 61 | 2s | 256MB | Minimum |

4 | 0 | 1 | 2s | 256MB | Minimum |

### Judge Compile Command

g++-8 grader.cpp ans.cpp -o similarity -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512