Project Team Vacation Schedule

A team of $m$ members runs a project over $n$ consecutive working days, numbered 1 to $n$. You draw up the vacation schedule of the members.

Every member works on at least $p$ and at most $p'$ of the $n$ working days. On working day $i$ the number of members who work must be at least $q_i$ and at most $q_i'$, for $i = 1, \dots, n$.

Each member also submits a list of vacation plans

$(d_1, [r_1, r_1']), (d_2, [r_2, r_2']), \dots, (d_k, [r_k, r_k']).$

The plan $(d_t, [r_t, r_t'])$ means the member takes at least $d_t$ vacation days among the working days $r_t, r_t + 1, \dots, r_t'$. The member also wants to work on every day outside the union of those periods, $\bigcup_{t=1}^{k}\{r : r_t \le r \le r_t'\}$, so a member never takes a vacation day outside the listed periods.

A vacation plan does not fix which days the vacation days are. A member holding the plan $(2, [7, 9])$ can take the two days $\{7, 8\}$, $\{7, 9\}$ or $\{8, 9\}$, and can also take all three days $\{7, 8, 9\}$. For a plan such as $(2, [3, 4])$ the vacation days are fixed.

An assignment of vacation days to every member that satisfies all the constraints above is a vacation schedule. Members are numbered 1 to $m$. Decide whether a vacation schedule exists, and print one when it does.

Read from standard input. The first line contains four positive integers $m$, $n$, $p$ and $p'$, where $m \le 100$, $n \le 100$ and $p \le p' \le n$.

Each of the next $n$ lines contains two positive integers $q_i$ and $q_i'$ for $i = 1$ to $n$, where $q_i \le q_i' \le m$.

Each of the next $m$ lines holds the vacation plans of one member, the $j$-th of these lines belonging to member $j$. The plans $(d_1, [r_1, r_1']), \dots, (d_k, [r_k, r_k'])$ are given as a sequence of $3k + 1$ positive integers: $k, d_1, r_1, r_1', d_2, r_2, r_2', \dots, d_k, r_k, r_k'$. A member has at most 20 vacation plans. For every $t$, $r_t \le r_t' \le n$ and $d_t \le r_t' - r_t + 1$. Also $r_1 < r_2 < \dots < r_k$, and the periods $[r_a, r_a']$ and $[r_b, r_b']$ share no working day when $a \ne b$.

Write to standard output. The first line contains 1 when a vacation schedule satisfying every constraint exists, and -1 when none exists.

When and only when the first line is 1, print $m$ more lines. The $j$-th of them describes the vacation schedule of member $j$ as the number of vacation days followed by the vacation days in increasing order.

Several vacation schedules can satisfy all the constraints. In that case print the lexicographically smallest one, under the following comparison. Write a schedule as a table of $m$ rows and $n$ columns whose entry in row $j$ and column $i$ is 0 when member $j$ works on day $i$ and 1 when member $j$ is on vacation on day $i$. Read the table row by row, member 1 first, and inside a row day 1 first, which gives a sequence of 0s and 1s. Among all valid schedules, print the one whose sequence is lexicographically smallest.

The same rule stated as a procedure: walk through the members in order 1 to $m$ and, for each member, through the days in order 1 to $n$. Let the member work on the current day when at least one valid schedule keeps every decision already made and has that member working on that day. Otherwise the member takes that day off.