16368번 - Working Plan 스페셜 저지다국어

문제

ICPC manager plans a new project which is to be carried out for n days. In this project, m persons numbered from 1 to m are supposed to work. Each day j (1 ≤ j ≤ n) requires d_j persons, and each person i (1 ≤ i ≤ m) wants to work w_idays.

To increase the efficiency in performing the project, the following two conditions should be satisfied:

1. each person works for only consecutive w days when he/she works, and
2. each person can work again after he/she has a rest for at least h days.

ICPC manager wants to find a working plan to assign the working days for all persons such that the number of working days of each person i (1 ≤ i ≤ m) is equal to w_i and the number of persons who work for each day j (1 ≤ j ≤ n) is equal to d_j, and above two conditions are also satisfied.

For example, assume the project is carried out for n = 9 days, and m = 4 persons participate in the project. Let w = 2 and h = 1. Also, assume (w₁, w₂, w₃, w₄) = (4, 4, 6, 2) and (d₁, d₂, d₃, d₄, d₅, d₆, d₇, d₈, d₉) = (1, 3, 2, 1, 2, 1, 1, 3, 2). The table below shows a feasible solution where the i-th row corresponds to person i, and the j-th column corresponds to day j. If person i works or has a rest in day j, the value of the table element with row i and column j is 1 or 0, respectively.

Given m, n, w, h, w_i (1 ≤ i ≤ m) which is a multiple of w, and d_j (1 ≤ j ≤ n), write a program to find a feasible solution as a working plan.

입력

Your program is to read from standard input. The input starts with a line containing four integers, m, n, w, h (1 ≤ m ≤ 2,000, 1 ≤ n ≤ 2,000, 1 ≤ w, h ≤ n). The following line contains m integers where the i-th (1 ≤ i ≤ m) integer represents w_i (1 ≤ w_i ≤ n) which is a multiple of w. The next line contains n integers where the j-th (1 ≤ j ≤ n) integer represents d_j (0 ≤ d_j ≤ m).

출력

Your program is to write to standard output. If there is a feasible working plan, print 1 in the first line followed by m lines, each i-th (1 ≤ i ≤ m) line should contain w_i/w integers. These integers form an increasing sequence of first days that person i works in the feasible plan. If there is no feasible working plan, print only -1 in the first line. The first sample below corresponds to the example given in the table above.

제한

힌트