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

There are $n$ earthworms (where $n$ is a positive integer). Each earthworm has a length, and we denote the length of the $i$-th earthworm as $a_i$ ($i = 1, 2, \dots, n$). All lengths are non-negative integers (i.e., it is possible for an earthworm to have a length of 0).

Every second, you must accurately find the longest earthworm (if there are multiple, choose any one) and cut it into two pieces. The position of the cut is determined by a ratio $p$ (where $0 < p < 1$ is a rational number). If the length of the chosen earthworm is $x$, you will cut it into two pieces with lengths $\lfloor px \rfloor$ and $x - \lfloor px \rfloor$. Specifically, if one of these two pieces has a length of 0, that piece is also kept. Furthermore, except for the two new earthworms just created, the lengths of all other earthworms will increase by $q$ (a non-negative constant).

You need to know the state of the earthworms after $m$ seconds (where $m$ is a non-negative integer). Specifically, you want to know: The lengths of the earthworms cut in each of the $m$ seconds (before they are cut). The lengths of all earthworms after $m$ seconds (in descending order).

Input

The input is read from the file earthworm.in.

The first line contains six integers $n, m, q, u, v, t$. Here, $n, m, q$ have the meanings described above; $u, v, t$ are positive integers. You should calculate $p = u/v$ (given $0 < u < v$); $t$ is an output parameter, the meaning of which is explained in the Output section.

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

Two adjacent numbers on the same line are separated by a single space.

Constraints: $1 \le n \le 10^5$, $0 \le m \le 7 \times 10^6$, $0 < u < v \le 10^9$, $0 \le q \le 200$, $1 \le t \le 71$, $0 \le a_i \le 10^8$.

Output

The output is written to the file earthworm.out.

The first line outputs $\lfloor \frac{m}{t} \rfloor$ integers, outputting the lengths of the earthworms cut at the $t$-th second, $2t$-th second, $3t$-th second, $\dots$ (before they are cut) in chronological order.

The second line outputs $n+m$ integers, outputting the lengths of the earthworms after $m$ seconds, sorted in descending order.

Two adjacent numbers on the same line are separated by a single space. Even if there are no numbers to output on a line, you should output an empty line.

Examples

Input 1

3 7 1 1 3 1
3 3 2

Output 1

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

Note 1

Before the cuts: The lengths of the 3 earthworms are 3, 3, 2. After 1 second: An earthworm of length 3 is cut into two pieces of length 1 and 2. The remaining earthworms increase by 1. The lengths of the 4 earthworms are (1, 2), 4, 3. (Parentheses indicate the position where an earthworm was just cut). 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 at 7 seconds are 3, 4, 4, 4, 5, 5, 6. After 7 seconds, all earthworm lengths sorted from largest to smallest are 6, 6, 6, 5, 5, 4, 4, 3, 2, 2.

Input 2

3 7 1 1 3 2
3 3 2

Output 2

4 4 5
6 5 4 3 2

Note 2

This data only differs from the previous one in that $t=2$. We only need to output every second number in each line. Although the last 6 in the first line was not output, the second line still needs to start outputting from the second number.

Input 3

3 7 1 1 3 9
3 3 2

Output 3

2

Note 3

This data only differs from the previous one in that $t=9$. Note that the first line has no numbers to output, but an empty line must still be output.

Subtasks

• Test cases 1~3 satisfy $m = 0$.
• Test cases 4~7 satisfy $n, m \le 1,000$.
• Test cases 8~14 satisfy $q = 0$, among which test cases 8~9 also satisfy $m \le 10^5$.
• Test cases 15~18 satisfy $m \le 3 \times 10^5$.
• Test cases 19~20 have no special constraints; refer to the original data range.
• Test cases 1~12, 15~16 also satisfy $v \le 2$, which means the only possible values for $u, v$ are $u=1, v=2$, i.e., $p=0.5$. This may be helpful for solving the problem.

Detailed data ranges for each test case are in the table below.