Everything Is New
Time limit1sMemory limit1024 MB
Given a shuffled Ukdimensional sliding puzzle on an a x b x c x d x e x f grid, decide whether the pieces can be returned to the solved order.
- Level
Hard8 of 10
- Topics
- Math, Graph, Implementation
- Solved
- No attempts yet
Problem
Uk-jae says every math problem is 2ez. Ask him about an unsolved problem such as the Riemann hypothesis, and he will still answer '2ez'. When someone asks for the actual solution, he dodges by saying it is too easy to be worth answering. The trick is obvious, since it clearly shows he does not know the solution, but he cannot prove that, so it works as his usual irritating bait.
Uk-jae has one weakness: problems with a false premise. If he answers '2ez' to one of those, a bored person like Jeultalleuler will reply with something like 'That's wrong, how did you prove it lol' and mock him.
Jeultalleuler targeted Uk-jae by making a 'Ukdimensional sliding puzzle' and sending it to him by hand. This puzzle extends the familiar two-dimensional sliding puzzle to six dimensions. Specifically, a Ukdimensional sliding puzzle of size has cells in six dimensions. Each cell is located by six coordinates with , , , , , and . In other words, every coordinate is a positive integer no greater than its maximum. In the initial state, every cell except the empty cell holds one piece.
In this puzzle, you can move a piece next to the empty cell into the empty cell. Let the empty cell be . A piece at can move to if exactly one coordinate of differs from the matching coordinate of by 1, and all other coordinates are equal. Equivalently, exactly one of is 1 and the rest are 0. The piece moves from to , so the new empty cell is at . Given a shuffled state, the goal is to restore the pieces to their initial order.
Uk-jae does not plan to solve the puzzle. He will just call it 2ez. But this puzzle may be impossible to return to the initial state. Jeultalleuler will call Uk-jae and ask him to say '2ez' if the puzzle can be solved, and 'eokkkkkk' if it cannot. Help Uk-jae pick the right answer so he can stir up trouble without getting mocked.
Input
The first line contains the sizes in that order.
The second line contains numbers that give the piece in each cell. Each number is between and , inclusive, and all numbers are distinct. denotes the empty cell, and each number from upward denotes a piece. The pieces are given in lexicographic order of their coordinates. That is, the coordinates are listed as
The solved state is written as in this notation.
Output
Print '2ez' if the puzzle can be solved, and 'eokkkkkk' otherwise (without the quotes).
Constraints
- At least one of is 2 or greater.