#include <bits/stdc++.h>
using namespace std;
template <typename T>
void dbn(T a) {
  cerr << "#0 = " << a << '\n';
}
template <typename T, typename... Rest>
void dbn(T a, Rest... rest) {
  dbn(rest...);
  cerr << '#' << sizeof...(rest) << " = " << a << '\n';
}
const int MAX_N = 100002;
const int MAGIC = 300;
const int LG_N = 17;
int n, nQueries, timer, buffer_value[MAX_N], a[MAX_N], tin[MAX_N], tout[MAX_N];
int64_t f[MAX_N];
int p[MAX_N][LG_N + 2];
bool in_buffer[MAX_N];
vector<int> g[MAX_N];
vector<int> buffer;
int64_t calc_old_weight(int u, int v) {
  return max(abs(a[u] + a[v]), abs(a[u] - a[v]));
}
int64_t calc_new_weight(int u, int v) {
  int x = (in_buffer[u] ? buffer_value[u] : a[u]);
  int y = (in_buffer[v] ? buffer_value[v] : a[v]);
  return max(abs(x + y), abs(x - y));
}
void fix_root(int u) {
  tin[u] = ++timer;
  for (auto v : g[u]) {
    if (v != p[u][0]) {
      p[v][0] = u;
      f[v] = f[u] + calc_old_weight(u, v);
      fix_root(v);
    }
  }
  tout[u] = ++timer;
}
void build_lca() {
  for (int i = 1; i <= LG_N; ++i) {
    for (int u = 1; u <= n; ++u) {
      p[u][i] = p[p[u][i - 1]][i - 1];
    }
  }
  for (int u = 2; u <= n; ++u)
    g[u].erase(find(g[u].begin(), g[u].end(), p[u][0]));
}
bool is_ancestor(int u, int v) {
  return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
  if (is_ancestor(u, v)) return u;
  if (is_ancestor(v, u)) return v;
  for (int i = LG_N; i >= 0; --i) {
    if (p[u][i] != 0 && !is_ancestor(p[u][i], v)) u = p[u][i];
  }
  return p[u][0];
}
void add_update_query(int u, int c) {
  if (!in_buffer[u]) buffer.push_back(u);
  in_buffer[u] = true;
  buffer_value[u] = c;
  if (buffer.size() > MAGIC) {
    for (auto v : buffer) {
      in_buffer[v] = false;
      a[v] = buffer_value[v];
    }
    buffer.clear();
    fix_root(1);
  }
}
int bisect(int anc, int des) {
  int l = 0, r = (int)g[anc].size() - 1;
  for (int mid = (l + r) / 2; mid != l && mid != r; mid = (l + r) / 2) {
    int u = g[anc][mid];
    if (tout[u] < tout[des])
      l = mid;
    else
      r = mid;
  }
  for (int mid = l; mid <= r; ++mid) {
    int u = g[anc][mid];
    if (is_ancestor(u, des)) return u;
  }
  assert(0);
}
bool onPath(int u, int v, int anc, int w) {
  if (!is_ancestor(anc, w)) return false;
  return is_ancestor(w, u) || is_ancestor(w, v);
}
int64_t query(int u, int v) {
  int anc = lca(u, v);
  int64_t res = f[u] + f[v] - 2 * f[anc];
  for (auto w : buffer) {
    if (!onPath(u, v, anc, w)) continue;
    if (onPath(u, v, anc, p[w][0]) && !in_buffer[p[w][0]])
      res = res - calc_old_weight(w, p[w][0]) + calc_new_weight(w, p[w][0]);
    if (u != w && is_ancestor(w, u)) {
      int t = bisect(w, u);
      res = res - calc_old_weight(w, t) + calc_new_weight(w, t);
    }
    if (v != w && is_ancestor(w, v)) {
      int t = bisect(w, v);
      res = res - calc_old_weight(w, t) + calc_new_weight(w, t);
    }
  }
  return res;
}
int main() {
  cin >> n >> nQueries;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  fix_root(1);
  build_lca();
  while (nQueries--) {
    int t, u, v;
    cin >> t >> u >> v;
    if (t == 1)
      add_update_query(u, v);
    else {
      cout << query(u, v) << '\n';
    }
  }
}

### Prompt

Generate a cpp solution to the following problem:

Chanek Jones is back, helping his long-lost relative Indiana Jones, to find a secret treasure in a maze buried below a desert full of illusions.

The map of the labyrinth forms a tree with n rooms numbered from 1 to n and n - 1 tunnels connecting them such that it is possible to travel between each pair of rooms through several tunnels.

The i-th room (1 ≤ i ≤ n) has a_i illusion rate. To go from the x-th room to the y-th room, there must exist a tunnel between x and y, and it takes max(|a_x + a_y|, |a_x - a_y|) energy. |z| denotes the absolute value of z.

To prevent grave robbers, the maze can change the illusion rate of any room in it. Chanek and Indiana would ask q queries.

There are two types of queries to be done:

  * 1\ u\ c — The illusion rate of the x-th room is changed to c (1 ≤ u ≤ n, 0 ≤ |c| ≤ 10^9). 
  * 2\ u\ v — Chanek and Indiana ask you the minimum sum of energy needed to take the secret treasure at room v if they are initially at room u (1 ≤ u, v ≤ n). 



Help them, so you can get a portion of the treasure!

Input

The first line contains two integers n and q (2 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5) — the number of rooms in the maze and the number of queries.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ |a_i| ≤ 10^9) — inital illusion rate of each room.

