Safe Foraging Plan

In the kingdom of rabbits, a terrible flood has caused a famine. There are ( n ) rabbits numbered from ( 1 ) to ( n ), and for ( m ) days before the relief food arrives, exactly ( k ) rabbits must go out each day to search for food in a dangerous forest. In the forest live wolves that, on each day, will prey on a fixed set of rabbits. For day ( i ), let ( F_i ) be the set of rabbits that the wolves will attack. The rabbits must select a set ( S_i ) of ( k ) rabbits for day ( i ) such that ( S_i \cap F_i = \varnothing ) (i.e. no rabbit going out is attacked by the wolves).

Furthermore, because the group of foraging rabbits is not always the same, the rabbits define a novelty (or "strangeness") ( p_i ) for day ( i ) as the number of rabbits in ( S_i ) which did not forage on day ( i-1 ), i.e. ( p_i = |S_i \setminus S_{i-1}| ) for ( i \ge 2 ) (with ( p_1 ) defined as ( 0 )). The plan must ensure that for each day, ( p_i \leq l ).

Construct a plan (i.e. choose ( S_1, S_2, \dots, S_m )) that satisfies both the safety condition and the novelty bound.

inputFormat

The input consists of multiple lines. The first line contains four integers ( n ), ( m ), ( k ), and ( l ) — the total number of rabbits, the number of days, the number of rabbits that must forage each day, and the maximum allowed novelty, respectively.

For the next ( m ) lines, each line describes the list of forbidden rabbits for that day. Each such line begins with an integer ( r ) representing the number of rabbits the wolves will attack that day, followed by ( r ) distinct integers (each between ( 1 ) and ( n )) specifying their indices.

outputFormat

Output exactly ( m ) lines. The ( i\text{-th} ) line should contain ( k ) space‑separated integers representing the indices of the rabbits chosen for day ( i ). The chosen set ( S_i ) must satisfy ( S_i \cap F_i = \varnothing ), and for every day ( i \ge 2 ), it must hold that (|S_i \setminus S_{i-1}| \le l).

sample

5 3 2 1
1 3
1 2
1 5

1 2
1 3
1 3