Reconstruction of hv-Convex polyominoes

The problem is the following. We are given an empty n times m grid and an integer for each row and column, called row and column sums. The goal is to output a set of grid cells such that (a) the number of cells in each row and column is exactly the specified number, (b) the set of cells is connected, (c) every column and every row contains cells only in a single (possibly empty) interval.

This is known as the horizonal and vertical convex polyomino reconstruction problem from their vertical and horizontal projections. This page shows an implementation of an algorithm from [CD98b].

Input

Instance described by the following sums
row sums:
column sums:

Output