Description

The only difference between this question and Big orange cat's puzzle III is the input constraints.

Based on his previous three experiences (hw4, lab4, mid1), Big Orange Cat has finally figured out which puzzle pieces to choose!

He has now completed 90% of the puzzle. The current puzzle can be represented as an n x m matrix A, with -1 indicating unfilled spaces.
Fortunately, he knows that the sum of numbers in each row should be approximately S_i. However, there might be some error, so the actual sum could be in the range [S_i - P, S_i + P].

He now has k puzzle pieces B₁ to B_k. Please tell him how many ways he can use pieces from B to fill the puzzle so that each row's sum falls within the specified range. Also, find the method with the smallest lexicographical order.

The lexicographical order for this puzzle starts from the top-left corner A_1,1, then A_1,2, and so on. After comparing the first row, move to the second row, following a left-to-right, top-to-bottom rule. For detailed examples, please refer to the sample output.

Input

The first line of input contains four integers n, m, k, P, separated by spaces.

The second line contains k integers B₁ to B_k, separated by spaces.

The next n lines each contain m integers A_i,1 to A_i,m.

The last line contains n integers representing S₁ to S_n.

Constraints

• 1 <= n, k <= 10
• 1 <= m <= 10⁵
• In matrix A, the number of occurrences of -1 will not exceed 10 times.
• -1 <= A_{i, j} <= 10
• 1 <= B_i, S_i, P <= 10⁹

Subtasks

• testcases 1 ~ 2: n = 1, -1 will appear at most once in each row.
• testcases 3 ~ 4: n = 1
• testcases 5 ~ 6: n <= 10, -1 will appear at most once in each row.
• testcases 7 ~ 8: n <= 10
• testcases 9 ~ 10: No additional restrictions.

Output

There are two types of output based on different situations:

1. If there is no way to fill in the puzzle: Output a single line with "baganono" (without quotes).
2. If there is a way to fill in the puzzle:
   The first line outputs a positive integer representing the number of possible methods.
   The next n lines each output m integers representing the matrix filled using the method with the smallest lexicographical order.

Please remember to print "\n" at the end, and dont print space (" ") at the end of every line.

Sample Input  Download

Sample Output  Download

Tags

Discuss