Little Y is a girl with a vivid imagination.

One night, while gazing at the starry sky, Little Y began to identify constellations using the astronomical knowledge she had learned. This time, however, she hoped to add her own creative touch to the existing patterns to create designs of her own.

There are $n$ stars in the sky. By consulting various ancient and modern texts, Little Y obtained $m$ pieces of information. The $i$-th piece of information states that there should be a connection between star $a_i$ and star $b_i$. For each piece of information, Little Y assigned a weight $c_i$ to the connection based on its age, origin, and other factors.

Little Y wants to select some of these $m$ pieces of information to connect the stars and form her own pattern.

Little Y hopes that the resulting pattern contains no multiple edges, meaning there is at most one edge between any two stars. Furthermore, the pattern must be connected.

Additionally, since this year is 2017, Little Y wants the sum of the weights of the selected edges, modulo $p = 17$, to be a specific value. Therefore, for each $k$ where $0 \le k < p$, Little Y wants to know the number of ways to form a connected pattern with no multiple edges such that the sum of the edge weights modulo $p$ is $k$.

Since the answer may be very large, you only need to provide the answer modulo $998244353$.

Input

The input is read from standard input.

The first line contains two integers $n$ and $m$, as described above.

The next $m$ lines each contain three integers $a_i, b_i, c_i$, representing an edge connecting $a_i$ and $b_i$ with weight $c_i$.

Output

The output is sent to standard output.

The output consists of $p$ lines, each containing one integer. The $i$-th line represents the number of ways such that the sum of the edge weights modulo $p$ is $i - 1$, modulo $998244353$.

Examples

Input 1

4 8
1 2 0
1 2 1
2 3 0
2 3 1
3 4 0
3 4 1
1 4 0
1 4 2

Output 1

5
12
13
11
6
1
0
0
0
0
0
0
0
0
0
0
0

Subtasks

The data scale and characteristics for each test case are shown in the table below.

For 100% of the data, it is guaranteed that $1 \le n \le 17, 1 \le m \le 10^5, 0 \le c_i < p = 17$.