#include<stack>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,M=,inf=1e9;

 int siz[N],far[N],imp[N],top[N],lst[N];

 int p[N],noww[M],goal[M],val[N],dfn[N];

 int n,m,t1,t2,t3,t4,t5,t6,cnt,tot;

 char typ[]; long long sum;

 struct a

 {

     long long mat[][];

     void Clean()

     {

         memset(mat,,sizeof mat);

     }

 }seg[*N],tre[N];

 a Matime(a x,a y)

 {

     a ret; ret.Clean();

     for(int i=;i<;i++)

         for(int j=;j<;j++)

             for(int k=;k<;k++)

                 ret.mat[i][j]=max(ret.mat[i][j],x.mat[i][k]+y.mat[k][j]);

     return ret;

 }

 void Link(int f,int t)

 {

     noww[++cnt]=p[f];

     goal[cnt]=t,p[f]=cnt;

     noww[++cnt]=p[t];

     goal[cnt]=f,p[t]=cnt;

 }

 void DFS(int nde,int fth)

 {

     int tmp=;

     siz[nde]=,far[nde]=fth;

     for(int i=p[nde];i;i=noww[i])

         if(goal[i]!=fth)

         {

             DFS(goal[i],nde);

             siz[nde]+=siz[goal[i]];

             if(siz[goal[i]]>tmp)

                 tmp=siz[goal[i]],imp[nde]=goal[i];

         }

 }

 void Mark(int nde,int tpp)

 {

     dfn[nde]=++tot,top[nde]=tpp;

     if(imp[nde])

     {

         Mark(imp[nde],tpp);

         for(int i=p[nde];i;i=noww[i])

             if(goal[i]!=imp[nde]&&goal[i]!=far[nde])

                 Mark(goal[i],goal[i]);

     }

     lst[nde]=imp[nde]?lst[imp[nde]]:nde;

 }

 a Query(int nde,int l,int r,int ll,int rr)

 {

     if(l>=ll&&r<=rr)

         return seg[nde];

     else

     {

         int mid=(l+r)/,ls=*nde,rs=*nde+;

         if(mid>=ll&&mid<rr)

             return Matime(Query(rs,mid+,r,ll,rr),Query(ls,l,mid,ll,rr));

         if(mid>=rr) return Query(ls,l,mid,ll,rr);

         if(mid<ll) return Query(rs,mid+,r,ll,rr);

     }

 }

 void Modify(int nde,int l,int r,int pos,a tsk)

 {

     if(l==r) seg[nde]=tsk;

     else

     {

         int mid=(l+r)/,ls=*nde,rs=*nde+;

         if(pos<=mid) Modify(ls,l,mid,pos,tsk);

         else Modify(rs,mid+,r,pos,tsk);

         seg[nde]=Matime(seg[rs],seg[ls]);

     }

 }

 void Prework(int nde)

 {

     stack<int> st;

     for(int i=nde;i;i=imp[i]) st.push(i);

     while(!st.empty())

     {

         int tn=st.top(); st.pop();

         long long x=,y=val[tn];

         for(int i=p[tn];i;i=noww[i])

             if(goal[i]!=imp[tn]&&goal[i]!=far[tn])

             {

                 Prework(goal[i]); a mtr=tre[goal[i]];

                 x+=max(mtr.mat[][],mtr.mat[][]),y+=mtr.mat[][];

             }

         a tmp; tmp.mat[][]=tmp.mat[][]=x,tmp.mat[][]=y,tmp.mat[][]=-inf;

         Modify(,,n,dfn[tn],tmp);

     }

     tre[nde]=Query(,,n,dfn[nde],dfn[lst[nde]]);

 }

 void Change(int nde,long long tsk)

 {

     a tmp=Query(,,n,dfn[nde],dfn[nde]);

     tmp.mat[][]+=tsk-val[nde];

     Modify(,,n,dfn[nde],tmp),val[nde]=tsk;

     for(int i=top[nde];i!=;i=top[i])

     {

         int fa=far[i];

         a tmp=Query(,,n,dfn[fa],dfn[fa]),tep=Query(,,n,dfn[i],dfn[lst[i]]);

         tmp.mat[][]+=max(tep.mat[][],tep.mat[][])-max(tre[i].mat[][],tre[i].mat[][]);

         tmp.mat[][]+=tep.mat[][]-tre[i].mat[][],tmp.mat[][]=tmp.mat[][];

         Modify(,,n,dfn[fa],tmp),tre[i]=tep,i=fa;

     }

 }

 int main()

 {

     scanf("%d%d%s",&n,&m,typ);

     for(int i=;i<=n;i++)

         scanf("%d",&val[i]),sum+=val[i];

     for(int i=;i<n;i++)

         scanf("%d%d",&t1,&t2),Link(t1,t2);

     DFS(,),Mark(,),Prework();

     while(m--)

     {

         scanf("%d%d%d%d",&t1,&t2,&t3,&t4);

         if(!t2&&!t4&&(far[t1]==t3||far[t3]==t1))

             printf("-1\n");

         else

         {

             t5=val[t1],t6=val[t3];

             Change(t1,t2?-inf:inf);

             Change(t3,t4?-inf:inf);

             a qry=Query(,,n,,dfn[lst[]]);

             long long ans=sum-max(qry.mat[][],qry.mat[][]);

             printf("%lld\n",ans+(inf-t5)*(t2^)+(inf-t6)*(t4^));

             Change(t1,t5),Change(t3,t6);

         }

     }

     return ;

 }