Юная И — девушка с богатым воображением.

Однажды ночью, глядя на звездное небо, Юная И начала узнавать созвездия, используя свои знания по астрономии. Однако в этот раз она захотела добавить немного собственного творчества к тому, что было известно ранее, чтобы создать свой собственный узор.

На небе всего $n$ звезд. Изучив множество древних и современных книг, Юная И получила $m$ фрагментов информации. В $i$-м фрагменте говорится, что между звездой $a_i$ и звездой $b_i$ должна быть проведена линия. Для каждого фрагмента Юная И также определила вес $c_i$ этой линии, основываясь на её возрасте, источнике и другой информации.

Юная И хочет выбрать некоторые из этих $m$ фрагментов информации и соединить звезды согласно им, чтобы получить свой узор.

Юная И хочет, чтобы в полученном узоре не было кратных ребер, то есть между любыми двумя звездами должно быть не более одного ребра. Кроме того, узор должен быть связным.

Помимо этого, поскольку сейчас 2017 год, Юная И хочет, чтобы сумма весов выбранных ребер по модулю $p = 17$ была равна определенному числу. Юная И хочет узнать для каждого $k$ из диапазона $0 \le k < p$: сколько существует способов выбрать ребра так, чтобы узор был связным, не имел кратных ребер, а сумма весов ребер по модулю $p$ была равна $k$?

Так как ответ может быть очень большим, вам нужно сообщить Юной И ответ по модулю $998244353$.

Входные данные

Программа считывает данные из стандартного ввода (stdin).

В первой строке содержатся два целых числа $n$ и $m$, смысл которых описан выше.

Далее следуют $m$ строк, в каждой из которых записаны три целых числа $a_i, b_i, c_i$, обозначающие наличие ребра между $a_i$ и $b_i$ с весом $c_i$.

Выходные данные

Программа выводит данные в стандартный вывод (stdout).

Выведите $p$ строк. В $i$-й строке выведите количество способов, при которых сумма весов ребер по модулю $p$ равна $i - 1$, взятое по модулю $998244353$.

Примеры

Пример 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

Выходные данные

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

Подзадачи

Масштаб данных и характеристики каждого теста приведены в таблице ниже.

Для 100% данных гарантируется, что $1 \le n \le 17, 1 \le m \le 10^5, 0 \le c_i < p = 17$.