A. Anti-Closed Subsequences
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We consider a set of integers $$$S$$$ to be anti-closed if there do not exist elements $$$x$$$, $$$y$$$ and $$$z$$$ in $$$S$$$ where $$$x+y=z$$$ ($$$x$$$, $$$y$$$ and $$$z$$$ do not necessarily have to be distinct).

For example:

  • $$$\{2, 3, 7\}$$$ is anti-closed, because no such $$$x$$$, $$$y$$$, $$$z$$$ exist
  • $$$\{1, 3, 7, 10\}$$$ is not anti-closed, because $$$3$$$, $$$7$$$, and $$$10$$$ are all in the set and $$$3+7=10$$$
  • $$$\{2, 4\}$$$ is also not anti-closed, because $$$2$$$ and $$$4$$$ are in the set and $$$2+2=4$$$

You are given an array $$$a$$$ of $$$n$$$ distinct integers. Partition it into at most $$$60$$$ anti-closed subsequences. Formally, find an array $$$b$$$ of size $$$n$$$ such that

  • $$$1 \leq b_i \leq 60$$$ for all $$$1 \le i \le n$$$
  • For each $$$1 \le x \le 60$$$, the subsequence of $$$a$$$ containing all values at indices $$$i$$$ where $$$b_i = x$$$ is anti-closed (The empty subsequence is considered anti-closed)

It can be shown that a solution always exists.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^4$$$) — the size of the array $$$a$$$.

The next line of the input contains $$$n$$$ distinct integers $$$a_1, a_2 \cdots a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — the elements of the array $$$a$$$.

Output

Output $$$n$$$ integers $$$b_1, b_2, \cdots b_n$$$ ($$$1 \le b_i \le 60$$$), representing the partition of $$$a$$$, as described above.

If there are multiple solutions, print any.

Examples
Input
15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Output
1 2 2 1 3 1 3 3 2 2 4 4 4 2 1
Input
3
250000000000000000 500000000000000000 1000000000000000000
Output
1 2 3
Note

For the first test case, the input array is partitioned into these subsequences:

  • $$$b_i = 1$$$: $$$\{1, 4, 6, 15\}$$$
  • $$$b_i = 2$$$: $$$\{2, 3, 9, 10, 14\}$$$
  • $$$b_i = 3$$$: $$$\{5, 7, 8\}$$$
  • $$$b_i = 4$$$: $$$\{11, 12, 13\}$$$

We can show that each of these sets is anti-closed.