# Easy Path

Limits 1s, 128 MB

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

InputOutput
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