背景

十周年記念を記念して、小Tと小Sはメイン会場に大型のインタラクティブアート装置「幻光留影」を設置しました。

この装置は、多くの浮遊する映像ノードで構成されており、光束によって木のような形に接続されています。各ノードには異なる色の光影フィルターが設定されています。制御コンソールの前に立つと、自由に操作できることがわかります。コンソールのパラメータを調整するたびに、システムは特定の番号区間内の光束のみを一時的に有効化します。これにより、元々完全だった映像ネットワークは、いくつかの独立した連結成分に分裂します。

興味深いことに、同じ連結成分内にある同じ色のフィルターを持つノード間では光学干渉が発生します。ある色のフィルターがその連結成分内で偶数回出現する場合、それらの光は互いに打ち消し合って見えなくなります。一方、出現回数が奇数回である場合、それらは集まってはっきりと見える色となります。

光影の破壊と再構築は非常に魅力的です。あなたは、その中に隠された構造の変化に強い関心を持ちました。このような局所的な有効化が行われるたびに、分裂したすべての連結成分において、それぞれに含まれる「可視フィルター」（すなわち、出現回数が奇数であるフィルターの色）の種類数の総和はいくつになるでしょうか。

問題

「幻光留影」装置は、$n$ 個のノードを持つ木として抽象化できます。各ノードは映像ノードを表し、ノード $i$ ($1 \le i \le n$) のフィルターの色は $c_i$ です。ノードを接続する光束は全部で $n-1$ 本あり、それぞれ $1$ から $n-1$ まで番号が付けられています。

この装置の規則を探る過程で、$m$ 回の動的効果テストのデータを記録しました。各テストにおいて、あなたは光束の番号の区間 $[l, r]$ を指定します。このとき、番号がその区間内にある光束のみが有効化され（区間外の他の光束は切断され）、元々連結していたネットワーク全体がいくつかの独立した連結成分に分裂すると仮定します。

この変化をより深く分析するために、各テストについて、すべての連結成分において、それぞれに含まれる「可視フィルター」（すなわち、出現回数が奇数であるフィルターの色）の種類数の総和を計算してください。

入力

入力の最初の行には、2 つの正整数 $n, m$ ($1 \le n \le 3 \times 10^5, 1 \le m \le 10^6$) が含まれており、それぞれ映像ノードの数とテスト回数を表します。

入力の 2 行目には、$n$ 個の正整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$) が含まれており、それぞれ各映像ノードのフィルターの色を表します。

続く $n-1$ 行のうち、$i$ 行目 ($1 \le i \le n-1$) には 2 つの正整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$) が含まれており、番号 $i$ の光束が接続する 2 つのノードを表します。

続く $m$ 行の各行には、2 つの正整数 $l, r$ ($1 \le l \le r \le n-1$) が含まれており、あるテストにおける光束の番号区間を表します。

出力

$m$ 行を出力してください。各行には非負整数を 1 つ出力し、各テストにおいてすべての独立した連結成分がそれぞれ含む可視フィルターの種類数の総和を順に示してください。

入出力例

入力 1

12 13
2 4 1 2 3 4 2 4 3 3 3 6
3 5
9 1
5 11
4 9
1 12
2 1
10 8
11 10
8 4
6 11
7 6
1 3
2 2
6 6
9 11
6 11
1 4
8 10
1 11
5 10
4 7
1 10
6 8
11 11

出力 1

10
12
12
12
6
8
10
4
8
12
4
10
12