오늘은 영선이의 생일이다. 친구들이 직사각형 모양의 생일 케이크를 하나 준비했다.
케이크의 윗면은 n×m개의 칸으로 나누어져 있다. 왼쪽 위 칸의 좌표는 (1,1), 오른쪽 위 칸의 좌표는 (n,1), 오른쪽 아래 칸의 좌표는 (n,m)이다. 좌표 (x,y)에서 x는 왼쪽에서 센 열 번호, y는 위에서 센 행 번호다.
일곱 개의 칸에는 장식이 하나씩 놓여 있다.
- (x1,y1)에는 초가 놓여 있다.
- (x2,y2), (x3,y3), (x4,y4)에는 체리가 놓여 있다.
- (x5,y5), (x6,y6), (x7,y7)에는 딸기가 놓여 있다.
영선이는 케이크를 네 조각으로 나누려고 한다. 한 조각은 영선이가 먹고, 나머지 세 조각은 친구들이 먹는다.
네 조각은 모두 칸으로 이루어져야 하고, 모든 칸은 정확히 한 조각에 속해야 한다. 또 네 조각은 모두 연결되어 있어야 한다. 변을 맞대고 있는 두 칸은 서로 이웃하고, 한 조각에 속한 어떤 두 칸이든 그 조각 안의 이웃한 칸만 밟아서 오갈 수 있으면 그 조각은 연결되어 있다.
영선이는 초가 놓인 조각을 먹어야 하고, 나머지 세 조각에는 딸기 하나와 체리 하나가 들어 있어야 한다.
n과 m, 초와 체리와 딸기의 위치가 주어졌을 때, 조건에 맞게 케이크를 나눌 수 있는지 없는지 구하는 프로그램을 작성하시오.