As COVID-19 is rampantly infecting more and more people, casting a devastating impact on human-world, Cuber QQ, as a super-man, is busy travelling around the world saving lives, and meanwhile putting his own health under threat.
However, as a super-man, Cuber QQ has a different immune system from a normal human being. For simplicity, Cuber QQ's immune system can be modeled as thousands of leukocytes, sophisticatedly arranged into a phalanx, in a three dimensional space. Each of them has a distinct location $(x, y, z)$ where $x$, $y$ and $z$ are positive integers. When the virus initiates one attack, it always comes from negative-$x$, negative-$y$ and negative-$z$ direction. A leukocyte can survive this attack, if and only if it is protected by another cell whose location is more exposed to virus, i.e., a leukocyte with location $(x ', y ', z ')$ where $x ' <= x, y ' <= y$ and $z ' <= z$, and at least one of $x ' < x, y ' < y, z ' < z$ is satisfied. If a leukocyte is not protected during this round of attack, it will die immediately and cannot protect others any more in future. Otherwise, it will survive.
Sophisticated as the system is, with the virus attacking over and over again, eventually all the leukocytes will die and Cuber QQ's immune system will crash, after which he shall be very sick. Nevertheless, Cuber QQ is a super-man who is willing to push his limits and fight as he can. He wants to know how much time he has got left. And you, as the best programmer in Cuber-ECNU-Joint-Force-Facility, are just given 4 hours to figure out how many rounds of attacks our world's hero will be put through before he falls down.
The first and only line of the input contains three space-separated integers $n$ ($1 <= n <= 10^5$), $k_1$ and $k_2$ ($10^8 <= k_1, k_2 <= 10^(12)$).
The following code describes the algorithm Cuber QQ's immune system used to arranage the cells. It is written in C++, and surely you can convert it to any other language you would like to use. With this algorithm, $(x_1, y_1, z_1), \\dots, (x_n, y_n, z_n)$ ($0 <= x_i, y_i, z_i < 2^(64)$) can be generated.
Except for the examples, $k_1$ and $k_2$ are randomly chosen. And it is guaranteed that all locations generated will be distinct.
Output the number of attacks $t$ before Cuber QQ's immune system is destroyed.
To increase the credibility of your answer, in the next line, you also need to print $n$ integers $a_1, a_2, \\dots, a_n$ ($0 <= a_i < t$). $a_i$ is the number of attacks the $i$-th leukocytes will survive.
For the first example, the locations are:
After the first one died, the rest can no longer protect each other, and won't survive the second attack.
## Input
The first and only line of the input contains three space-separated integers $n$ ($1 <= n <= 10^5$), $k_1$ and $k_2$ ($10^8 <= k_1, k_2 <= 10^(12)$).The following code describes the algorithm Cuber QQ's immune system used to arranage the cells. It is written in C++, and surely you can convert it to any other language you would like to use. With this algorithm, $(x_1, y_1, z_1), \\dots, (x_n, y_n, z_n)$ ($0 <= x_i, y_i, z_i < 2^(64)$) can be generated.unsigned long long k1, k2;unsigned long long CoronavirusBeats() { unsigned long long k3 = k1, k4 = k2; k1 = k4; k3 ^= k3 « 23; k2 = k3 ^ k4 ^ (k3 » 17) ^ (k4 » 26); return k2 + k4;}for (int i = 1; i <= n; ++i) { x[i] = CoronavirusBeats(); y[i] = CoronavirusBeats(); z[i] = CoronavirusBeats();}Except for the examples, $k_1$ and $k_2$ are randomly chosen. And it is guaranteed that all locations generated will be distinct.
## Output
Output the number of attacks $t$ before Cuber QQ's immune system is destroyed.To increase the credibility of your answer, in the next line, you also need to print $n$ integers $a_1, a_2, \\dots, a_n$ ($0 <= a_i < t$). $a_i$ is the number of attacks the $i$-th leukocytes will survive.
[samples]
## Note
For the first example, the locations are:8373945454928271 8388672858446274 53524348051889380313645619435845943757 2297581721369636385 206554215232035208515149090731305068611 13847141931455896476 94049348072223253917454784661911327411 15090004400591888349 68471422055056668011704920635736733272 11725064299927455615 11820794347659711998After the first one died, the rest can no longer protect each other, and won't survive the second attack.
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ k_1, k_2 \in \mathbb{Z} $ with $ 10^8 \leq k_1, k_2 \leq 10^{12} $.
Let $ (x_i, y_i, z_i) \in \mathbb{Z}^3 $, $ i \in \{1, \dots, n\} $, be distinct points generated by the given deterministic algorithm (LFSR-style), satisfying $ 0 \leq x_i, y_i, z_i < 2^{64} $.
**Partial Order**
Define a partial order $ \preceq $ on the set of points:
$ (x', y', z') \preceq (x, y, z) $ if and only if $ x' \leq x $, $ y' \leq y $, $ z' \leq z $, and at least one inequality is strict.
**Attack Dynamics**
In each attack round:
- A leukocyte at $ (x_i, y_i, z_i) $ survives if and only if there exists another leukocyte at $ (x_j, y_j, z_j) $ such that $ (x_j, y_j, z_j) \preceq (x_i, y_i, z_i) $.
- Surviving leukocytes remain; others are removed.
- Process repeats until no leukocytes remain.
**Objective**
Let $ t \in \mathbb{Z}^+ $ be the number of attack rounds until all leukocytes are eliminated.
Let $ a_i \in \{0, 1, \dots, t-1\} $ be the number of rounds leukocyte $ i $ survives (i.e., the round in which it dies, with 0-indexed rounds).
Compute:
1. $ t $: the total number of rounds until system collapse.
2. $ (a_1, a_2, \dots, a_n) $: the death round index for each leukocyte.
**Note**
The coordinates $ (x_i, y_i, z_i) $ are generated by an unspecified deterministic algorithm (LFSR-based), but all points are distinct. The problem reduces to computing the **height of the poset** under the dominance order $ \preceq $, and the **level** of each element in the greedy layer decomposition (Dilworth-type decomposition into antichains).