막대기 게임

장애물이 있는 격자에 주어진 길이의 가로 막대를 겹치지 않게 놓으며 최적으로 둘 때 승자를 구한다.

보통6게임 이론구현아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

영선이와 효빈이가 이번 컨테스트를 연다. 둘뿐이라 대회 스태프까지 겸하지만, 소규모 대회라서 실제 대회처럼 풍선을 달아 줄 일도 없고, 사고만 없으면 할 일이 거의 없다.

그래서 대회 동안 딴 짓으로 할 게임을 하나 준비했다. 이름은 막대기 게임이고 규칙은 다음과 같다.

  1. n×mn \times m 크기의 격자판이 있다.
  2. 일부 칸에는 장애물이 있고, 그 칸에는 막대기를 놓을 수 없다.
  3. 주어진 길이마다 1×p1 \times p 막대기가 무한히 있다.
  4. 두 사람이 번갈아 막대기를 하나 골라 원하는 위치에 놓는다.
  5. 더 놓을 곳이 없는 사람이 진다.
  6. 막대기는 겹쳐 놓을 수 없고, 돌릴 수도 없다.

막대기를 돌릴 수 없으므로 길이가 pp인 막대기는 한 행에서 가로로 연속한 빈 칸 pp개를 차지한다.

위 그림처럼 막대기를 놓을 수 있다.

두 사람은 생각할 시간이 넉넉해서 언제나 최적으로 둔다. 게임은 항상 영선이가 먼저 시작한다. 게임판이 주어졌을 때 이기는 사람의 아이디를 출력한다.

입력

첫째 줄에 nnmm이 주어진다. (1n,m10001 \le n, m \le 1000)

다음 nn개의 줄에는 길이가 mm인 문자열이 주어져 게임판의 각 행을 나타낸다. 빈 칸은 ., 장애물은 @이다.

다음 줄에 막대기 종류의 수 kk가 주어진다. (1k10001 \le k \le 1000)

다음 줄에 kk개의 정수 p1,p2,,pkp_1, p_2, \dots, p_k가 오름차순으로 주어진다. (1pi10001 \le p_i \le 1000) pip_iii번째 종류의 막대기 길이다.

출력

영선이가 이기면 nein을, 효빈이가 이기면 hyo123bin을 출력한다.