This is an interactive problem.

An equivalence relation $=$ is defined on set $D$, satisfying:

• Reflexivity: $\forall a \in D$, $a = a$.
• Transitivity: $\forall a, b, c \in D$, if $a = b$ and $b = c$, then $a = c$.
• Symmetry: $\forall a, b \in D$, if $a = b$, then $b = a$.

A total order relation $\leq$ is defined on set $D$, satisfying:

• Totality: $\forall a, b \in D$, $a \le b$ or $b \le a$.
• Transitivity: $\forall a, b, c \in D$, if $a \le b$ and $b \le c$, then $a \le c$.
• Antisymmetry: $\forall a, b \in D$, if $a \le b$ and $b \le a$, then $a = b$.

The strict total order relation $<$ associated with $\leq$ satisfies:

• $\forall a, b \in D$, $a < b$ if and only if $a \le b$ and $a \ne b$.

The strict majority element of a multiset $S$ consisting of elements from $D$ is an element $x$ such that the number of occurrences of $x$ in $S$ is strictly greater than half the size of the set. That is, $x$ is a strict majority element if and only if: $$\displaystyle \sum_{e \in S} [e = x] > \frac{1}{2}|S|$$

You need to maintain a multiset $S$ of elements from $D$ online (initially $S$ is empty, $\varnothing$), supporting the following operations:

• Insert: Given an element $x \in D$, add $x$ to the multiset $S$.
• Erase: Given an element $x \in D$, remove $x$ from the multiset $S$. It is guaranteed that $x \in S$. Specifically, if $x$ appears multiple times in $S$, you only need to remove exactly one instance.

After each operation, you must report whether a strict majority element exists in $S$. If it exists, you must also provide the strict majority element.

You may perform several queries to the interactor, each of which can be:

• Equivalence Test $\mathbf{E}$: Given elements $x, y \in D$, the interactor returns whether $x = y$ holds.
• Comparison Test $\mathbf{C}$: Given elements $x, y \in D$, the interactor returns whether $x \le y$ holds.

Each subtask limits the number of each type of test. Your score depends on the correctness of your answers and the number of each type of query performed after each operation.

Implementation Details

This is an interactive problem; only C++ is supported.

You do not need to, and should not, implement a main() function, nor should you read from or write to standard input/output or any files.

You must include the header file majority.h.

The header file defines the data type D_t, which describes elements in $D$.

The interactor overloads the following operators for D_t, corresponding to the binary relations mentioned above:

• The operator <= describes the binary relation $\le$. Its interface is:

bool operator<= (const D_t &rhs) const;

For two variables x and y of type D_t (representing $x, y \in D$), x <= y returns a bool value: true if $x \le y$, and false otherwise.

Calling the <= operator incurs a cost of $1$ unit of $\mathbf{C}$-cost.

• The operator == describes the binary relation $=$. Its interface is:

bool operator== (const D_t &rhs) const;

For two variables x and y of type D_t (representing $x, y \in D$), x == y returns a bool value: true if $x = y$, and false otherwise.

Calling the == operator incurs a cost of $1$ unit of $\mathbf{E}$-cost.

Additionally, for convenience, we have overloaded the operators >, >=, !=, and < as follows:

• a > b is equivalent to !(a <= b). Calling this operator incurs a cost of $1$ unit of $\mathbf{C}$-cost.
• a < b is equivalent to !(b <= a). Calling this operator incurs a cost of $1$ unit of $\mathbf{C}$-cost.
• a >= b is equivalent to b <= a. Calling this operator incurs a cost of $1$ unit of $\mathbf{C}$-cost.
• a != b is equivalent to !(a == b). Calling this operator incurs a cost of $1$ unit of $\mathbf{E}$-cost.

For debugging purposes, we provide the function get_value(). Calling this function returns the member variable info of the class D_t. This method is only included in the sample interactor to assist in debugging your algorithm. During evaluation, you must not obtain the value of info by any means; doing so will be considered an attack on the interactor, and your score will be invalidated.

You must implement the following functions:

bool insert(const D_t& x);

• This indicates that the interactor has initiated an insertion operation.
• You must return a bool value indicating whether a strict majority element exists in the set after the operation.
• Specifically, if the returned value is true, you must call the submit function to submit the strict majority element. See the description of the submit function below for details.

bool erase(int id);

• This indicates that the interactor has initiated an erasure operation.
  • The variable id represents that the element to be removed is the one inserted during the id-th insertion operation.
  • It is guaranteed that the element inserted during the id-th insertion operation has not been removed previously.
• You must return a bool value indicating whether a strict majority element exists in the set after the operation.
• Specifically, if the returned value is true, you must call the submit function to submit the strict majority element. See the description of the submit function below for details.

The interactor provides the submit function to submit your answer:

void submit(const D_t& x);

• When a strict majority element exists after an operation, you must call this function exactly once, where the parameter x represents the strict majority element in $S$.
• When no strict majority element exists after an operation, you should not call this function.

The function subtask_id() returns the subtask number of the current test case. In the sample interactor, this function always returns $0$.

int subtask_id();

Please note that the [Subtasks] section contains the scoring method for this problem. Specifically, if in your calls to insert and erase:

