406896: GYM102606 C Coronavirus Battle

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' \le x, y' \le y$$$ and $$$z' \le 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 \le n \le 10^5$$$), $$$k_1$$$ and $$$k_2$$$ ($$$10^8 \le k_1, k_2 \le 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), \ldots, (x_n, y_n, z_n)$$$ ($$$0 \le 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 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, \ldots, a_n$$$ ($$$0 \le a_i < t$$$). $$$a_i$$$ is the number of attacks the $$$i$$$-th leukocytes will survive.

5 998244353 1000000007

2
0 1 1 1 1

5 100000000 1000000000000

1
0 0 0 0 0

5 1000000000000 100000000

2
1 0 0 0 1

For the first example, the locations are:

8373945454928271 8388672858446274 535243480518893803
13645619435845943757 2297581721369636385 2065542152320352085
15149090731305068611 13847141931455896476 940493480722232539
17454784661911327411 15090004400591888349 684714220550566680
11704920635736733272 11725064299927455615 11820794347659711998

After the first one died, the rest can no longer protect each other, and won't survive the second attack.