I. Er7am El Tree
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Gohary loved a big tree behind his house, but he did a lot of operations and one day the tree unexpectedly exploded — not the good kind. Every edge fell off and scattered. Gohary and his friends gathered the loose edges and the lonely nodes and laid the edges down in a row on the ground.

To keep things tidy, each friend packed a consecutive run of edges into a box; when they stacked boxes for transport they either nested a box inside another for safe packing or put boxes side-by-side so nothing slipped. (They never made a messy partial overlap — that would have been chaotic.)

Now, Gohary wants to play with the pieces.

You are given the list of node values and the array of discarded edges (in the order they were placed). For a query, friends take the edges from position $$$l$$$ to $$$r$$$ in the array and reconnect them. After connecting edges $$$l$$$ through $$$r$$$, if two nodes $$$u$$$ and $$$v$$$ are connected, consider the unique simple path between $$$u$$$ and $$$v$$$. Along that path you can look at the sequence of node values. The answer to the query is the length of the longest contiguous subsegment of that path in which all node values are equal. If $$$u$$$ and $$$v$$$ are not connected after adding edges $$$l \ldots r$$$, the answer is $$$-1$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 2 \times 10^5$$$, $$$1 \leq q \leq 2 \times 10^5$$$) — the number of nodes and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the values of the nodes.

Each of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$) — the edges in the order they were placed on the ground. The edges form a valid tree (no duplicates, no self-loops).

Each of the next $$$q$$$ lines contains four integers $$$l$$$, $$$r$$$, $$$u$$$, and $$$v$$$ ($$$1 \leq l \leq r \leq n-1$$$, $$$1 \leq u, v \leq n$$$, $$$u \neq v$$$) — a query asking about the longest equal-value subsegment on the path from $$$u$$$ to $$$v$$$ using edges $$$l$$$ through $$$r$$$.

Output

For each query, output a single integer:

  • If $$$u$$$ and $$$v$$$ are connected using edges $$$l \ldots r$$$, output the length of the longest contiguous subsegment of equal values on the path from $$$u$$$ to $$$v$$$.
  • If $$$u$$$ and $$$v$$$ are not connected, output $$$-1$$$.
Examples
Input
6 5
2 2 2 2 1 1
1 3
1 5
1 2
4 6
2 4
4 4 1 3
1 3 2 5
2 5 5 2
1 4 2 4
5 5 4 5
Output
-1
2
2
-1
-1
Input
10 5
6 5 1 13 9 18 13 8 18 16
1 2
4 9
2 3
4 6
6 8
6 7
8 10
3 5
2 4
7 7 10 5
3 9 10 8
9 9 10 8
8 8 4 2
4 9 1 5
Output
-1
1
-1
-1
-1