A reset sequence is a series of commands which, when issued, brings a chip to the ready state. When a chip is powered on or encounters an error, it may be in an arbitrary state. The reset sequence ensures that the chip is appropriately (re-)initialized for subsequent tasks.

The state control of a chip is typically modeled after a finite automaton. (Please refer to Problem 3599 Pumping Lemma for an informal description of finite automata.) When it receives a command, the chip transits from its current state to another state as its control logic dictates.

Given the description of the control logic of a chip, compute the shortest reset sequence.

The input consists of a single test case. The first line contains two integers n and m (2 ≤ n ≤ 8, 1 ≤ m ≤ 16), which are the numbers of states and different commands. The states are numbered 0 through n − 1. State 0 is the only ready state. The commands are denoted by hexadecimal digits 0 through f.

Immediately following the first line comes an n × m matrix Δ = {δ_ij}_n×m with zero-based indices. Each element δ_ij (0 ≤ δ_ij ≤ n − 1) indicates that when the chip receives command j in state i, it transits to state δ_ij .

Output the shortest reset sequence using its representation by hexadecimal digits. If there are multiple such sequences, output any one. If there are no such sequences, output an asterisk (“*”).