Problem D
Architecture
Your brother has won an award at the recent Breakthroughs in Architectural Problems Conference and has been given the once in a lifetime opportunity of redesigning the city center of his favorite city Nijmegen. Since the most striking parts of a city’s layout are the skylines, your brother has started by drawing ideas for how he wants the northern and eastern skylines of Nijmegen to look. However, some of his proposals look rather outlandish, and you are starting to wonder whether his designs are possible.
For his design, your brother has put an $R\times C$ grid on the city. Each cell of the city will contain a building of a certain height. The eastern skyline is given by the tallest building in each of the $R$ rows, and the northern skyline is given by the tallest building in each of the $C$ columns.
A pair of your brother’s drawings of skylines is possible if and only if there exists some way of assigning building heights to the grid cells such that the resulting skylines match these drawings.
Figure 1 shows a possible city with the northern and eastern skylines exactly as given in the input of the first sample.
|
$1$ |
$2$ |
$3$ |
$4$ |
|
$0$ |
$1$ |
$2$ |
$3$ |
|
$1$ |
$2$ |
$1$ |
$1$ |
|
$1$ |
$0$ |
$1$ |
$1$ |
Input
-
The first line consists of two integers $1 \leq R, C \leq 100$, the number of rows and columns in the grid.
-
The second line consists of $R$ integers $x_1, \dots , x_ R$ describing the eastern skyline (${0 \le x_ i \le 1\, 000}$ for all $i$).
-
The third line consists of $C$ integers $y_1, \dots , y_ C$ describing the northern skyline (${0 \le y_ j \le 1\, 000}$ for all $j$).
Output
Output one line containing the string possible if there exists a city design that produces the specified skyline, and impossible otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 4 4 3 2 1 1 2 3 4 |
possible |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 4 1 2 3 4 1 2 3 2 |
impossible |
