There is a treasure hunting game played on a tree with $n$ nodes, where the treasure is buried at some unknown node $x$. Each time a node $u$ is excavated, the player receives feedback in the form of a value $d$, which represents the number of edges on the simple path between node $u$ and node $x$. This game is played $q$ times, and the location of the treasure may be different for each game.

As an excellent Oler, you are extremely confident. You want to find the treasure with the minimum number of excavations. You have chosen two different nodes $a$ and $b$ to excavate and obtained the feedback values $d_a$ and $d_b$, respectively. For the third excavation, you want to dig directly at a possible location $x$. Since the tree is too large to find the exact location of $x$ by eye, you turn to your computer and start writing a program to help you solve this problem.

Input

The first line contains two positive integers $n$ and $q$, representing the number of nodes in the tree and the number of games, respectively.

The next $n-1$ lines each contain two positive integers $u, v$, describing an edge in the tree. It is guaranteed that the input forms a tree.

The next $q$ lines each contain four positive integers $a, d_a, b, d_b$, representing the feedback obtained from two excavations in one game.

Output

Output $q$ lines. Each line contains an integer representing a treasure location that satisfies the conditions, or output $-1$ if there is no solution. If there are multiple possible treasure locations, output any one of them.

Examples

Input 1

5 3
1 2
2 3
3 4
3 5
2 1 4 1
2 2 4 2
1 1 2 1

Output 1

3
5
-1

Constraints

• For 20% of the data, $3 \le n \le 3000$, $1 \le q \le 3000$;
• For 40% of the data, $3 \le n \le 10^5$, $1 \le q \le 10^5$;
• For another 20% of the data, all queries have the same $a$ and the same $b$;
• For 100% of the data, $3 \le n \le 10^6$, $1 \le q \le 10^6$, $1 \le u < v \le n$, $1 \le a, b, d_a, d_b \le n$.