In a undirected graph of $n$ vertices and $m$ edges, every vertex is numbered with a 6-digit string, i.e. 000000, 000001, 000002...... till the 6-digit string corresponding to $n-1$. We guarantee $n \leq 10^6$, so a 6-digit index is enough.

For each point except 000000, you need to find a path, travelling from 000000, without containing duplicate vertices, such that the concatenation of strings along this path is lexicographically smallest.

To compare two different strings lexicographically: if one string is a prefix of the other, the shorter string is smaller; otherwise, scan the strings from left to right to find the first different position of them, the string is smaller if the digit at the position is smaller.

You do not need to output the complete path, but only need to output the digit string (viewed as integer) modulo 998244353.

Input Format

Read from standard input.

The first line contains two integers $n$ and $m$.

The second line is a string of $12m$ digits, representing each edge. Each edge is denoted by $12$ digits, where the former and the latter $6$ digits respectively represent the index of two vertices this edge connects.

The input may contain self-loops or multiple edges between same pair of vertices.

Output Format

Write to the standard output.

Output $n-1$ lines. In each line output the answer of one vertex.

If a vertex cannot be reached from 000000, output -1 for this vertex.

Sample

Input

5 5
000000000003000001000003000001000002000002000000000002000003

Output

2000001
2
517560944
-1

Explanation

• From 000000 to 000001, the path is 000000000002000001。
• From 000000 to 000002, the path is 000000000002。
• From 000000 to 000003, the path is 000000000002000001000003, which is 517560944 modulo 998244353.
• From 000000 to 000004, no such path exists.

Subtasks

Subtask 1 (11 points)

$1 \leq n \leq 10^6, m=0$。

Subtask 2 (55 points)

$1 \leq n \leq 10, 0 \leq m \leq 20$。

Subtask 3 (34 points)

$1 \leq n \leq 10^6, 0 \leq m \leq 10^6$。