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.
#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2,bmi,bmi2")
using namespace std;
using ll = long long int;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

/**
 * Point-update Segment Tree
 * Source: kactl
 * Description: Iterative point-update segment tree, ranges are half-open i.e [L, R).
 *              f is any associative function.
 * Time: O(logn) update/query
 */

template<class T, T unit = T()>
struct SegTree {
    T f(T a, T b) { return a+b; }
    vector<T> s; int n;
    SegTree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {}
    void update(int pos, T val) {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e) {
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

const int N = 1e5 + 5;
const int LOG = 19;
int jump[LOG][N];

struct HLD {
    int N, tim = 0;
    vector<vector<int>> adj;
    vector<int> par, siz, depth, rt, pos, out;
    SegTree<ll> tree;
    HLD(vector<vector<int>> adj_)
        : N(size(adj_)), adj(adj_), par(N, -1), siz(N, 1), depth(N),
          rt(N),pos(N),out(N), tree(N){ dfsSz(0); dfsHld(0); }
    void dfsSz(int v) {
        if (par[v] != -1) {
            adj[v].erase(find(begin(adj[v]), end(adj[v]), par[v]));
            jump[0][v] = par[v];
            for (int level = 1; level < LOG; ++level)
                jump[level][v] = jump[level-1][jump[level-1][v]];
        }
        for (int& u : adj[v]) {
            par[u] = v, depth[u] = depth[v] + 1;
            dfsSz(u);
            siz[v] += siz[u];
            if (siz[u] > siz[adj[v][0]]) swap(u, adj[v][0]);
        }
    }
    void dfsHld(int v) {
        pos[v] = tim++;
        for (int u : adj[v]) {
            rt[u] = (u == adj[v][0] ? rt[v] : u);
            dfsHld(u);
        }
        out[v] = tim;
    }
    template <class B> void process(int u, int v, B op) {
        for (; rt[u] != rt[v]; v = par[rt[v]]) {
            if (depth[rt[u]] > depth[rt[v]]) swap(u, v);
            op(pos[rt[v]], pos[v] + 1);
        }
        if (depth[u] > depth[v]) swap(u, v);
        op(pos[u], pos[v] + 1);
    }
    // void modifyPath(int u, int v, int val) {
    //     process(u, v, [&](int l, int r) { tree->add(l, r, val); });
    // }
    void modify (int u, int val) {
        tree.update(pos[u], val);
    }
    ll queryPath(int u, int v) { // Modify depending on problem
        ll res = 0;
        process(u, v, [&](int l, int r) {
                res += tree.query(l, r);
        });
        return res;
    }
    // int querySubtree(int v) { // modifySubtree is similar
    //     return tree->query(pos[v] + VALS_EDGES, pos[v] + siz[v]);
    // }
};


int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    int n, q; cin >> n >> q;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    vector<vector<int>> adj(n);
    vector<int> deg(n);
    for (int i = 0; i+1 < n; ++i) {
        int u, v; cin >> u >> v;
        adj[--u].push_back(--v);
        adj[v].push_back(u);
        ++deg[u], ++deg[v];
    }
    HLD hld(adj);
    auto is_anc = [&] (int u, int v) {
        return hld.pos[u] <= hld.pos[v] and hld.out[u] >= hld.out[v];
    };
    auto get_highest = [&] (int u, int v) {
        for (int level = LOG-1; level >= 0; --level)
            if (!is_anc(jump[level][u], v))
                u = jump[level][u];
        return u;
    };
    auto lca = [&] (int u, int v) {
        if (is_anc(u, v)) return u;
        return hld.par[get_highest(u, v)];
    };

    const int MAGIC = 350;
    vector<int> heavy;
    for (int i = 0; i < n; ++i)
        if (deg[i] >= MAGIC)
            heavy.push_back(i);
    for (int u = 0; u < n; ++u) {
        if (deg[u] >= MAGIC) continue;
        for (int v : adj[u]) {
            if (deg[v] >= MAGIC) continue;

            if (hld.pos[u] < hld.pos[v]) hld.modify(v, max(abs(a[u] + a[v]), abs(a[u] - a[v])));
            else hld.modify(u, max(abs(a[u] + a[v]), abs(a[u] - a[v])));
        }
    }

    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int u, c; cin >> u >> c; --u;
            a[u] = c;
            if (deg[u] < MAGIC) {
                for (int v : adj[u]) {
                    if (deg[v] >= MAGIC) continue;

                    if (hld.pos[u] < hld.pos[v]) hld.modify(v, max(abs(a[u] + a[v]), abs(a[u] - a[v])));
                    else hld.modify(u, max(abs(a[u] + a[v]), abs(a[u] - a[v])));
                }
            }
        }
        else {
            int u, v; cin >> u >> v; --u, --v;
            if (u == v) {cout << 0 << '\n'; continue;}
            int l = lca(u, v);
            ll res = hld.queryPath(u, v) - hld.queryPath(l, l);
            ll sub = 0;
            for (int x : heavy) {
                int ct = is_anc(x, u) + (1<<is_anc(x, v));
                if (ct == 0) continue;
                else if (ct == 1) {
                    int y = get_highest(u, x);
                    if (y != x) {
                        res += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                        if (deg[y] >= MAGIC and x < y) sub += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                    }
                    y = hld.par[x];
                    res += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                    if (deg[y] >= MAGIC and x < y) sub += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                }
                else if (ct == 2) {
                    // int y = get_highest(v, x);
                    // res += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                    // y = hld.par[x];
                    // res += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                    int y = get_highest(v, x);
                    if (y != x) {
                        res += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                        if (deg[y] >= MAGIC and x < y) sub += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                    }
                    y = hld.par[x];
                    res += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                    if (deg[y] >= MAGIC and x < y) sub += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                }
                else {
                    if (x != l) continue;
                    int y = get_highest(u, x);
                    if (y != x) {
                        res += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                        if (deg[y] >= MAGIC and x < y) sub += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                    }
                    y = get_highest(v, x);
                    if (y != x) {
                        res += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                        if (deg[y] >= MAGIC and x < y) sub += max(abs(a[x] + a[y]), abs(a[x] - a[y]));
                    }
                }
            }
            cout << res - sub << '\n';
        }
    }
}