모든 것이 새롭다

섞인 6차원 슬라이딩 퍼즐 상태가 주어질 때, 순열의 홀짝성과 차원 조건으로 풀 수 있는지 판정하는 문제이다.

어려움8조합론수학구현아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

욱제에게 모든 수학 문제는 2ez다. 리만가설 같이 현재까지 전 인류가 못 푼 난제를 물어봐도 욱제는 '2ez'라고 답할 것이다. 이때 욱제의 특징은 구체적인 풀이를 물어보면 졸렬하게 '너무 쉬워서 대답할 가치가 없다'고 답을 회피한다는 것이다. 이 스킬은 그가 풀이를 모른다는 게 사실상 너무 뻔하지만, 그렇다고 그걸 또 완벽히 입증할 수는 없다는 것 때문에 특유의 킹받는 욱제식 어그로가 된다. 하지만 이런 욱제에게도 약점은 있다. 바로 아예 틀린 전제로 사람을 낚는 낚시 문제이다. 이런 문제에 '2ez'를 시전하는 순간, 욱제는 그를 노리는 즈탈즐러같이 똑같이 할 일 없는 사람에게 '저거 틀렸는데 어떻게 증명함 엌ㅋㅋㅋㅋㅋ' 같은 핀잔을 듣는 것이다. 

즈탈즐러는 욱제를 노리고 '욱차원 슬라이딩 퍼즐'이라는 걸 만들어 욱제에게 인편으로 보냈다. 이 퍼즐은 가끔씩 볼 수 있는 2차원 슬라이딩 퍼즐을 6차원으로 확장한 것이다. 구체적으로, a×b×c×d×e×fa \times b \times c \times d \times e \times f 짜리 욱차원 슬라이딩 퍼즐은 6차원에 있는 총 N=abcdefN = a b c d e f개 칸으로 구성되어 있다. 이때 각 칸의 위치는 6개 좌표 (i,j,k,l,m,n)(i, j, k, l, m, n) 으로 나타낼 수 있고, 이때 1ia1 \leq i \leq a, 1jb1 \leq j \leq b, 1k c1 \leq k \leq c1ld1 \leq l \leq d, 1m e1 \leq m \leq e1n f1 \leq n \leq f 의 조건을 만족한다. 즉 좌표계는 1 이상, 최대 크기 이하의 자연수로 표시된다. 초기 상태에서는 빈 칸 (a,b,c,d,e,f)(a, b, c, d, e, f)를 뺀 모든 칸에 각각 해당하는 조각이 하나씩 위치해 있다.

이 퍼즐에서는 빈 칸과 인접한 위치에 있는 조각을 빈 칸으로 이동할 수 있다. 즉, 빈 칸이 있는 좌표 p_0=(i_0,j_0,k_0,l_0,m_0,n_0)p\_0 = (i\_0, j\_0, k\_0, l\_0, m\_0, n\_0)에 대해, p_0p\_0과 딱 하나의 좌표값만 정확히 1 차이나고 나머지 좌표값들은 다 똑같은 좌표 p_1=(i_1,j_1,k_1,l_1,m_1,n_1)p\_1 = (i\_1, j\_1, k\_1, l\_1, m\_1, n\_1) 위에 있는 조각을 p_0p\_0으로 옮길 수 있다 (다르게 쓰면 i_0i_1,j_0j_1|i\_0 - i\_1|, |j\_0 - j\_1| \cdots 중 딱 하나만 1이고 나머지는 다 0이라는 것이다). 이때 p_1p\_1에 있던 조각이 p_0p\_0으로 이동했으므로 새로운 빈 칸은 p_1p\_1에 위치하게 된다. 퍼즐의 목표는 섞여진 조각들의 상태가 주어질 때, 조각들을 초기 상태의 순서로 맞추는 것이다.

퍼즐을 받은 욱제는 역시나 퍼즐을 풀 생각은 안 하고 2ez를 시전하기로 했다. 그러나 이 퍼즐은 아예 초기 상태로 돌릴 수 없을 수도 있다. 즉, 즈탈즐러가 보낸 퍼즐을 규칙에 맞게 푸는 게 아예 불가능할 수도 있는 것이다. 욱제는 즈탈즐러에게 전화해 인편으로 받은 퍼즐을 푸는 게 가능하면 '2ez', 불가능하면 'eokkkkkk'를 시전할 예정이다. 욱제가 핀잔을 듣지 않고 어그로를 끌 수 있도록 욱제의 전화통화를 도와주자.\

입력

첫째 줄에 퍼즐의 크기를 나타내는 수 a,b,c,d,e,fa, b, c, d, e, f가 순서대로 주어진다.

둘째 줄에 퍼즐의 각 칸에 위치한 조각을 나타내는 N=abcdefN = abcdef개의 수가 주어진다. 각 수는 00 이상 N1N-1 이하이고, 서로 다 다르다. 00은 빈 칸을, 11 이상의 수는 각각의 조각을 나타낸다. 조각들은 좌표값의 사전순으로 주어진다. 즉, 조각들이 좌표 
\begin{align*}
(1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 2), & \cdots, (1, 1, 1, 1, 1, f), \\
(1, 1, 1, 1, 2, 1), (1, 1, 1, 1, 2, 2), & \cdots, (1, 1, 1, 1, 2, f), \\
\cdots & \cdots \cdots \\
(1, 1, 1, 1, e, 1), (1, 1, 1, 1, e, 2), & \cdots, (1, 1, 1, 1, e, f), \\
(1, 1, 1, 2, 1, 1), (1, 1, 1, 2, 1, 2), & \cdots, (1, 1, 1, 2, 1, f), \\
\cdots & \cdots \cdots \\
& \vdots \\
(a, b, c, d, e, 1), (a, b, c, d, e, 2), & \cdots, (a, b, c, d, e, f)
\end{align*}
의 순으로 주어진다. 퍼즐을 맞춘 상태는 이 표기법으로 1,2,,N1,01, 2, \cdots, N-1, 0 으로 나타내어 진다.

출력

퍼즐을 맞추는 게 가능하면 '2ez'를, 아니면 'eokkkkkk'를 출력한다 (따옴표 제외).

제한

  • a,b,c,d,e,f1a, b, c, d, e, f \geq 1
  • N=abcdef106N = abcdef \leq 10^6
  • a,b,c,d,e,fa, b, c, d, e, f 중 적어도 하나는 2 이상이다.