Distinct Problem Path Queries

In this problem, you are given a rooted tree with (n) nodes (the root is node (1)). Each node (i) has an associated problem type (a_i). Two nodes (i) and (j) have the same problem source if and only if (a_i = a_j).

There are (m) queries. Each query is one of the following two types:

1. Query Type 1:
       1 x y
       For the unique simple path between nodes (x) and (y) (including both endpoints), determine the number of distinct problem types (i.e. distinct values among (a_i) for nodes on the path).
   
   
2. Query Type 2:
       2 A B
       Let the path from node (A) to the root (node (1)) be (P_A) and the path from node (B) to the root be (P_B). A node (x) is chosen uniformly at random from (P_A) and a node (y) from (P_B). Let (cnt_A) and (cnt_B) be the number of nodes in (P_A) and (P_B) respectively. The query asks for the expected value of the answer to query type 1 on the pair ((x, y)). It is guaranteed that the expectation can be written as a rational number of the form (\frac{ans}{cnt_A \times cnt_B}). You only need to output the numerator (ans).
   
   Note: For query type 1, the path between (x) and (y) can be constructed by taking the path from (x) to (LCA(x,y)) and then from (LCA(x,y)) to (y) (with the lowest common ancestor counted only once).

inputFormat

The first line contains two integers (n) and (m) denoting the number of nodes and the number of queries respectively.<br> The second line contains (n) integers (a_1, a_2, \ldots, a_n), where (a_i) represents the type of the problem at node (i).

Each of the following (n-1) lines contains two integers (u) and (v) indicating there is an edge between nodes (u) and (v) (forming a tree with root at node 1).

Each of the next (m) lines represents a query in one of the two formats:

• For Query Type 1: 1 x y
  
• For Query Type 2: 2 A B

outputFormat

For each query, output a single integer on a separate line representing the answer.

For Query Type 1, output the number of distinct problem types on the path between (x) and (y).
For Query Type 2, output the numerator (ans) such that the expected value is (\frac{ans}{cnt_A \times cnt_B}).

sample

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

3
16
2
4