Distinct Values on Tree Paths

You are given a tree with \(n\) nodes. Each node \(i\) has an integer value \(val_i\). The tree is connected by \(n-1\) edges.

There are \(m\) queries. Each query consists of two integers \(u'\) and \(v\). To decrypt the query, compute \(u = u' \oplus lastans\), where \(lastans\) is the answer to the previous query (and \(0\) for the first query). Then, you must count the number of distinct integers on the unique simple path between node \(u\) and node \(v\).

Note: \(\oplus\) denotes the bitwise XOR operation.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of nodes and the number of queries.

The second line contains \(n\) integers \(val_1, val_2, \ldots, val_n\), where \(val_i\) is the integer at node \(i\).

Each of the next \(n - 1\) lines contains two integers \(u\) and \(v\), representing an edge between nodes \(u\) and \(v\>.

The following \(m\) lines each contain two integers \(u'\) and \(v\), representing a query.

outputFormat

For each query, output a single line containing one integer — the number of distinct values on the path between the decrypted node \(u\) and node \(v\), where \(u = u' \oplus lastans\).

sample

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

3
2
2