Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
Reset Sequence
 Time Limit: 1000MS Memory Limit: 131072K Total Submissions: 948 Accepted: 357 Special Judge

Description

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.

Input

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 ≤ δijn − 1) indicates that when the chip receives command j in state i, it transits to state δij .

Output

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 (“*”).

Sample Input

```3 4
2 1 1 2
1 0 0 0
0 0 0 1```

Sample Output

`101`

Source

[Submit]   [Go Back]   [Status]   [Discuss]