Easy Path

After performing so badly in the World Cup, Mushfiq left cricket and started problem solving. You told him to solve the following problem.

You are given a rooted tree with $n$ vertices (each edge of the tree has a cost) and a magic integer $x$. The vertices are numbered from $1$ to $n$, the root is the vertex number $1$. You are also given an operation —

• You can change the cost of an edge by multiplying it by any integer $k$. For example, cost of an edge is $p$, you can change it to $q$ such that $q = p * k$, where $k≥1$.

You have to find two integers $node_i$ and $k$ such that length of the path from root to $node_i$ is maximum, GCD of the costs of the path is a multiple of $x$ by applying the operation at most once and $k$ is minimum. If there are multiple nodes with maximum path length and minimum $k$ print the node with minimum label.

Input

The first line contains two space separated integers $n$ and $x$ — the number of vertices and the magic integer.

Each of the next $n−1$ lines describes an edge of the tree. Edge $i$ is denoted by three integers $u_i$, $v_i$ and $cost_i$— the labels of vertices it connects and cost of the edge.

$2≤n≤2*10^5$

$1≤x, cost_i≤10^{18}$

$1≤u_i, v_i≤n, u_i≠v_i$

Output

Print two integers $node_i$ and $k$ — if length of the path from root to $node_i$ is maximum, GCD of the path is a multiple of $x$ and $k$ is minimum.

Sample

Input	Output
9 6 1 2 6 1 3 6 2 4 6 2 5 6 3 6 12 3 7 18 5 8 8 5 9 7	8 3
Test Case 1 Tree