#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5 + 5;
const long long SQRTN = 1003;
const long long LOGN = 22;
const double PI = acos(-1);
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const long long FMOD = 998244353;
const double eps = 1e-9;
void __print(long long x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
T gcd(T a, T b) {
  if (b == 0) return a;
  a %= b;
  return gcd(b, a);
}
template <typename T>
T lcm(T a, T b) {
  return (a * (b / gcd(a, b)));
}
long long add(long long a, long long b, long long c = MOD) {
  long long res = a + b;
  return (res >= c ? res % c : res);
}
long long sub(long long a, long long b, long long c = MOD) {
  long long res;
  if (abs(a - b) < c)
    res = a - b;
  else
    res = (a - b) % c;
  return (res < 0 ? res + c : res);
}
long long mul(long long a, long long b, long long c = MOD) {
  long long res = (long long)a * b;
  return (res >= c ? res % c : res);
}
long long muln(long long a, long long b, long long c = MOD) {
  long long res = (long long)a * b;
  return ((res % c) + c) % c;
}
long long mulmod(long long a, long long b, long long m = MOD) {
  long long q = (long long)(((long double)a * (long double)b) / (long double)m);
  long long r = a * b - q * m;
  if (r > m) r %= m;
  if (r < 0) r += m;
  return r;
}
template <typename T>
T binpow(T e, T n) {
  T x = 1, p = e;
  while (n) {
    if (n & 1) x = x * p;
    p = p * p;
    n >>= 1;
  }
  return x;
}
template <typename T>
T binpow2(T e, T n, T m = MOD) {
  T x = 1, p = e;
  while (n) {
    if (n & 1) x = mul(x, p, m);
    p = mul(p, p, m);
    n >>= 1;
  }
  return x;
}
template <typename T>
T extended_euclid(T a, T b, T &x, T &y) {
  T xx = 0, yy = 1;
  y = 0;
  x = 1;
  while (b) {
    T q = a / b, t = b;
    b = a % b;
    a = t;
    t = xx;
    xx = x - q * xx;
    x = t;
    t = yy;
    yy = y - q * yy;
    y = t;
  }
  return a;
}
template <typename T>
T mod_inverse(T a, T n = MOD) {
  T x, y, z = 0;
  T d = extended_euclid(a, n, x, y);
  return (d > 1 ? -1 : sub(x, z, n));
}
const long long FACSZ = 1e4;
long long fact[FACSZ], ifact[FACSZ];
void precom(long long c = MOD) {
  fact[0] = 1;
  for (long long i = 1; i < FACSZ; i++) fact[i] = mul(fact[i - 1], i, c);
  ifact[FACSZ - 1] = mod_inverse(fact[FACSZ - 1], c);
  for (long long i = FACSZ - 1 - 1; i >= 0; i--) {
    ifact[i] = mul(i + 1, ifact[i + 1], c);
  }
}
vector<long long> primes;
void prime_precom() {
  primes.push_back(2);
  for (long long x = 3; primes.size() <= MAXN; x += 2) {
    bool isPrime = true;
    for (auto p : primes) {
      if (x % p == 0) {
        isPrime = false;
        break;
      }
      if (p * p > x) {
        break;
      }
    }
    if (isPrime) {
      primes.push_back(x);
    }
  }
}
long long ncr(long long n, long long k) {
  if (n < k) return 0;
  if (k == 0) return 1;
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 0; i < k; ++i) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
long long ncr_modp(long long n, long long k, long long c = MOD) {
  if (n < k) return 0;
  if (k == 0) return 1;
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 0; i < k; ++i) {
    res = mul(res, n - i, c);
    res = mul(res, binpow2(i + 1, c - 2, c), c);
  }
  return res;
}
vector<long long> factors;
void factorize(long long a) {
  factors.clear();
  for (long long i = 1; i * i <= a; i++) {
    if (a % i == 0) {
      factors.push_back(i);
      factors.push_back(a / i);
    }
  }
  sort(factors.begin(), factors.end());
}
long long ncr_precom(long long n, long long r, long long c = MOD) {
  return mul(mul(ifact[r], ifact[n - r], c), fact[n], c);
}
long long ceil(long long a, long long b) { return (a + b - 1) / b; }
bool is_prime(long long n) {
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return 0;
    }
  }
  return 1;
}
bool diophantine_checker(long long a, long long b, long long n) {
  for (long long i = 0; i * a <= n; i++) {
    if ((n - (i * a)) % b == 0) {
      return true;
    }
  }
  return false;
}
long long count_divisors(long long n) {
  long long c;
  long long ans = 1;
  for (long long i = 2; i * i <= n; i++) {
    c = 0;
    while (n % i == 0) {
      c++;
      n /= i;
    }
    ans *= (c + 1);
  }
  if (n > 2) {
    return ans * 2;
  }
  return ans;
}
string to_binary(long long n) {
  string r;
  while (n != 0) {
    r = (n % 2 == 0 ? "0" : "1") + r;
    n /= 2;
  }
  return r;
}
bool ispower2(long long x) { return x && (!(x & (x - 1))); }
vector<long long> spf;
void sieve() {
  spf.resize(MAXN);
  spf[1] = 1;
  for (long long i = 2; i < MAXN; i++) {
    spf[i] = i;
  }
  for (long long i = 4; i < MAXN; i += 2) {
    spf[i] = 2;
  }
  for (long long i = 3; i * i <= MAXN; i++) {
    if (spf[i] == i) {
      for (long long j = i * i; j < MAXN; j += i) {
        if (spf[j] == j) {
          spf[j] = i;
        }
      }
    }
  }
}
void pfactor(long long x, vector<long long> &ret) {
  while (x != 1) {
    ret.push_back(spf[x]);
    x = x / spf[x];
  }
}
vector<long long> v[MAXN];
vector<long long> par(MAXN);
long long start;
vector<long long> a(MAXN);
vector<long long> flat_tree(MAXN);
vector<long long> in(MAXN), out(MAXN);
void dfs1(long long node, long long p = 0) {
  par[node] = p;
  in[node] = ++start;
  flat_tree[start] = abs(a[node]);
  for (auto child : v[node]) {
    if (child ^ p) {
      dfs1(child, node);
    }
  }
  out[node] = ++start;
  flat_tree[start] = -abs(a[node]);
}
long long dp[MAXN][LOGN];
vector<long long> depth(MAXN);
void dfs(long long node, long long p = 0) {
  depth[node] = depth[p] + 1;
  dp[node][0] = p;
  for (long long i = 1; i < LOGN; i++) {
    dp[node][i] = dp[dp[node][i - 1]][i - 1];
  }
  for (auto child : v[node]) {
    if (child == p) continue;
    dfs(child, node);
  }
}
long long ancestor(long long node, long long k) {
  for (long long i = 0; i < LOGN && node; i++) {
    if (k & (1ll << i)) {
      node = dp[node][i];
    }
  }
  return (node == 0 ? -1 : node);
}
long long lca(long long node1, long long node2) {
  if (depth[node1] < depth[node2]) {
    swap(node2, node1);
  }
  node1 = ancestor(node1, depth[node1] - depth[node2]);
  if (node1 == node2) return node1;
  for (long long i = LOGN - 1; i >= 0; i--) {
    if (dp[node1][i] != dp[node2][i]) {
      node1 = dp[node1][i];
      node2 = dp[node2][i];
    }
  }
  return dp[node1][0];
}
template <class T>
struct fenwick_tree {
 public:
  fenwick_tree() : _n(0) {}
  fenwick_tree(long long n) : _n(n), data(n) {}
  void add(long long i, T delta) {
    assert(0 <= i && i < _n);
    i++;
    while (i <= _n) {
      data[i - 1] += (delta);
      i += i & -i;
    }
  }
  T sum(long long l, long long r) {
    assert(0 <= l && l <= r && r <= _n);
    return sum(r) - sum(l);
  }

