건축

형이 최근 Breakthroughs in Architectural Problems Conference에서 상을 받았고, 가장 좋아하는 도시 Nijmegen의 도심을 다시 설계할 일생일대의 기회를 얻었다. 도시 배치에서 가장 눈에 띄는 부분이 스카이라인이므로, 형은 Nijmegen의 북쪽과 동쪽 스카이라인이 어떻게 보이길 원하는지에 대한 아이디어를 그리기 시작했다. 그러나 형의 제안 중 일부는 상당히 엉뚱해 보여서, 그 설계가 실현 가능한지 의문이 들기 시작했다.

형은 설계를 위해 도시 위에 R × C 격자를 두었다. 도시의 각 칸에는 특정 높이의 건물이 들어간다. 동쪽 스카이라인은 R개 행 각각에서 가장 높은 건물로 주어지고, 북쪽 스카이라인은 C개 열 각각에서 가장 높은 건물로 주어진다.

형이 그린 두 스카이라인 쌍은, 격자 칸에 건물 높이를 배정하여 그 결과 스카이라인이 이 그림과 일치하게 만드는 방법이 존재할 때에만 실현 가능하다.

그림 A.1은 첫 번째 샘플의 입력에 주어진 북쪽과 동쪽 스카이라인을 정확히 갖는 가능한 도시를 보여준다.

그림 A.1: 샘플 1에 유효한 해가 있음을 보여주는 예시 도시.

• 첫 번째 줄은 격자의 행 수와 열 수를 나타내는 두 정수 1 ≤ R, C ≤ 100으로 이루어진다.
• 두 번째 줄은 동쪽 스카이라인을 나타내는 R개 정수 x1, . . . , xR로 이루어진다 (모든 i에 대해 0 ≤ xi ≤ 1000).
• 세 번째 줄은 북쪽 스카이라인을 나타내는 C개 정수 y1, . . . , yC로 이루어진다 (모든 j에 대해 0 ≤ yj ≤ 1000).

주어진 스카이라인을 만들어내는 도시 설계가 존재하면 possible, 그렇지 않으면 impossible을 한 줄에 출력한다.