// 那就是希望。
// 即便需要取模，也是光明。

// 线段树大科技题。
// 自己 yy 出来一个奇葩做法，使得构成一个可以维护的非半群信息。
// 但是修改代价太大了。
// 考虑怎么办。
// 考虑嗯做。
// 直接，直接扔一个底层分块上去啊！
// 很快啊！
// 希望能暴力草过。
// bruteforce!
// 我感觉我很有精神！

// 写得我直接 /tuu 了

#include <algorithm>
#include <set>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
ullt V[200005];uint Pre[200005];
ullt S(uint l,uint r){return V[r]-V[l];}
ullt A(uint p){return S(p,p+1);}
ullt T(uint l,uint r){return S(Pre[r],l+1);}
ullt W(uint l){return T(l,l+1);}
struct Info{ullt F,G,H;};
const uint B=100;
typedef std::pair<llt,llt>Pair;
typedef std::pair<llt,Pair>Pair2;
const llt inf=1e18;
std::vector<Pair2>Merge(std::vector<Pair2>L1,std::vector<Pair2>L2){
    std::vector<Pair2>Line;
    std::vector<llt>X,User1,User2;
    for(auto s:L1)User1.push_back(s.first);
    for(auto s:L2)User2.push_back(s.first);
    X.resize(User1.size()+User2.size());
    std::merge(User1.begin(),User1.end(),User2.begin(),User2.end(),X.begin());
    X.erase(std::unique(X.begin(),X.end()),X.end());
    std::vector<Pair2>R;
    for(uint i=0,j=0;i<X.size();i++){
        while(j+1<L1.size()&&L1[j+1].first<=X[i])j++;
        R.push_back({X[i],L1[j].second});
    }
    L1=R;R.clear();
    for(uint i=0,j=0;i<X.size();i++){
        while(j+1<L2.size()&&L2[j+1].first<=X[i])j++;
        R.push_back({X[i],L2[j].second});
    }
    L2=R;R.clear();
    for(uint i=0;i<X.size();i++)
    {
        Pair l1=L1[i].second,l2=L2[i].second;
        if(l1.first==l2.first)R.push_back({X[i],std::max(l1,l2)});
        else{
            if(l1>l2)std::swap(l1,l2);
            llt p=l1.second-l2.second;
            if(p<=X[i])R.push_back({X[i],l2});
            else if(i+1<X.size()&&X[i+1]>=p)R.push_back({X[i],l1});
            else R.push_back({X[i],l1}),R.push_back({p,l2});
        }
    }
    for(uint i=0;i<R.size();i++)if(!i||R[i].second!=R[i-1].second)Line.push_back(R[i]);
    return Line;
}
struct Seg{
    Seg*L,*R;uint len,from;ullt H;
    std::vector<Pair2>Line;
    voi buildLine(){
        if(len==1)Line={{0,{1,A(from)}},{W(from)-A(from),{0,W(from)}}};
        else{
            std::vector<ullt>H={L->H};
            for(uint r=from+(len>>1);r<from+len;r++)
                H.push_back(std::min(H.back()+A(r),W(r)));
            Line=L->Line;
            for(uint i=1;i<H.size();i++)
                Line=Merge(Line,{{0,{1,S(from+(len>>1),from+(len>>1)+i)}},
                        {H[i]-S(from+(len>>1),from+(len>>1)+i),{0,H[i]}}});
        }
    }
    Seg(uint l,uint r):L(NULL),R(NULL),len(r-l),from(l){
        if(len>1)
            L=new Seg(l,(l+r)>>1),R=new Seg((l+r)>>1,r),
            H=std::min(L->H+S((l+r)>>1,r),R->H);
        else H=W(l);
        if(len<=B)buildLine();
    }
    Info query(uint l,uint r,ullt v){
        if(!l&&r==len&&len<=B){
            auto p=std::upper_bound(Line.begin(),Line.end(),Pair2{v,{inf,inf}})[-1].second;
            return{std::min(S(from,from+len)+v,H),p.first*v+p.second,H};
        }
        if(l<(len>>1))
            if(r<=(len>>1))return L->query(l,r,v);
            else{
                Info t1=L->query(l,len>>1,v);
                Info t2=R->query(0,r-(len>>1),t1.F);
                return{std::min({v+S(from+l,from+r),t1.H+S(from+(len>>1),from+r),t2.H}),
                            std::max(t1.G,t2.G),std::min(t1.H+S(from+(len>>1),from+r),t2.H)};
            }
        else return R->query(l-(len>>1),r-(len>>1),v);
    }
    voi update(uint p){
        if(len==1)H=W(from);
        else
            p<(len>>1)?L->update(p):R->update(p),
            H=std::min(L->H+S(from+(len>>1),from+len),R->H);
        if(len<=B)buildLine();
    }
};
std::set<uint>Set[200005];
uint C[200005];
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#else
#if !defined(ONLINE_JUDGE)
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
#endif
    uint n,m,q;scanf("%u%u%u",&n,&m,&q);
    for(uint i=0;i<n;i++)scanf("%llu",V+i+1),V[i+1]+=V[i];
    for(uint i=0;i<m;i++)Set[i].insert(0);
    for(uint i=0;i<n;i++)scanf("%u",C+i),Pre[i]=*--Set[--C[i]].insert(i+1).first;
    Seg S(0,n);
    while(q--){
        uint op;scanf("%u",&op);
        if(op==1){
            uint l,r;scanf("%u%u",&l,&r);
            printf("%llu\n",S.query(l-1,r,0).G);
        }else{
            uint p;scanf("%u",&p),p--;
            Set[C[p]].erase(p+1);
            auto t=Set[C[p]].upper_bound(p);
            if(t!=Set[C[p]].end())Pre[*t]=Pre[p],S.update(*t);
            scanf("%u",C+p);
            t=Set[--C[p]].insert(p+1).first;
            if(++t!=Set[C[p]].end())Pre[*t]=p,S.update(*t);
            --t;Pre[p]=*--t;S.update(p);
        }
    }
    return 0;
}

// 那就是希望。
// 即便需要取模，也是光明。