 private:
  long long _n;
  vector<T> data;
  T sum(long long r) {
    T s = 0;
    while (r > 0) {
      s += data[r - 1];
      r -= r & -r;
    }
    return s;
  }
};
void solvethetestcase() {
  long long n, q;
  cin >> n >> q;
  for (long long i = 0; i < n; i++) {
    cin >> a[i + 1];
  }
  for (long long i = 0; i < n - 1; i++) {
    long long a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  dfs1(1);
  dfs(1);
  fenwick_tree<long long> ft(2 * n + 2);
  for (long long i = 0; i < 2 * n + 1; i++) {
    ft.add(i, flat_tree[i]);
  }
  while (q--) {
    long long op;
    cin >> op;
    if (op == 1) {
      long long u, x;
      cin >> u >> x;
      long long i1 = in[u];
      long long i2 = out[u];
      long long v1 = ft.sum(i1, i1 + 1);
      long long v2 = ft.sum(i2, i2 + 1);
      ft.add(i1, -v1);
      ft.add(i2, -v2);
      ft.add(i1, abs(x));
      ft.add(i2, -abs(x));
    } else {
      long long e1, e2;
      cin >> e1 >> e2;
      long long l = lca(e1, e2);
      if (l == e1 || l == e2) {
        if (l == e2) {
          swap(e1, e2);
        }
        if (e1 == e2) {
          cout << 0 << "\n";
          continue;
        }
        cout << ft.sum(in[e1], in[e2] + 1ll) +
                    ((in[e1] + 1 < in[e2]) ? ft.sum(in[e1] + 1, in[e2]) : 0ll)
             << "\n";
      } else {
        cout << ft.sum(in[l], in[e1] + 1ll) + ft.sum(in[l], in[e2] + 1ll) +
                    ((in[l] + 1ll < in[e1]) ? ft.sum(in[l] + 1ll, in[e1])
                                            : 0ll) +
                    ((in[l] + 1ll < in[e2]) ? ft.sum(in[l] + 1ll, in[e2]) : 0ll)
             << "\n";
      }
    }
  }
}
signed main() {
  cout << fixed << setprecision(12);
  ;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  for (long long testcase = 1; testcase < t + 1; testcase++) {
    solvethetestcase();
  }
}

### Prompt

Please formulate 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;
const long long MAXN = 2e5 + 5;
const long long SQRTN = 1003;
const long long LOGN = 22;
const double PI = acos(-1);
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const long long FMOD = 998244353;
const double eps = 1e-9;
void __print(long long x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
T gcd(T a, T b) {
  if (b == 0) return a;
  a %= b;
  return gcd(b, a);
}
template <typename T>
T lcm(T a, T b) {
  return (a * (b / gcd(a, b)));
}
long long add(long long a, long long b, long long c = MOD) {
  long long res = a + b;
  return (res >= c ? res % c : res);
}
long long sub(long long a, long long b, long long c = MOD) {
  long long res;
  if (abs(a - b) < c)
    res = a - b;
  else
    res = (a - b) % c;
  return (res < 0 ? res + c : res);
}
long long mul(long long a, long long b, long long c = MOD) {
  long long res = (long long)a * b;
  return (res >= c ? res % c : res);
}
long long muln(long long a, long long b, long long c = MOD) {
  long long res = (long long)a * b;
  return ((res % c) + c) % c;
}
long long mulmod(long long a, long long b, long long m = MOD) {
  long long q = (long long)(((long double)a * (long double)b) / (long double)m);
  long long r = a * b - q * m;
  if (r > m) r %= m;
  if (r < 0) r += m;
  return r;
}
template <typename T>
T binpow(T e, T n) {
  T x = 1, p = e;
  while (n) {
    if (n & 1) x = x * p;
    p = p * p;
    n >>= 1;
  }
  return x;
}
template <typename T>
T binpow2(T e, T n, T m = MOD) {
  T x = 1, p = e;
  while (n) {
    if (n & 1) x = mul(x, p, m);
    p = mul(p, p, m);
    n >>= 1;
  }
  return x;
}
template <typename T>
T extended_euclid(T a, T b, T &x, T &y) {
  T xx = 0, yy = 1;
  y = 0;
  x = 1;
  while (b) {
    T q = a / b, t = b;
    b = a % b;
    a = t;
    t = xx;
    xx = x - q * xx;
    x = t;
    t = yy;
    yy = y - q * yy;
    y = t;
  }
  return a;
}
template <typename T>
T mod_inverse(T a, T n = MOD) {
  T x, y, z = 0;
  T d = extended_euclid(a, n, x, y);
  return (d > 1 ? -1 : sub(x, z, n));
}
const long long FACSZ = 1e4;
long long fact[FACSZ], ifact[FACSZ];
void precom(long long c = MOD) {
  fact[0] = 1;
  for (long long i = 1; i < FACSZ; i++) fact[i] = mul(fact[i - 1], i, c);
  ifact[FACSZ - 1] = mod_inverse(fact[FACSZ - 1], c);
  for (long long i = FACSZ - 1 - 1; i >= 0; i--) {
    ifact[i] = mul(i + 1, ifact[i + 1], c);
  }
}
vector<long long> primes;
void prime_precom() {
  primes.push_back(2);
  for (long long x = 3; primes.size() <= MAXN; x += 2) {
    bool isPrime = true;
    for (auto p : primes) {
      if (x % p == 0) {
        isPrime = false;
        break;
      }
      if (p * p > x) {
        break;
      }
    }
    if (isPrime) {
      primes.push_back(x);
    }
  }
}
long long ncr(long long n, long long k) {
  if (n < k) return 0;
  if (k == 0) return 1;
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 0; i < k; ++i) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
long long ncr_modp(long long n, long long k, long long c = MOD) {
  if (n < k) return 0;
  if (k == 0) return 1;
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 0; i < k; ++i) {
    res = mul(res, n - i, c);
    res = mul(res, binpow2(i + 1, c - 2, c), c);
  }
  return res;
}
vector<long long> factors;
void factorize(long long a) {
  factors.clear();
  for (long long i = 1; i * i <= a; i++) {
    if (a % i == 0) {
      factors.push_back(i);
      factors.push_back(a / i);
    }
  }
  sort(factors.begin(), factors.end());
}
long long ncr_precom(long long n, long long r, long long c = MOD) {
  return mul(mul(ifact[r], ifact[n - r], c), fact[n], c);
}
long long ceil(long long a, long long b) { return (a + b - 1) / b; }
bool is_prime(long long n) {
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return 0;
    }
  }
  return 1;
}
bool diophantine_checker(long long a, long long b, long long n) {
  for (long long i = 0; i * a <= n; i++) {
    if ((n - (i * a)) % b == 0) {
      return true;
    }
  }
  return false;
}
long long count_divisors(long long n) {
  long long c;
  long long ans = 1;
  for (long long i = 2; i * i <= n; i++) {
    c = 0;
    while (n % i == 0) {
      c++;
      n /= i;
    }
    ans *= (c + 1);
  }
  if (n > 2) {
    return ans * 2;
  }
  return ans;
}
string to_binary(long long n) {
  string r;
  while (n != 0) {
    r = (n % 2 == 0 ? "0" : "1") + r;
    n /= 2;
  }
  return r;
}
bool ispower2(long long x) { return x && (!(x & (x - 1))); }
vector<long long> spf;
void sieve() {
  spf.resize(MAXN);
  spf[1] = 1;
  for (long long i = 2; i < MAXN; i++) {
    spf[i] = i;
  }
  for (long long i = 4; i < MAXN; i += 2) {
    spf[i] = 2;
  }
  for (long long i = 3; i * i <= MAXN; i++) {
    if (spf[i] == i) {
      for (long long j = i * i; j < MAXN; j += i) {
        if (spf[j] == j) {
          spf[j] = i;
        }
      }
    }
  }
}
void pfactor(long long x, vector<long long> &ret) {
  while (x != 1) {
    ret.push_back(spf[x]);
    x = x / spf[x];
  }
}
vector<long long> v[MAXN];
vector<long long> par(MAXN);
long long start;
vector<long long> a(MAXN);
vector<long long> flat_tree(MAXN);
vector<long long> in(MAXN), out(MAXN);
void dfs1(long long node, long long p = 0) {
  par[node] = p;
  in[node] = ++start;
  flat_tree[start] = abs(a[node]);
  for (auto child : v[node]) {
    if (child ^ p) {
      dfs1(child, node);
    }
  }
  out[node] = ++start;
  flat_tree[start] = -abs(a[node]);
}
long long dp[MAXN][LOGN];
vector<long long> depth(MAXN);
void dfs(long long node, long long p = 0) {
  depth[node] = depth[p] + 1;
  dp[node][0] = p;
  for (long long i = 1; i < LOGN; i++) {
    dp[node][i] = dp[dp[node][i - 1]][i - 1];
  }
  for (auto child : v[node]) {
    if (child == p) continue;
    dfs(child, node);
  }
}
long long ancestor(long long node, long long k) {
  for (long long i = 0; i < LOGN && node; i++) {
    if (k & (1ll << i)) {
      node = dp[node][i];
    }
  }
  return (node == 0 ? -1 : node);
}
long long lca(long long node1, long long node2) {
  if (depth[node1] < depth[node2]) {
    swap(node2, node1);
  }
  node1 = ancestor(node1, depth[node1] - depth[node2]);
  if (node1 == node2) return node1;
  for (long long i = LOGN - 1; i >= 0; i--) {
    if (dp[node1][i] != dp[node2][i]) {
      node1 = dp[node1][i];
      node2 = dp[node2][i];
    }
  }
  return dp[node1][0];
}
template <class T>
struct fenwick_tree {
 public:
  fenwick_tree() : _n(0) {}
  fenwick_tree(long long n) : _n(n), data(n) {}
  void add(long long i, T delta) {
    assert(0 <= i && i < _n);
    i++;
    while (i <= _n) {
      data[i - 1] += (delta);
      i += i & -i;
    }
  }
  T sum(long long l, long long r) {
    assert(0 <= l && l <= r && r <= _n);
    return sum(r) - sum(l);
  }

