프로젝트 팀 휴가 일정

$m$명으로 이루어진 팀이 연속된 $n$일의 근무일 동안 프로젝트를 진행한다. 근무일에는 1번부터 $n$번까지 번호를 붙인다. 팀원들의 휴가 일정을 짜는 것이 목표다.

팀원은 각자 $n$일의 근무일 중 최소 $p$일, 최대 $p'$일을 근무한다. $i = 1, \dots, n$에 대해 $i$번째 근무일에 근무하는 팀원 수는 $q_i$명 이상 $q_i'$명 이하여야 한다.

팀원은 각자 휴가 계획 목록

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

을 제출한다. 계획 $(d_t, [r_t, r_t'])$는 근무일 $r_t, r_t + 1, \dots, r_t'$ 중 최소 $d_t$일을 휴가로 쓰겠다는 뜻이다. 또 팀원은 이 기간들의 합집합 $\bigcup_{t=1}^{k}\{r : r_t \le r \le r_t'\}$에 속하지 않는 날에는 근무하려 하므로, 목록에 없는 날에는 휴가를 쓰지 않는다.

휴가 계획은 어느 날을 쉬는지까지 정하지 않는다. 계획이 $(2, [7, 9])$인 팀원은 $\{7, 8\}$, $\{7, 9\}$, $\{8, 9\}$ 중 어느 이틀을 쉬어도 되고, 사흘 $\{7, 8, 9\}$을 모두 쉴 수도 있다. $(2, [3, 4])$처럼 쉬는 날이 하나로 정해지는 계획도 있다.

위 조건을 모두 만족하도록 팀원 전원에게 휴가 날짜를 배정한 것을 휴가 일정이라고 한다. 팀원에는 1번부터 $m$번까지 번호가 붙어 있다. 휴가 일정이 존재하는지 판정하고, 존재하면 하나를 출력하라.

표준 입력으로 읽는다. 첫 줄에 양의 정수 $m$, $n$, $p$, $p'$가 주어진다. $m \le 100$, $n \le 100$, $p \le p' \le n$이다.

다음 $n$개 줄에는 $i = 1$부터 $n$까지 두 양의 정수 $q_i$와 $q_i'$가 주어진다. $q_i \le q_i' \le m$이다.

다음 $m$개 줄에는 팀원 한 명의 휴가 계획이 주어지며, 그중 $j$번째 줄이 $j$번 팀원의 계획이다. 계획 $(d_1, [r_1, r_1']), \dots, (d_k, [r_k, r_k'])$는 $3k + 1$개의 양의 정수 $k, d_1, r_1, r_1', d_2, r_2, r_2', \dots, d_k, r_k, r_k'$로 나타낸다. 한 팀원의 휴가 계획은 20개 이하다. 모든 $t$에 대해 $r_t \le r_t' \le n$이고 $d_t \le r_t' - r_t + 1$이다. 또 $r_1 < r_2 < \dots < r_k$이고, $a \ne b$이면 기간 $[r_a, r_a']$와 $[r_b, r_b']$는 겹치는 근무일이 없다.

표준 출력으로 쓴다. 첫 줄에는 모든 조건을 만족하는 휴가 일정이 존재하면 1, 존재하지 않으면 -1을 출력한다.

첫 줄이 1인 경우에만 $m$개 줄을 더 출력한다. 그중 $j$번째 줄에는 $j$번 팀원의 휴가 일정을 휴가 일수와 휴가 날짜를 오름차순으로 이어서 출력한다.

조건을 만족하는 휴가 일정이 여러 개일 수 있다. 그런 경우 다음 기준으로 사전순 최소인 일정을 출력한다. 휴가 일정을 $m$행 $n$열 표로 적고, $j$행 $i$열의 값은 $j$번 팀원이 $i$번째 날에 근무하면 0, 휴가면 1로 둔다. 이 표를 1번 팀원부터 행 단위로, 한 행 안에서는 1번째 날부터 읽어 0과 1의 수열을 만든다. 가능한 휴가 일정 가운데 이 수열이 사전순으로 가장 작은 것을 출력한다.

같은 규칙을 절차로 쓰면 이렇다. 팀원을 1번부터 $m$번까지 차례로 보고, 각 팀원에 대해 날짜를 1번째부터 $n$번째까지 차례로 본다. 지금까지 정한 결정을 모두 유지하면서 그 팀원이 그 날 근무하는 유효한 휴가 일정이 하나라도 있으면 근무로 정하고, 없으면 그 날을 휴가로 정한다.