막대기 게임
시간 제한1초메모리 제한512 MB
장애물이 있는 격자에 주어진 길이의 가로 막대를 겹치지 않게 놓으며 최적으로 둘 때 승자를 구한다.
문제
영선이와 효빈이가 이번 컨테스트를 연다. 둘뿐이라 대회 스태프까지 겸하지만, 소규모 대회라서 실제 대회처럼 풍선을 달아 줄 일도 없고, 사고만 없으면 할 일이 거의 없다.
그래서 대회 동안 딴 짓으로 할 게임을 하나 준비했다. 이름은 막대기 게임이고 규칙은 다음과 같다.
- 크기의 격자판이 있다.
- 일부 칸에는 장애물이 있고, 그 칸에는 막대기를 놓을 수 없다.
- 주어진 길이마다 막대기가 무한히 있다.
- 두 사람이 번갈아 막대기를 하나 골라 원하는 위치에 놓는다.
- 더 놓을 곳이 없는 사람이 진다.
- 막대기는 겹쳐 놓을 수 없고, 돌릴 수도 없다.
막대기를 돌릴 수 없으므로 길이가 인 막대기는 한 행에서 가로로 연속한 빈 칸 개를 차지한다.

위 그림처럼 막대기를 놓을 수 있다.
두 사람은 생각할 시간이 넉넉해서 언제나 최적으로 둔다. 게임은 항상 영선이가 먼저 시작한다. 게임판이 주어졌을 때 이기는 사람의 아이디를 출력한다.
입력
첫째 줄에 과 이 주어진다. ()
다음 개의 줄에는 길이가 인 문자열이 주어져 게임판의 각 행을 나타낸다. 빈 칸은 ., 장애물은 @이다.
다음 줄에 막대기 종류의 수 가 주어진다. ()
다음 줄에 개의 정수 가 오름차순으로 주어진다. () 는 번째 종류의 막대기 길이다.
출력
영선이가 이기면 nein을, 효빈이가 이기면 hyo123bin을 출력한다.