Battle_Of_Bests_Soln

    #include<bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp> // Common file
    #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
    #define ff first
    #define ss second
    #define pb push_back
    #define pf push_front
    #define eb emplace_back
    #define emp emplace
    #define ins insert
    #define mp make_pair
    #define mt make_tuple
    #define sz(s) (int)s.size()
    #define forp(i,a,b) for( int i=a;i<=b;i++)
    #define rep(i,n)    for( int i=0;i<n;i++)
    #define ren(i,n)    for( int i=n-1;i>=0;i--)
    #define forn(i,a,b) for( int i=a;i>=b;i--)
    #define w(t) while(t)
    #define on cout<<"\n"
    #define os cout <<" "
    #define o2(a,b) cout<<a<<" "<<b
    #define o(a) cout << a
    #define bitcount __builtin_popcount
    #define gcd __gcd
    #define all(v) v.begin(),v.end()
    #define mem(n,m) memset(n,m,sizeof(n))
    #define pii pair<int,int>
    #define tiii tuple<int, int, int>
    #define pll pair<long long,long long>
    #define sii set<int>
    #define sll set<long long>
    #define vii vector<int>
    #define vll vector<long long>
    #define mii map<int,int>
    #define mll map<long long, long long>
    #define lob lower_bound
    #define upb upper_bound
    #define ret return
    #define present(s,x) (s.find(x) != s.end())
    #define cpresent(s,x) (find(all(s),x) != s.end())
    #define ford(container, it) for(auto it = container.begin(); it != container.end(); it++)
    #define fors(container, it, a, b) for(auto it = a; it != b; it++)
    using namespace __gnu_pbds;
    #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #define MOD 1000000007
    #define EPSILON 1e-9
    #define PI acos(-1)
    #define inf 1e18
    #define siz 100005
    #define SIZ 1000005
    #define SIZE 200005
    #define int long long
    #define debug(a) cerr<<#a<<": ";for(auto i:a)cerr<<i<<" ";cerr<<'\n';
    #define trace(a) cerr<<#a<<": "<<a<<"\n"
    #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>


    typedef long long  ll;
    typedef long double  ldo;
    typedef double  db ;
    using namespace std;
    auto start = std::chrono::system_clock::now();
    inline void skj()
    {
      std::chrono::time_point<std::chrono::system_clock> end;
      end = std::chrono::system_clock::now();
      std::chrono::duration<double> elapsed_seconds = end - start;
      std::time_t end_time = std::chrono::system_clock::to_time_t(end);
      cerr<<"Time taken " << elapsed_seconds.count()*1000<<"\n";
    }

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    //uniform_int_distribution<int> ud(1, 100); use this for random number generator

        //custom hash for unordered map
    struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
            // http://xorshift.di.unimi.it/splitmix64.c
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };
    inline int binexp(int a,int b,int m)
    {
        int res=1;
        a%=m;
        while(b)
        {
            if(b&1)
                res=(res*1ll*a)%m;
            a=(a*1ll*a)%m;
            b>>=1;
        }
        return res;
    }
    const ll is_query = -(1LL<<62);
    struct Line {
        ll m, b;
        mutable function<const Line*()> succ;
        bool operator<(const Line& rhs) const {
            if (rhs.b != is_query) return m < rhs.m;
            const Line* s = succ();
            if (!s) return 0;
            ll x = rhs.m;
            return b - s->b < (s->m - m + 0.0) * x;
        }
    };
    struct HullDynamic : public multiset<Line> { // will maintain upper hull for maximum
        bool bad(iterator y) {
            auto z = next(y);
            if (y == begin()) {
                if (z == end()) return 0;
                return y->m == z->m && y->b <= z->b;
            }
            auto x = prev(y);
            if (z == end()) return y->m == x->m && y->b <= x->b;
            return (x->b - y->b)*1.0*(z->m - y->m) >= (y->b - z->b)*1.0*(y->m - x->m);
        }
        void insert_line(ll m, ll b) {
            auto y = insert({ m, b });
            y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
            if (bad(y)) { erase(y); return; }
            while (next(y) != end() && bad(next(y))) erase(next(y));
            while (y != begin() && bad(prev(y))) erase(prev(y));
        }
        ll eval(ll x) {
            auto l = *lower_bound((Line) { x, is_query });
            return l.m * x + l.b;
        }
    };
    const int N = 1e4+5, M = 15;
    HullDynamic seg[4 * N][M];
    int expr[N][M], rel[N][M];
    inline void build(int i, int pos, int s, int e) {
        if(s == e) {
            seg[i][pos].insert_line(rel[s][pos], expr[s][pos]);
        }
        else {
            int mid = (s + e) >> 1, p = i << 1, q = p | 1;
            build(p, pos, s, mid);
            build(q, pos, mid + 1, e);
            forp(j, s, e) {
                seg[i][pos].insert_line(rel[j][pos], expr[j][pos]);
            }
        }
    }
    inline void update(int i, int pos, int s, int e, int ind) {
        if(s == e) {
            seg[i][pos].insert_line(rel[s][pos], expr[s][pos]);
        }
        else {
            int mid = (s + e) >> 1, p = i << 1, q = p | 1;
            if(ind <= mid) {
                update(p, pos, s, mid, ind);
            }
            else {
                update(q, pos, mid + 1, e, ind);
            }
            seg[i][pos].insert_line(rel[ind][pos], expr[ind][pos]);
        }
    }
    inline int query(int i, int pos, int s, int e, int l, int r, int x) {
        if(s > r || e < l) {
            ret 0;
        }
        if(s >= l && e <= r) {
            ret seg[i][pos].eval(x);
        }
        int mid = (s + e) >> 1, p = i << 1, q = p | 1;
        ret max(query(p, pos, s, mid, l, r, x), query(q, pos, mid + 1, e, l, r, x));
    }
    inline void solve_me_senpai() {
        int n, m, q;
        cin >> n >> m >> q;
        assert(1 <= n && n <= 1e4);
        assert(1 <= m && m <= 10);
        assert(1 <= q && q <= 1e5);
        forp(i, 1, n) {
            forp(j, 1, m) {
                cin >> rel[i][j];
                assert(1 <= rel[i][j] && rel[i][j] <= 1e6);
            }
        }
        forp(i, 1, n) {
            forp(j, 1, m) {
                cin >> expr[i][j];
                assert(1 <= expr[i][j] && expr[i][j] <= 1e6);
            }
        }
        forp(i, 1, m) {
            build(1, i, 1, n);
        }
        int c = 0;
        w(q--) {
            int t;
            cin >> t;
            if(t == 1) {
                int i, p, x;
                cin >> i >> p >> x;
                expr[i][p] += x;
                assert(1 <= i && i <= n);
                assert(1 <= p && p <= m);
                assert(1 <= x && x <= 1e6);
                update(1, p, 1, n, i);
            }
            else {
                int l, r, p, x;
                cin >> l >> r >> p >> x;
                assert(l <= r);
                assert(1 <= l);
                assert(r <= n);
                assert(1 <= p &&  p <= m);
                assert(1 <= x && x <= 1e6);
                o2(query(1, p, 1, n, l, r, x), "\n");
                c++;
            }
        }
        assert(c > 0);
    }

    signed main()
    {
        boost
        #ifndef ONLINE_JUDGE
        freopen("input.txt", "r",stdin);
        freopen("ot.txt", "w", stdout);
        #endif
        int t = 1;
        //cin >> t;
        //int a = 1;
        while(t--) {
          //  cout << "Case #" << a  << ": ";
            solve_me_senpai();
            //a++;
        }
        skj();
        return 0;
    }