동아리방 확장

모 프로그래밍 대회에서 큰 상금을 받은 상수는 좁은 동아리방에서 고통받는 SNUPS 회원들을 위해 새 동아리 공간을 지으려고 H행 W열의 격자가 그려진 직사각형 모양의 땅을 샀다.

상수는 땅을 여러 개의 방으로 나누기로 했다. 방은 크기별로 용도가 다른데, 개인 연습을 위한 한 칸짜리 방, 팀 연습을 위한 두 칸짜리 방, 스터디 및 세미나를 위한 세 칸짜리 방이 있다. 하나의 방에 속한 칸들은 상하좌우로 연결되어 있어야 하며, 하나의 칸이 여러 개의 방에 걸쳐 있을 수 없다.

상수는 어떤 방에도 속하지 않은 격자칸이 없도록 땅을 완전히 나눈 뒤, 모든 방의 둘레에 두꺼운 방음벽을 세웠다. 그리고 각각의 격자칸에 대해 상하좌우 중 몇 개의 방향이 벽으로 막혀 있는지를 기억해 두었다.

어느 날, 항상 열심히 연습하는 SNUPS 회원들의 열정에 못 이겨 동아리 공간의 모든 벽이 녹아 버리고 말았다. 상수는 기억에 의존해서 벽을 다시 세우려고 했지만, 너무 오래 전 기억이라 자신이 기억하고 있는 정보로 다시 벽을 복원할 수 있을지 의심이 들었다.

어차피 최초의 방의 배치를 완벽히 기억하고 있지 않기 때문에, 세 가지 크기의 방으로 땅을 완전히 나눌 수 있기만 하면 상수는 자신의 기억이 맞다고 생각할 것이다. 상수의 의문을 해결해 주자.

첫 줄에 땅에 그려진 격자의 행 수와 열 수를 의미하는 정수 H, W(1 ≤ H, W ≤ 100)가 주어진다.

두 번째 줄부터 H줄에 걸쳐 각 줄에 0 이상 4 이하의 정수가 W개씩 주어진다. i번째 줄의 j번째 정수는 상수가 기억하고 있는 i행 j열 칸의 벽으로 막혀 있는 방향의 개수를 의미한다.

첫 줄에 상수가 기억하고 있는 정보로 다시 벽을 복원할 수 있다면 HAPPY, 불가능하다면 HOMELESS를 출력한다.

두 번째 예시에서 방을 복원하기 위해서는 네 칸짜리 방이 필요하다.