Problem: In Homer's country, there are n cities numbered 1 to n and they form a tree. That is, there are (n-1) undirected roads between these n cities and every two cities can reach each other through these roads. 

Homer's country is an industrial country, and each of the n cities in it contains some mineral resource. The mineral resource of city i is labeled a_i. 

Homer is given the plans of the country in the following q years. The plan of the i-th year is described by four parameters u_i, v_i, l_i and r_i, and he is asked to find any mineral resource c_i such that the following two conditions hold: 

  * mineral resource c_i appears an odd number of times between city u_i and city v_i; and 
  * l_i ≤ c_i ≤ r_i. 



As the best friend of Homer, he asks you for help. For every plan, find any such mineral resource c_i, or tell him that there doesn't exist one.

Input

The first line contains two integers n (1 ≤ n ≤ 3 ⋅ 10^5) and q (1 ≤ q ≤ 3 ⋅ 10^5), indicating the number of cities and the number of plans.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n).

Then the i-th line of the following (n-1) lines contains two integers x_i and y_i (1 ≤ x_i, y_i ≤ n) with x_i ≠ y_i, indicating that there is a bidirectional road between city x_i and city y_i. It is guaranteed that the given roads form a tree.

Then the i-th line of the following q lines contains four integers u_i, v_i, l_i, r_i (1 ≤ u_i ≤ n, 1 ≤ v_i ≤ n, 1 ≤ l_i ≤ r_i ≤ n), indicating the plan of the i-th year.

Output

Print q lines, the i-th of which contains an integer c_i such that 

  * c_i = {-1} if there is no such mineral resource that meets the required condition; or 
  * c_i is the label of the chosen mineral resource of the i-th year. The chosen mineral resource c_i should meet those conditions in the i-th year described above in the problem statement. If there are multiple choices of c_i, you can print any of them. 

Example

Input


6 8
3 2 1 3 1 3
1 2
1 3
2 4
2 5
4 6
3 5 1 1
3 5 1 3
3 5 1 3
1 1 2 2
1 1 3 3
1 4 1 5
1 6 1 3
1 6 1 3


Output


-1
2
3
-1
3
2
2
3

Note

In the first three queries, there are four cities between city 3 and city 5, which are city 1, city 2, city 3 and city 5. The mineral resources appear in them are mineral resources 1 (appears in city 3 and city 5), 2 (appears in city 2) and 3 (appears in city 1). It is noted that 

  * The first query is only to check whether mineral source 1 appears an odd number of times between city 3 and city 5. The answer is no, because mineral source 1 appears twice (an even number of times) between city 3 and city 5. 
  * The second and the third queries are the same but they can choose different mineral resources. Both mineral resources 2 and 3 are available. 

Solution (in CPP):

Solution:
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cassert>
#include <map>
#include <numeric>
#include <cstring>
#include <set>
#include <ctime>
#include <queue>
#include <cmath>
#include <iomanip>
#include <iterator>

using namespace std;

clock_t timeStart, timeFinish;

void timeBegin() {
    timeStart = clock();
}

void timeEnd() {
    timeFinish = clock();
}

void timeDuration() {
    timeEnd();
    double time_taken = double(timeFinish - timeStart) / double(CLOCKS_PER_SEC);
    cout << "Time taken by program is : " << fixed << time_taken << setprecision(5);
    cout << " sec " << endl;
}

class InputReader {
public:
    InputReader() {
        input_file = stdin;
        cursor = 0;
        fread(buffer, SIZE, 1, input_file);
    }
    InputReader(const char *file_name) {
        input_file = fopen(file_name, "r");
        cursor = 0;
        fread(buffer, SIZE, 1, input_file);
    }
    inline InputReader &operator >>(int &n) {
        while((buffer[cursor] < '0' || buffer[cursor] > '9') && buffer[cursor] != '-') {
            advance();
        }
        int sign = 1;
        if (buffer[cursor] == '-') {
            sign = -1;
            advance();
        }
        n = 0;
        while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
            n = n * 10 + buffer[cursor] - '0';
            advance();
        }
        n *= sign;
        return *this;
    }
private:
    FILE *input_file;
    static const int SIZE = 1 << 17;
    int cursor;
    char buffer[SIZE];
    inline void advance() {
        ++ cursor;
        if(cursor == SIZE) {
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
    }
};

