tanprodium, người được mệnh danh là nặng \(10^7\) \(\text{kg}\) tại trường LQD đã thực hiện một phi vụ cực kỳ mạo hiểm, đó là trốn học lớp học của GSPVH cute. Tưởng rằng có thể một tay che trời, nhưng ngờ đâu, Flower_On_Stone đã phát hiện ra vụ việc này và rất tức giận. Flower_On_Stone quyết định dạy cho hắn một bài học nhớ đời. Để kiểm tra kiến thức lập trình của hắn, Flower_On_Stone đã ra 1 bài toán rất khó để đố hắn, và nếu không giải được thì tanprodium phải chịu phạt rất nặng. Nhưng vì hắn đang buồn vì tình nên không có tâm trí làm bài, mà lại không muốn chịu phạt nên tanprodium đã quyết định nhờ các bạn pro coder trên LQDOJ giải hộ. Là một pro coder, bạn hãy giải bài toán này giúp hắn nhé.

Cho một cây có \(n\) đỉnh, mỗi đỉnh có một trọng số và hai số \(a, b\). Hãy đếm số cặp \((u, v)\) mà \(u \leq v\) sao cho tổng xor các đỉnh trên đường đi từ \(u\) đến \(v\) lớn hơn hoặc bằng \(a\) và bé hơn hoặc bằng \(b\).

Input

• Dòng đầu tiên chứa số \(n\) và hai số \(a, b\)

• Dòng thứ hai chứa \(n\) số nguyên \(l_1, l_2 ... l_n\) trong đó \(l_ì\) là trọng số của đỉnh thứ \(i\)

• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) đại diện cho một cạnh của cây

Output

• Gồm một dòng là kết quả bài toán

Constants

• \(n \leq 100000\)

• \(1 \leq a,b,l_i \leq 10^9\)

• \(1 \leq u, v \leq n\)

Dữ liệu vào đảm bảo đồ thị là một cây

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 5000\)

• Subtask \(2\) (\(25\%\) số điểm): Cây là một đường thẳng, các cạnh có dạng \((i, i+1)\) với $ 1 \leq i < n$

• Subtask \(3\) (\(25\%\) số điểm): Cây là một cây nhị phân, các cạnh có dạng \((\lfloor{\dfrac{i}{2}\rfloor}, i)\) với $ 1 < i \leq n$

• Subtask \(4\) (\(25\%\) số điểm): Giới hạn gốc, không có ràng buộc gì thêm.

Example

3 1 3
1 2 3
1 2
2 3

5