 private:
  long long _n;
  vector<T> data;
  T sum(long long r) {
    T s = 0;
    while (r > 0) {
      s += data[r - 1];
      r -= r & -r;
    }
    return s;
  }
};
void solvethetestcase() {
  long long n, q;
  cin >> n >> q;
  for (long long i = 0; i < n; i++) {
    cin >> a[i + 1];
  }
  for (long long i = 0; i < n - 1; i++) {
    long long a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  dfs1(1);
  dfs(1);
  fenwick_tree<long long> ft(2 * n + 2);
  for (long long i = 0; i < 2 * n + 1; i++) {
    ft.add(i, flat_tree[i]);
  }
  while (q--) {
    long long op;
    cin >> op;
    if (op == 1) {
      long long u, x;
      cin >> u >> x;
      long long i1 = in[u];
      long long i2 = out[u];
      long long v1 = ft.sum(i1, i1 + 1);
      long long v2 = ft.sum(i2, i2 + 1);
      ft.add(i1, -v1);
      ft.add(i2, -v2);
      ft.add(i1, abs(x));
      ft.add(i2, -abs(x));
    } else {
      long long e1, e2;
      cin >> e1 >> e2;
      long long l = lca(e1, e2);
      if (l == e1 || l == e2) {
        if (l == e2) {
          swap(e1, e2);
        }
        if (e1 == e2) {
          cout << 0 << "\n";
          continue;
        }
        cout << ft.sum(in[e1], in[e2] + 1ll) +
                    ((in[e1] + 1 < in[e2]) ? ft.sum(in[e1] + 1, in[e2]) : 0ll)
             << "\n";
      } else {
        cout << ft.sum(in[l], in[e1] + 1ll) + ft.sum(in[l], in[e2] + 1ll) +
                    ((in[l] + 1ll < in[e1]) ? ft.sum(in[l] + 1ll, in[e1])
                                            : 0ll) +
                    ((in[l] + 1ll < in[e2]) ? ft.sum(in[l] + 1ll, in[e2]) : 0ll)
             << "\n";
      }
    }
  }
}
signed main() {
  cout << fixed << setprecision(12);
  ;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  for (long long testcase = 1; testcase < t + 1; testcase++) {
    solvethetestcase();
  }
}

```