Domino Painter - Repovive Premier Round 5 | Repovive

13E. Domino Painter

2500 pts2s256 MB

There is an infinite grid. A cell is identified by a pair of integer coordinates $(x,y)$ .

A domino covers exactly two cells sharing a side. There are two types of dominoes:

Type $1$ : the domino covers cells $(x,y)$ and $(x+1,y)$ .
Type $2$ : the domino covers cells $(x,y)$ and $(x,y+1)$ .

In both cases, $(x,y)$ is the cell of the domino with the smallest coordinates.

You are given $q$ operations. Each operation either adds a new domino to the grid or removes an existing domino from the grid. The operations are valid: an added domino is placed on two currently empty cells, and a removed domino is currently present.

For every added domino, choose a color for it: one of $1,2,3,4$ .

After every operation, for every two dominoes that are both present in the grid and have two cells sharing a side, their colors must be different.

Constraints

$1 \le q \le 10^4$
$0 \le x, y \le 10^6$
Each added domino is placed on two currently empty cells
Each removed domino is currently present in the grid

Input

q

\left. \begin{array}{l} op \quad t \quad x \quad y \end{array} \right\} \times q

Each $op_i$ is either +, meaning add a domino, or -, meaning remove a domino.

Each $t_i$ denotes the type of the domino: $1$ for cells $(x_i, y_i)$ and $(x_i+1, y_i)$ , and $2$ for cells $(x_i, y_i)$ and $(x_i, y_i+1)$ .

Output

For every operation with $op_i =$ +, output one integer: the color assigned to the newly added domino.

If there are $m$ add operations, the output format is:

c_1 \quad c_2 \quad \cdots \quad c_m

The colors must be given in the same order as the add operations.

Each color must be an integer between $1$ and $4$ .

Samples

Input

Explanation

There are 8 add operations, so the output contains 8 colors.

The first domino has no active neighbor, so color 1 is valid.

The second domino is adjacent to the first one and receives color 2, so they have different colors.

The third domino is adjacent to the first one and receives color 3.

The fourth domino is adjacent to the first and second dominoes, and color 3 is different from the colors of both active adjacent dominoes.

After removing the second domino, the fifth added domino receives color 1. It is adjacent to the fourth domino, whose color is 3.

The sixth added domino receives color 2 and is adjacent to the third domino, whose color is 3.

After removing the third domino, the seventh added domino receives color 4. Its active adjacent dominoes have colors 1 and 3.

The last added domino receives color 2. Its only active adjacent domino has color 1.

Output

1 2 3 3 1 2 4 2

There is an infinite grid. A cell is identified by a pair of integer coordinates $(x,y)$ .

A domino covers exactly two cells sharing a side. There are two types of dominoes:

Type $1$ : the domino covers cells $(x,y)$ and $(x+1,y)$ .
Type $2$ : the domino covers cells $(x,y)$ and $(x,y+1)$ .

In both cases, $(x,y)$ is the cell of the domino with the smallest coordinates.

For every added domino, choose a color for it: one of $1,2,3,4$ .

After every operation, for every two dominoes that are both present in the grid and have two cells sharing a side, their colors must be different.

$1 \le q \le 10^4$
$0 \le x, y \le 10^6$
Each added domino is placed on two currently empty cells
Each removed domino is currently present in the grid

q

\left. \begin{array}{l} op \quad t \quad x \quad y \end{array} \right\} \times q

Each $op_i$ is either +, meaning add a domino, or -, meaning remove a domino.

Each $t_i$ denotes the type of the domino: $1$ for cells $(x_i, y_i)$ and $(x_i+1, y_i)$ , and $2$ for cells $(x_i, y_i)$ and $(x_i, y_i+1)$ .

For every operation with $op_i =$ +, output one integer: the color assigned to the newly added domino.

If there are $m$ add operations, the output format is:

c_1 \quad c_2 \quad \cdots \quad c_m

The colors must be given in the same order as the add operations.

Each color must be an integer between $1$ and $4$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

13E. Domino Painter

Constraints

Input

Output

Samples

13E. Domino Painter

Constraints

Input

Output

Samples