• You return the correct existence of a strict majority element but fail to call submit, or submit an incorrect answer.
• You provide a possible solution but the judgment of existence is incorrect.

You will receive partial credit.

Examples

The provided files include a sample interactor grader_majority.cpp, which you can use to help write your program.

Note that the interactor used during actual testing differs from this sample interactor; you should not rely on the implementation details of the sample interactor.

You can use the following command in your terminal to compile your program majority.cpp into an executable named majority:

g++ majority.cpp grader_majority.cpp -o majority -O2 -std=c++14

Note that the implementation of the interactor used in final testing differs from the sample interactor. You should not rely on the implementation of the sample interactor.

Input

The sample interactor reads input data from standard input in the following format:

The first line contains an integer $Q$, representing the number of operations.

The next $Q$ lines each contain two integers $\mathrm{op}~ x$, describing an operation:

• When $\mathrm{op} = 0$, it represents an insertion operation, inserting element $x$.
• When $\mathrm{op} = 1$, it represents an erasure operation, removing the element inserted during the $x$-th operation.

It is guaranteed that $\mathrm{op} \in \{0, 1\}$ and $0 \le x \le 10^5$. Note that when reading data for insertion operations, each variable of type D_t is represented by a non-negative integer. The constructor D_t(x) can convert a 32-bit unsigned integer x into the corresponding D_t variable.

Output

The sample interactor outputs to standard output in the following format:

• The first line contains information about your interaction process.
• The next $Q$ lines each contain two integers:
  • The first integer is in $\{ 0, 1 \}$, representing the value you returned in the call. $0$ represents false, and $1$ represents true.
  • The second integer is the value of info corresponding to your submitted answer. Specifically, if you did not submit any answer after this operation, the value is $-1$.

Examples

Input 1

5
0 1
0 1
0 2
0 2
1 2

Output 1

1 1
1 1
1 1
0 -1
1 2

Please note that the parameter $x$ for operation 1 refers to removing the element inserted in the $x$-th insertion operation, not removing the element with value $x$.

Input 2

13
0 1
0 2
0 3
0 1
0 1
1 4
1 5
0 2
0 2
1 6
1 7
0 3
0 3

Output 2

1 1
0 -1
0 -1
0 -1
1 1
0 -1
0 -1
0 -1
1 2
0 -1
0 -1
0 -1
1 3

Subtasks

Let $Q$ be the number of operations performed in a test case.

Explanations of the scoring methods:

• Let $C$ be the maximum $\mathbf{C}$-cost incurred in any single operation.
• Let $E$ be the maximum $\mathbf{E}$-cost incurred in any single operation.
• If $\max(C, E) \ge 1000$, your score is $0$ regardless of the scoring method.
• Scoring Method A:
  • If for every call, your answer regarding the existence of a strict majority element is correct, you receive $50\%$ of the points.
  • If for every call, you provide a possible candidate solution, you receive $50\%$ of the points.
  • Your final score is the sum of these two parts.
  • The interactor guarantees that in any interaction process where points can be obtained (which must satisfy $\max(C, E) \le 1\,000$), the interactor will use no more than $200$ ms and $16$ MB of memory.
• Scoring Method B:
  • Let $p \in (0, 1)$ be a scoring parameter:
    • If for every call, your answer regarding the existence of a strict majority element is correct AND you provide a possible candidate solution, $p = 100\%$.
    • If for every call, your answer regarding the existence of a strict majority element is correct, $p = 10\%$.
    • If for every call, you provide a possible candidate solution, $p = 10\%$.
    • Otherwise, $p = 0$.
  • If $C > 500$, your score is $4 \cdot p$.
  • Otherwise, if $C > 20$, your score is $9 \cdot p$.
  • Otherwise, if $C > 0$, your score is $15 \cdot p$.
  • Otherwise, if $E > 800$, your score is $18 \cdot p$.
  • Otherwise, if $E > 100$, your score is $\displaystyle \left(20 + 2 \times \frac{800-E}{100}\right) \cdot p$.
  • Otherwise, if $E > 10$, your score is $\displaystyle \left(35 + 2 \times \frac{100-E}{10}\right) \cdot p$.
  • Otherwise, if $E > 5$, your score is $(64 - E) \cdot p$.
  • Otherwise, if $E = 5$, your score is $60 \cdot p$.
  • Otherwise, if $E = 4$, your score is $64 \cdot p$.
  • Otherwise, if $E = 3$, your score is $69 \cdot p$.
  • Otherwise, your score is $74 \cdot p$.
• Your answer regarding the existence of a strict majority element is correct means:
  • When a strict majority element exists, you return true.
  • When no strict majority element exists, you return false.
  • Whether you call submit or whether the reported solution is correct does not affect this. You may submit or not submit any solution.
• You provide a possible candidate solution means:
  • When a strict majority element exists, you call submit exactly once, and the reported solution is the unique strict majority element.
  • When no strict majority element exists, whether you call submit or what solution you provide does not affect this.
  • The returned value of the function does not affect this; you may return any true or false.

That is, if you answer all queries correctly and satisfy $E \le 2$ and $C = 0$, you can receive full marks.

Note

Since the input data guarantees $0 \le x \le 10^5$, you can use D_t(-1), D_t(-2), etc., to generate objects that are not equal to any inserted elements.