// what is matter? never mind.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
//#define ll __int128
//#define ull unsigned long long
#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 500005
#define inf 0x3f3f3f3f3f3f3f3f
int n,m;
vi e[maxn];
namespace TT{
vi e[maxn],g[maxn],dom[maxn];
int fa[maxn],dfn[maxn],que[maxn],idx;
void adde(int u,int v){e[u].pb(v);}
void dfs(int u){
que[dfn[u]=++idx]=u;
for(int v:e[u]){
if(!dfn[v])dfs(v),fa[dfn[v]]=dfn[u];
g[dfn[v]].pb(dfn[u]);
}
}
int p[maxn],mn[maxn],sdom[maxn],idom[maxn];
int get(int u){
if(p[u]!=p[p[u]]){
if(sdom[mn[u]]>sdom[get(p[u])])mn[u]=get(p[u]);
p[u]=p[p[u]];
}return mn[u];
}
void solve()
{
cout<<"solve"<<endl;
For(i,1,n)p[i]=mn[i]=sdom[i]=i;
dfs(1);
Rep(i,n,2){
for(int j:g[i])sdom[i]=min(sdom[i],sdom[get(j)]);
dom[sdom[i]].pb(i);
int x=p[i]=fa[i];
for(int j:dom[x])idom[j]=(sdom[get(j)]<x?get(j):x);
dom[x].clear();
}
For(i,2,n){
if(idom[i]!=sdom[i])idom[i]=idom[idom[i]];
cout<<"ADD "<<que[idom[i]]<<' '<<que[i]<<endl;
::e[que[idom[i]]].pb(que[i]);
}
cout<<"qwq"<<endl;
}
void init(){
For(i,1,n) e[i].clear(),g[i].clear(),dom[i].clear(),fa[i]=dfn[i]=que[i]=p[i]=mn[i]=sdom[i]=idom[i]=0; idx=0;
For(i,1,m){
int u=read(),v=read();
cout<<"edge "<<u<<" "<<v<<endl;
e[v].pb(u);
}
solve();
}
}
int fa[maxn],son[maxn],sz[maxn],dep[maxn];
int dfn[maxn],out[maxn],top[maxn],que[maxn],idx;
void dfs1(int u){
sz[u]=1;
for(auto v:e[u]){
if(v==fa[u])continue;
fa[v]=u,dep[v]=dep[u]+1,dfs1(v),sz[u]+=sz[v];
if(sz[v]>sz[son[u]])son[u]=v;
}
}
void dfs2(int u,int tp){
top[u]=tp,dfn[u]=++idx,que[idx]=u;
if(son[u])dfs2(son[u],tp);
for(auto v:e[u])if(v!=fa[u]&&v!=son[u])dfs2(v,v);
out[u]=idx;
}
int lca(int u,int v){
for(;top[u]!=top[v];u=fa[top[u]])if(dep[top[u]]<dep[top[v]])swap(u,v);
return dep[u]<dep[v]?u:v;
}
int kth(int u,int k){
while(k>=dfn[u]-dfn[top[u]]+1&&dfn[u]!=1)
k-=dfn[u]-dfn[top[u]]+1,u=fa[top[u]];
return que[dfn[u]-k];
}
int jump(int u,int v){
for(;top[u]!=top[v];u=fa[top[u]])
if(fa[top[u]]==v)return top[u];
return son[v];
}
/*
weihu g[i]=f[i]-c[i]
qmin g[i]+c[i]
g[i]=min(g[i],X)
g[i] range add
*/
struct info{
int mx,cmx;
int mx2,cmx2;
info (){
mx=-inf;cmx=inf;
mx2=-inf;cmx2=inf;
}
};
struct oper{
int add,addmx;
oper (){
add=addmx=0;
}
};
info operator +(info a,info b){
info c;
c.mx=max(a.mx,b.mx);
c.mx2=max((a.mx==c.mx?a.mx2:a.mx),(b.mx==c.mx?b.mx2:b.mx));
c.cmx2=min((a.mx==c.mx?a.cmx2:a.cmx),(b.mx==c.mx?b.cmx2:b.cmx));
c.cmx=inf;
if(a.mx==c.mx) c.cmx=min(c.cmx,a.cmx);
if(b.mx==c.mx) c.cmx=min(c.cmx,b.cmx);
return c;
}
void operator +=(oper &a,oper b){
a.add+=b.add;
a.addmx+=b.addmx;
}
void app(info &a,oper b,bool is){
if(is){
a.mx+=b.add+b.addmx;
a.cmx+=b.add+b.addmx;
}else{
a.mx+=b.add;
a.cmx+=b.add;
}
a.mx2+=b.add;
a.cmx2+=b.add;
}
template<class info,class oper>
struct segt{
int n;
vector<info>tr;
vector<oper>tag;
void init(vector<info>a){
n=a.size(); assert(n);
tr.assign(4<<__lg(n),info());
tag.assign(4<<__lg(n),oper());
function<void(int,int,int)>build=[&](int p,int l,int r){
if(l==r)return tr[p]=a[l],void();
int mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r),up(p);
};
build(1,0,n-1);
}
void init(int _n){
n=_n; assert(n);
tr.assign(4<<__lg(n),info());
tag.assign(4<<__lg(n),oper());
}
void up(int p){
tr[p]=tr[p<<1]+tr[p<<1|1];
}
void pt(int p,oper v){
tag[p]+=v;
app(tr[p],v,1);
//tr[p]+=v;
}
void down(int p){
tag[p<<1]+=tag[p];
tag[p<<1|1]+=tag[p];
app(p<<1,tag[p],(tr[p<<1].mx==tr[p].mx));
app(p<<1|1,tag[p],(tr[p<<1|1].mx==tr[p].mx));
tag[p]=oper();
}
void upd(int p,int l,int r,int x,info y){
if(l==r)return tr[p]=y,void();
int mid=l+r>>1; down(p);
if(x<=mid)upd(p<<1,l,mid,x,y);
else upd(p<<1|1,mid+1,r,x,y); up(p);
}
// beats
void mdf(int p,int l,int r,int ql,int qr,int v){
// cout<<"mdf "<<p<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<v<<endl;
// cout<<"mx,mx2 "<<tr[p].mx<<" "<<tr[p].mx2<<endl;
// cout<<"cmx,cmx2 "<<tr[p].cmx<<" "<<tr[p].cmx2<<endl;
if(v>=tr[p].mx) return;
if(l>=ql&&r<=qr && v>tr[p].mx2) {
oper tmp;
tmp.addmx=v-tr[p].mx;
return pt(p,tmp);
}
int mid=l+r>>1; down(p);
if(ql<=mid)mdf(p<<1,l,mid,ql,qr,v);
if(qr>mid)mdf(p<<1|1,mid+1,r,ql,qr,v); up(p);
}
void mdf(int p,int l,int r,int ql,int qr,oper v){
if(l>=ql&&r<=qr)return pt(p,v);
int mid=l+r>>1; down(p);
if(ql<=mid)mdf(p<<1,l,mid,ql,qr,v);
if(qr>mid)mdf(p<<1|1,mid+1,r,ql,qr,v); up(p);
}
info ask(int p,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr)return tr[p];
int mid=l+r>>1; down(p);
if(qr<=mid)return ask(p<<1,l,mid,ql,qr);
if(ql>mid)return ask(p<<1|1,mid+1,r,ql,qr);
return ask(p<<1,l,mid,ql,qr)+ask(p<<1|1,mid+1,r,ql,qr);
}
void upd(int x,info y){
--x;
upd(1,0,n-1,x,y);
}
void mdf(int l,int r,oper y){
if(l>r)return;
cout<<"MDF "<<l<<" "<<r<<" "<<y.add<<endl;
--l,--r;
mdf(1,0,n-1,l,r,y);
}
info ask(int l,int r){
if(l>r)return info();
--l,--r;
return ask(1,0,n-1,l,r);
}
};
segt<info,oper> T;
int res[maxn];
int b[maxn],c[maxn],sumb[maxn],a[maxn],q;
/*
weihu g[i]=f[i]-c[i]
qmin g[i]+c[i]
g[i]=min(g[i],X)
g[i] range add
*/
void work()
{
n=read(),m=read(),q=read();
For(i,1,n) e[i].clear(),dfn[i]=fa[i]=top[i]=0; idx=0;
TT::init();
For(i,1,n) for(int v:e[i]) cout<<"tree "<<i<<" "<<v<<endl;
dfs1(1),dfs2(1,1);
For(i,1,n)c[i]=read();
For(i,1,q){
a[i]=read(),b[i]=read();
sumb[i]=sumb[i-1]+b[i];
}
vector<info>mys;
For(i,1,n) {
int u=que[i];
info t;
t.mx=0;
t.cmx=c[u];
mys.pb(t);
}
T.init(mys);
For(i,1,q+1){
int mns=inf;
mns=min(mns,T.tr[1].cmx);
mns=min(mns,T.tr[1].cmx2);
res[i-1]=mns;
cout<<"solve "<<i<<" "<<mns<<endl;
if(i==q+1) break;
T.mdf(1,0,n-1,0,n-1,mns);
oper ad; ad.add=c[i];
T.mdf(1,n,ad);
ad.add=-c[i];
int u=a[i];
while(u){
int t=top[u];
T.mdf(dfn[t],dfn[u],ad);
u=fa[top[u]];
}
For(j,1,n){
auto t=T.ask(j,j);
cout<<"j: "<<j<<"\n";
cout<<"mx,cmx "<<t.mx<<" "<<t.cmx<<"\n";
}
For(j,1,n){
auto t=T.ask(j,j);
cout<<"j: "<<j<<"\n";
cout<<"mx,cmx "<<t.mx<<" "<<t.cmx<<"\n";
}
}
For(i,1,q){
printf("%lld\n",res[i]);
}
}
signed main()
{
int T=read();
while(T--)work();
return 0;
}
/*
1
7 6 2
2 1
3 1
4 2
5 2
6 3
7 3
4 3 5 2 2 1 1
4 2
5 2
6 2
7 2
0 0 0 0 0 0 0
0 0 0 4 4 4 4
*/