Дано дерево з \(N\) вершин. Назар вирішив пофарбувати вершини в білий або чорний колір таким чином, щоб будь-яка чорна вершина була досяжна з будь-якої іншої чорної лише через чорні вершини (тобто щоб усі чорні вершини формували зв'язну "чорну компоненту").

Для кожної вершини \(V\) дерева знайдіть кількість розфарбовок, при умові що вершина \(V\) буде розфарбована в чорний колір.

Відповідь виведіть за модулем \(M\)

Формат вхідних даних

В першому рядку два цілих числа \(N,M\) - (\(1 \le N \le 10^5\) , \(2 \le M \le 10^9\))
В наступних \(N-1\) рядках міститься по два числа (вершини які задають ребро дерева).

Формат вихідних даних

Виведіть \(N\) рядків, в рядку номер \(V\) виведіть кількість розфарбовок дерева за модулем \(M\) якщо вершина \(V\) буде пофарбована в чорний колір.

Приклад вхідних даних-1

3 100
1 2
2 3

Приклад вихідних даних-1

3
4
3

Пояснення до прикладу-1

Приклад вхідних даних-2

4 100
1 2
1 3
1 4

Приклад вихідних даних-2

8
5
5
5

Пояснення до прикладу-2

Приклад вхідних даних-3

1 100

Приклад вихідних даних-3

1

Приклад вхідних даних-4

10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7

Приклад вихідних даних-4

0
0
1
1
1
0
1
0
1
1