시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 186 47 41 30.370%

문제

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

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

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

땅을 나눈 예시

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

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

입력

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

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

출력

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

예제 입력 1

3 4
3 2 3 3
3 4 3 2
3 3 3 4

예제 출력 1

HAPPY

예제 입력 2

3 4
3 2 3 3
2 3 3 3
2 3 3 4

예제 출력 2

HOMELESS

노트

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