const int MAXN = 300000;
const int MAXLOG = 20;

int v[1 + MAXN];
unsigned long long code[1 + MAXN];

unsigned long long genCode() {
    return ((unsigned long long) rand() << 32) + rand();
}

void generateCodes(int n) {
    for (int i = 1; i <= n; i++) {
        code[i] = genCode();
    }
}

int n;
vector<int> g[1 + MAXN];

int dad[1 + MAXN][1 + MAXLOG];
int depth[1 + MAXN], root[1 + MAXN];
unsigned long long hashSum[1 + MAXLOG * MAXN];
int leftSon[1 + MAXLOG * MAXN], rightSon[1 + MAXLOG * MAXN];
int nodeCount = 0;

int createNode(int node) {
    nodeCount++;
    leftSon[nodeCount] = leftSon[node];
    rightSon[nodeCount] = rightSon[node];
    return nodeCount;
}

int update(int oldNode, int left, int right, int where) {
    int newNode = createNode(oldNode);
    if (left == right) {
        hashSum[newNode] = hashSum[oldNode] ^ code[left];
        return newNode;
    }
    int middle = (left + right) / 2;
    if (where <= middle) {
        leftSon[newNode] = update(leftSon[oldNode], left, middle, where);
    } else {
        rightSon[newNode] = update(rightSon[oldNode], middle + 1, right, where);
    }
    hashSum[newNode] = hashSum[leftSon[newNode]] ^ hashSum[rightSon[newNode]];
    return newNode;
}

void DFS(int node, int father) {
    depth[node] = depth[father] + 1;
    dad[node][0] = father;
    for (int i = 1; (1 << i) < depth[node]; i++) {
        dad[node][i] = dad[dad[node][i - 1]][i - 1];
    }
    root[node] = update(root[father], 1, n, v[node]);
    for (auto son : g[node]) {
        if (son != father) {
            DFS(son, node);
        }
    }
}

int raise(int node, int delta) {
    for (int i = 0; i <= MAXLOG; i++) {
        if (delta & (1 << i)) {
            node = dad[node][i];
        }
    }
    return node;
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) {
        swap(a, b);
    }
    a = raise(a, depth[a] - depth[b]);
    for (int i = MAXLOG; i >= 0; i--) {
        if (dad[a][i] != dad[b][i]) {
            a = dad[a][i];
            b = dad[b][i];
        }
    }
    if (a != b) {
        a = dad[a][0];
    }
    return a;
}

unsigned long long getHash(int node1, int node2, int left, int right, int x) {
    return hashSum[node1] ^ hashSum[node2] ^ ((left <= x && x <= right) ? code[x] : 0);
}

int query(int node1, int node2, int left, int right, int from, int to, int x) {
    if (from <= left && right <= to) {
        unsigned long long h = getHash(node1, node2, left, right, x);
        if (h == 0) {
            return -1;
        } else {
            while (left != right) {
                int middle = (left + right) / 2;
                h = getHash(leftSon[node1], leftSon[node2], left, middle, x);
                if (h != 0) {
                    node1 = leftSon[node1];
                    node2 = leftSon[node2];
                    right = middle;
                } else {
                    node1 = rightSon[node1];
                    node2 = rightSon[node2];
                    left = middle + 1;
                }
            }
            return left;
        }
    }
    int middle = (left + right) / 2, answer = -1;
    if (from <= middle) {
        answer = query(leftSon[node1], leftSon[node2], left, middle, from, to, x);
    }
    if (middle + 1 <= to && answer == -1) {
        answer = query(rightSon[node1], rightSon[node2], middle + 1, right, from, to, x);
    }
    return answer;
}

int main() {
    timeBegin();
    //InputReader cin("input.txt");
    //ofstream cout("greutati.out");
    srand(time(0));
    int q;
    cin >> n >> q;
    generateCodes(n);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    DFS(1, 0);
    for (int i = 1; i <= q; i++) {
        int a, b, l, r;
        cin >> a >> b >> l >> r;
        int c = lca(a, b);
        cout << query(root[a], root[b], 1, n, l, r, v[c]) << "\n";
    }
    //timeDuration();
    return 0;
}