#include<bits/stdc++.h>
using namespace std;
#define end END
#define int long long
const int N=1e5+5,inf=1e12;
int n,T,a[N],f[N],top[N],end[N],siz[N],h[N],dp[N][2],light[N][2],stamp,dfn[N],rnk[N];
vector<int>g[N];
char no;
void dfs(int u,int last){
    f[u]=last,siz[u]=1,dp[u][1]=a[u];
    for(int v:g[u]){
        if(v!=last){
            dfs(v,u),siz[u]+=siz[v],dp[u][0]+=dp[v][1],dp[u][1]+=min(dp[v][0],dp[v][1]);
            if(siz[h[u]]<siz[v]){
                h[u]=v;
            }
        }
    }
}
struct matrix{
    int a[3][3];
    matrix(){
        a[1][1]=a[2][2]=0,a[1][2]=a[2][1]=inf;
    }
    int*operator[](int x){
        return a[x];
    }
    friend matrix operator*(matrix a,matrix b){
        matrix c;
        for(int i=1;i<=2;i++){
            for(int j=1;j<=2;j++){
                for(int k=1;k<=2;k++){
                    c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
                }
            }
        }
        return c;
    }
}mul[N];
void dfs(int u,int last,int Top){
    top[u]=Top,dfn[u]=++stamp,rnk[stamp]=u,light[u][1]=a[u];
    if(!h[u]){
        end[u]=u;
        return;
    }
    dfs(h[u],u,Top),end[u]=end[h[u]];
    for(int v:g[u]){
        if(v!=last&&v!=h[u]){
            dfs(v,u,v),light[u][0]+=dp[v][1],light[u][1]+=min(dp[v][0],dp[v][1]);
        }
    }
    mul[u][1][1]=inf,mul[u][1][2]=light[u][0],mul[u][2][1]=mul[u][2][2]=light[u][1];
}
struct segtree{
    struct node{
        int l,r;
        matrix mul;
    }t[N*4];
    void pushup(int u){
        t[u].mul=t[u*2].mul*t[u*2+1].mul;
    }
    void build(int u,int l,int r){
        t[u].l=l,t[u].r=r;
        if(l==r){
            t[u].mul=mul[rnk[l]];
            return;
        }
        int mid=(l+r)>>1;
        build(u*2,l,mid),build(u*2+1,mid+1,r),pushup(u);
    }
    void modify(int u,int x){
        if(t[u].l==t[u].r){
            t[u].mul=mul[rnk[x]];
            return;
        }
        int mid=(t[u].l+t[u].r)>>1;
        if(x<=mid){
            modify(u*2,x);
        }
        else{
            modify(u*2+1,x);
        }
        pushup(u);
    }
    matrix query(int u,int l,int r){
        if(t[u].l>=l&&t[u].r<=r){
            return t[u].mul;
        }
        int mid=(t[u].l+t[u].r)>>1;
        if(l<=mid&&r>mid){
            return query(u*2,l,r)*query(u*2+1,l,r);
        }
        if(l<=mid){
            return query(u*2,l,r);
        }
        return query(u*2+1,l,r);
    }
}segtree;
matrix calc(int u){
    matrix ret=segtree.query(1,dfn[top[u]],dfn[end[u]]),base;
    base[2][1]=a[end[u]];
    return ret*base;
}
void modify(int u,int x){
    matrix bef=calc(u);
    mul[u][2][1]+=x-a[u],mul[u][2][2]=mul[u][2][1],a[u]=x;
    while(u){
        segtree.modify(1,dfn[u]);
        matrix aft=calc(u);
        u=f[top[u]],mul[u][1][2]+=aft[2][1]-bef[2][1],mul[u][2][1]+=min(aft[1][1],aft[2][1])-min(bef[1][1],bef[2][1]),mul[u][2][2]=mul[u][2][1],bef=calc(u);
    }
}
signed main(){
    cin>>n>>T>>no>>no;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v,g[u].push_back(v),g[v].push_back(u);
    }
    dfs(1,0),dfs(1,0,1),segtree.build(1,1,n);
    for(int A,x,B,y,tmpA,tmpB;T--;){
        cin>>A>>x>>B>>y,tmpA=a[A],tmpB=a[B];
        if(x){
            modify(A,-inf);
        }
        else{
            modify(A,inf);
        }
        if(y){
            modify(B,-inf);
        }
        else{
            modify(B,inf);
        }
        matrix ret=calc(1);
        int ans=min(ret[1][1],ret[2][1]);
        if(x){
            ans+=inf,ans+=tmpA;
        }
        if(y){
            ans+=inf,ans+=tmpB;
        }
        if(ans>1e10){
            ans=-1;
        }
        cout<<ans<<'\n';
        modify(A,tmpA),modify(B,tmpB);
    }
}