The Worm Cutting Game

In this problem, we denote the floor of a real number \(c\) by \(\lfloor c \rfloor\). For example, \(\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3\).

The Kingdom of Crickets is facing a severe earthworm crisis! With earthworms overrunning the land and even affecting the neighboring Kingdom of Fleas, King Cricket has turned to a divine knife-wielder to help eliminate the pests.

Initially, there are \(n\) earthworms. The \(i\)-th worm has an initial length \(a_i\) (\(i=1,2,\dots,n\)) where \(a_i \ge 0\). Every second, the divine knife-wielder performs the following operations:

• Select the worm with the maximum length (if there are multiple, any one may be chosen) and record its length \(x\) before cutting.
• Cut this worm at a position determined by the constant \(p\) (a rational number satisfying \(0<p<1\)), splitting it into two worms with lengths \(\lfloor px \rfloor\) and \(x-\lfloor px \rfloor\). Note that even if one of these lengths is \(0\), it is still kept.
• Increase the lengths of all the other worms (i.e. the ones that were not just produced) by \(q\), where \(q\) is a non-negative integer.

This process continues for \(m\) seconds. After \(m\) seconds, the total number of worms becomes \(n+m\) because each second the worm count increases by one.

Your task is to output two things:

1. The list of recorded lengths of the worm chosen for cutting in each of the \(m\) seconds.
2. The lengths of all \(n+m\) worms after \(m\) seconds.

inputFormat

The first line contains four values: an integer \(n\) (the number of worms), an integer \(m\) (the number of seconds), a rational number \(p\) (with \(0<p<1\)), and an integer \(q\) (with \(q\ge0\)).

The second line contains \(n\) non-negative integers \(a_1,a_2,\dots,a_n\) — the initial lengths of the worms.

outputFormat

Output two lines:

The first line should contain \(m\) integers, where the \(i\)-th integer is the length of the worm cut in the \(i\)-th second (before the cut).

The second line should contain \(n+m\) integers representing the lengths of all the worms after \(m\) seconds.

sample

3 2 0.5 1
2 5 3

5 4
4 3 4 2 2

</p>