Problem Background

NOIP2016 Senior Group D2T2

Problem Description

In this problem, we will use the symbol $\lfloor c \rfloor$ to denote the floor function of $c$, for example: $\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$.

Recently, the cricket country is plagued by earthworms! The fleas from the neighboring flea country are also helpless against them. The cricket king has no choice but to invite a skilled swordsman to help them eliminate the earthworms.

Currently, there are $n$ earthworms in the cricket country (where $n$ is a positive integer). Each earthworm has a length. We denote the length of the $i$-th earthworm as $a_i$ (where $i=1,2,\dots,n$), and we guarantee that all lengths are non-negative integers (i.e., there may be earthworms with a length of $0$).

Every second, the swordsman will accurately find the longest earthworm (if there are multiple, any one will be chosen) and cut it into two halves. The position at which the earthworm is cut is determined by a constant $p$ (a rational number satisfying $0 < p < 1$). Suppose the length of this earthworm is $x$, the swordsman will cut it into two earthworms with lengths $\lfloor px \rfloor$ and $x - \lfloor px \rfloor$. Specifically, if one of these numbers is $0$, the earthworm with a length of $0$ will also be retained. Additionally, except for the two newly created earthworms, the lengths of all other earthworms will increase by $q$ (a non-negative integer constant).

The cricket king knows that this is not a long-term solution because the earthworms not only increase in number but also in length. The cricket king decides to seek help from a mysterious figure with immense power, but the reinforcements will take $m$ seconds to arrive... (where $m$ is a non-negative integer).

The cricket king wants to know the situation during these $m$ seconds. Specifically, he wants to know:

• The lengths of the earthworms that were cut before being cut, for each second within $m$ seconds (there will be $m$ numbers);
• The lengths of all earthworms after $m$ seconds (there will be $n + m$ numbers).

The cricket king knows how to do it, but he wants to test you...

Input Format

The first line contains six integers $n, m, q, u, v, t$, where: $n, m, q$ have the meanings described in the problem; $u, v, t$ are positive integers; you need to calculate $p = u / v$ (guaranteed $0 < u < v$); $t$ is an output parameter, the meaning of which will be explained in the Output Format.

The second line contains $n$ non-negative integers, which are $a_1, a_2, \dots, a_n$, representing the initial lengths of the $n$ earthworms.

Adjacent numbers in the same line are separated by exactly one space.

It is guaranteed that $1 \leq n \leq 10^5$, $0 \leq m \leq 7 \times 10^6$, $0 < u < v \leq 10^9$, $0 \leq q \leq 200$, $1 \leq t \leq 71$, $0 \leq a_i \leq 10^8$.

Output Format

The first line should output $\left \lfloor \frac{m}{t} \right \rfloor$ integers, in chronological order, outputting the lengths of the earthworms (before being cut) at the $t$-th second, the $2t$-th second, the $3t$-th second, and so on.

The second line should output $\left \lfloor \frac{n+m}{t} \right \rfloor$ integers, outputting the lengths of the earthworms after $m$ seconds; they need to be output in descending order, starting from the $t$-th largest, then the $2t$-th largest, the $3t$-th largest, and so on.

Adjacent numbers in the same line are separated by exactly one space. Even if there are no numbers to output on a line, you should still output a blank line.

Please read the sample to better understand this format.

Sample Input and Output

Input Sample #1

3 7 1 1 3 1
3 3 2

Output Sample #1

3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2

Input Sample #2

3 7 1 1 3 2
3 3 2

Output Sample #2

4 4 5
6 5 4 3 2

Input Sample #3

3 7 1 1 3 9
3 3 2

Output Sample #3

// Empty line
2

Notes

Sample Explanation 1

Before the swordsman arrives: The lengths of the 3 earthworms are $3, 3, 2$.

After 1 second: An earthworm of length $3$ is cut into two with lengths $1$ and $2$, and the lengths of the other earthworms increase by $1$. Finally, the lengths of the 4 earthworms are $(1, 2), 4, 3$. Parentheses indicate that an earthworm was just cut at this position.

After 2 seconds: An earthworm of length $4$ is cut into $1$ and $3$. The lengths of the 5 earthworms are: $2, 3, (1, 3), 4$.

After 3 seconds: An earthworm of length $4$ is cut. The lengths of the 6 earthworms are: $3, 4, 2, 4, (1, 3)$.

After 4 seconds: An earthworm of length $4$ is cut. The lengths of the 7 earthworms are: $4, (1, 3), 3, 5, 2, 4$.

After 5 seconds: An earthworm of length $5$ is cut. The lengths of the 8 earthworms are: $5, 2, 4, 4, (1, 4), 3, 5$.

After 6 seconds: An earthworm of length $5$ is cut. The lengths of the 9 earthworms are: $(1, 4), 3, 5, 5, 2, 5, 4, 6$.

After 7 seconds: An earthworm of length $6$ is cut. The lengths of the 10 earthworms are: $2, 5, 4, 6, 6, 3, 6, 5, (2, 4)$. Therefore, the lengths of the earthworms cut within 7 seconds are $3, 4, 4, 4, 5, 5, 6$. After 7 seconds, the lengths of all earthworms sorted in descending order are $6, 6, 6, 5, 5, 4, 4, 3, 2, 2$.

Sample Explanation 2

This data only differs from the previous one in that $t = 2$. Simply output every two numbers on each line.

Although the last $6$ on the first line is not output, the second line still needs to start outputting from the second number.

Sample Explanation 3

This data only differs from the previous one in that $t = 9$.

Note that there are no numbers to output on the first line, but a blank line should still be output.

见题面 Input 部分

见题面 Output 部分