The i-th of the next n-1 lines contains two integers s_i and t_i (1 ≤ s_i, t_i ≤ n), meaning there is a tunnel connecting s_i-th room and t_i-th room. The given edges form a tree.

The next q lines contain the query as described. The given queries are valid.

Output

For each type 2 query, output a line containing an integer — the minimum sum of energy needed for Chanek and Indiana to take the secret treasure.

Example

Input


6 4
10 -9 2 -1 4 -6
1 5
5 4
5 6
6 2
6 3
2 1 2
1 1 -3
2 1 2
2 3 3


Output


39
32
0

Note

<image>

In the first query, their movement from the 1-st to the 2-nd room is as follows.

  * 1 → 5 — takes max(|10 + 4|, |10 - 4|) = 14 energy. 
  * 5 → 6 — takes max(|4 + (-6)|, |4 - (-6)|) = 10 energy. 
  * 6 → 2 — takes max(|-6 + (-9)|, |-6 - (-9)|) = 15 energy. 

In total, it takes 39 energy.

In the second query, the illusion rate of the 1-st room changes from 10 to -3.

In the third query, their movement from the 1-st to the 2-nd room is as follows.

  * 1 → 5 — takes max(|-3 + 4|, |-3 - 4|) = 7 energy. 
  * 5 → 6 — takes max(|4 + (-6)|, |4 - (-6)|) = 10 energy. 
  * 6 → 2 — takes max(|-6 + (-9)|, |-6 - (-9)|) = 15 energy. 



Now, it takes 32 energy.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void dbn(T a) {
  cerr << "#0 = " << a << '\n';
}
template <typename T, typename... Rest>
void dbn(T a, Rest... rest) {
  dbn(rest...);
  cerr << '#' << sizeof...(rest) << " = " << a << '\n';
}
const int MAX_N = 100002;
const int MAGIC = 300;
const int LG_N = 17;
int n, nQueries, timer, buffer_value[MAX_N], a[MAX_N], tin[MAX_N], tout[MAX_N];
int64_t f[MAX_N];
int p[MAX_N][LG_N + 2];
bool in_buffer[MAX_N];
vector<int> g[MAX_N];
vector<int> buffer;
int64_t calc_old_weight(int u, int v) {
  return max(abs(a[u] + a[v]), abs(a[u] - a[v]));
}
int64_t calc_new_weight(int u, int v) {
  int x = (in_buffer[u] ? buffer_value[u] : a[u]);
  int y = (in_buffer[v] ? buffer_value[v] : a[v]);
  return max(abs(x + y), abs(x - y));
}
void fix_root(int u) {
  tin[u] = ++timer;
  for (auto v : g[u]) {
    if (v != p[u][0]) {
      p[v][0] = u;
      f[v] = f[u] + calc_old_weight(u, v);
      fix_root(v);
    }
  }
  tout[u] = ++timer;
}
void build_lca() {
  for (int i = 1; i <= LG_N; ++i) {
    for (int u = 1; u <= n; ++u) {
      p[u][i] = p[p[u][i - 1]][i - 1];
    }
  }
  for (int u = 2; u <= n; ++u)
    g[u].erase(find(g[u].begin(), g[u].end(), p[u][0]));
}
bool is_ancestor(int u, int v) {
  return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
  if (is_ancestor(u, v)) return u;
  if (is_ancestor(v, u)) return v;
  for (int i = LG_N; i >= 0; --i) {
    if (p[u][i] != 0 && !is_ancestor(p[u][i], v)) u = p[u][i];
  }
  return p[u][0];
}
void add_update_query(int u, int c) {
  if (!in_buffer[u]) buffer.push_back(u);
  in_buffer[u] = true;
  buffer_value[u] = c;
  if (buffer.size() > MAGIC) {
    for (auto v : buffer) {
      in_buffer[v] = false;
      a[v] = buffer_value[v];
    }
    buffer.clear();
    fix_root(1);
  }
}
int bisect(int anc, int des) {
  int l = 0, r = (int)g[anc].size() - 1;
  for (int mid = (l + r) / 2; mid != l && mid != r; mid = (l + r) / 2) {
    int u = g[anc][mid];
    if (tout[u] < tout[des])
      l = mid;
    else
      r = mid;
  }
  for (int mid = l; mid <= r; ++mid) {
    int u = g[anc][mid];
    if (is_ancestor(u, des)) return u;
  }
  assert(0);
}
bool onPath(int u, int v, int anc, int w) {
  if (!is_ancestor(anc, w)) return false;
  return is_ancestor(w, u) || is_ancestor(w, v);
}
int64_t query(int u, int v) {
  int anc = lca(u, v);
  int64_t res = f[u] + f[v] - 2 * f[anc];
  for (auto w : buffer) {
    if (!onPath(u, v, anc, w)) continue;
    if (onPath(u, v, anc, p[w][0]) && !in_buffer[p[w][0]])
      res = res - calc_old_weight(w, p[w][0]) + calc_new_weight(w, p[w][0]);
    if (u != w && is_ancestor(w, u)) {
      int t = bisect(w, u);
      res = res - calc_old_weight(w, t) + calc_new_weight(w, t);
    }
    if (v != w && is_ancestor(w, v)) {
      int t = bisect(w, v);
      res = res - calc_old_weight(w, t) + calc_new_weight(w, t);
    }
  }
  return res;
}
int main() {
  cin >> n >> nQueries;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  fix_root(1);
  build_lca();
  while (nQueries--) {
    int t, u, v;
    cin >> t >> u >> v;
    if (t == 1)
      add_update_query(u, v);
    else {
      cout << query(u, v) << '\n';
    }
  }
}

```