Problem: There is a tree with N vertices, numbered 1, 2, \ldots, N. For each i (1 \leq i \leq N - 1), the i-th edge connects Vertex x_i and y_i.

Taro has decided to paint each vertex in white or black, so that any black vertex can be reached from any other black vertex by passing through only black vertices.

You are given a positive integer M. For each v (1 \leq v \leq N), answer the following question:

* Assuming that Vertex v has to be black, find the number of ways in which the vertices can be painted, modulo M.

Constraints

* All values in input are integers.
* 1 \leq N \leq 10^5
* 2 \leq M \leq 10^9
* 1 \leq x_i, y_i \leq N
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N M
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}


Output

Print N lines. The v-th (1 \leq v \leq N) line should contain the answer to the following question:

* Assuming that Vertex v has to be black, find the number of ways in which the vertices can be painted, modulo M.

Examples

Input

3 100
1 2
2 3


Output

3
4
3


Input

4 100
1 2
1 3
1 4


Output

8
5
5
5


Input

1 100


Output

1


Input

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


Output

0
0
1
1
1
0
1
0
1
1

Solution (in PYTHON):

Solution:
def main():
    n, mod = [int(x) for x in input().split()]

    coupl = [[] for _ in range(n)]
    for _ in range(n-1):
        u,v = [int(x)-1 for x in input().split()]
        coupl[u].append(v)
        coupl[v].append(u)

    subtree_memo = [-1]*n
    @bootstrap
    def subtrees_with_black_root(node, parent):
        if subtree_memo[node] == -1:
            ways = 1
            for nei in coupl[node]:
                if nei != parent:
                    ways = ways * (1 + \
                            (yield subtrees_with_black_root(nei, node)) \
                            ) % mod
            subtree_memo[node] = ways
        yield subtree_memo[node]

    ways_to_color_parent_black = [0]*n
    @bootstrap
    def tell_children(node, parent):
        # tell all children of node
        # the number of ways it is possible 
        # to color their parent (node) black
        A = []
        for nei in coupl[node]:
            if nei != parent:
                A.append(1 + (yield subtrees_with_black_root(nei, node)))
            else:
                A.append(1 +  ways_to_color_parent_black[node])

        prefix = [1]
        for a in A:
            prefix.append(prefix[-1] * a % mod)
        suffix = [1]
        for a in reversed(A):
            suffix.append(suffix[-1] * a % mod)

        for i, nei in enumerate(coupl[node]):
            if nei != parent:
                ways_to_color_parent_black[nei] = prefix[i] * suffix[~i-1] % mod
                yield tell_children(nei, node)
        yield
    tell_children(0, -1)

    ans = [-1]*n
    @bootstrap
    def solve(node, parent):
        ans[node] = (yield subtrees_with_black_root(node, parent)) \
                * (1 + ways_to_color_parent_black[node]) % mod
        
        for nei in coupl[node]:
            if nei != parent:    
                yield solve(nei, node)
        yield
    solve(0, -1)

    print ' '.join(str(x) for x in ans)


# Magic stackless recursion =D
# Should be fast enough for > 10^6 
# recursive calls in < 1 s in PyPy
from types import GeneratorType
def bootstrap(func, stack=[]):
    def wrapped_function(*args, **kwargs):
        if stack:
            return func(*args, **kwargs)
        else:
            call = func(*args, **kwargs)
            while True:
                if type(call) is GeneratorType:
                    stack.append(call)
                    call = next(call)
                else:
                    stack.pop()
                    if not stack:
                        break
                    call = stack[-1].send(call)
            return call

    return wrapped_function


######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using bytestrings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__== "__main__":
    main()