//if I only had one match left...
#include <bits/stdc++.h>
using namespace std;
#define MOD 18446744073709551616
int T,  //test point
    n,  //amount of people attending <=250000
    a[250010],  //1 <= XiaoN's team members' program design level <=n(250000)
    b[250010],  //1 <= XiaoO's team members' program design level <=n(250000)
    Q,          //time of matches <=250000
    l[250010],
    r[250010],
    jc=0;
bool possibleSelectionA[250010],
     possibleSelectionB[250010];
int main() {
    freopen("match.in", "r", stdin);    //Special A: a is 1~n #1-#9 #14-#21
    freopen("match.out", "w", stdout);  //Special B: b is 1~n #1-#9 #14-#17
    cin >> T >> n;              //Line 1 T marked test point #
    for(int i=1; i<=n; ++i) {   //Line 2
        cin >> a[i];
    }
    for(int i=1; i<=n; ++i) {   //Line 3
        cin >> b[i];
    }
    cin >> Q;                   //Line 4
    for(int i=1; i<=Q; ++i) {   //Line 5 - Line Q + 5
        cin >> l[i] >> r[i];
    }
    //Finish Inputting
    // for(int i=1; i<=Q; ++i) {
    //     int MaxA=0,
    //         MaxB=0;
    //     for(int j=l[i]; j<=r[i]; ++j) {
    //         if(a[j]>MaxA) MaxA=a[j];
    //         if(b[j]>MaxB) MaxB=b[j];
    //         cout << "[Debug] MaxA = " << MaxA << " MaxB = " << MaxB << endl;
    //     }
    //     jc += MaxA*MaxB;
    //     cout << "[Debug] jc=" << jc << endl;
        // jc %= pow(2,64);
    // }
    if((T==0 ||T==1 || T==2) && n <= 30) {
        for(int i=1; i<=Q; ++i) {//Once I mod this the program just refused to work ;( I guess I'll leave this untouched
            bool T1T2[31][31]={false};// I just need around 20 gigs of RAM to do 10^5*10^5 ;(
            // for(int a=1;a<=31;a++){
            //     for(int b=1;b<=31;b++) { 
            //         cout<<T1T2[a][b];
            //     }
            // }
            for(int j=l[i]; j<=r[i]; ++j) {
                for(int k=l[i]; k<=r[i]; ++k) {
                    if(!T1T2[j][k]) {//mark visited
                        T1T2[j][k] = true;
                        // cout << "[Debug] visited" << j << " " << k << endl;
                        int AMax=0, BMax=0;
                        for(int l=j; l<=k; ++l) {
                            if(a[l]>AMax) AMax=a[l];
                            if(b[l]>BMax) BMax=b[l];
                        }
                        jc+=AMax*BMax;
                    }
                }
            }
            cout<<jc<<endl;
            jc=0;
        }
        return 0;
    }
    // if((T==3 || T==4 || T==5) && n <= 3000) {//what eves
    //     for(int i=1; i<=Q; ++i) {
    //         bool T1T2[3010][3010]={false};// I just need around 20 gigs of RAM to do 10^5*10^5 ;(
    //         // for(int a=1;a<=31;a++){
    //         //     for(int b=1;b<=31;b++) { 
    //         //         cout<<T1T2[a][b];
    //         //     }
    //         // }
    //         for(int j=l[i]; j<=r[i]; ++j) {
    //             for(int k=l[i]; k<=r[i]; ++k) {
    //                 if(!T1T2[j][k]) {//mark visited
    //                     T1T2[j][k] = true;
    //                     // cout << "[Debug] visited" << j << " " << k << endl;
    //                     int AMax=0, BMax=0;
    //                     for(int l=j; l<=k; ++l) {
    //                         if(a[l]>AMax) AMax=a[l];
    //                         if(b[l]>BMax) BMax=b[l];
    //                     }
    //                     jc+=AMax*BMax;
    //                 }
    //             }
    //         }
    //         cout<<jc<<endl;
    //         jc=0;
    //     }
    //     return 0;
    // }
    // for(int i=1; i<=Q; ++i) {
    //     for(int j=l[i]; j<=r[i]; ++j) {
    //         for(int k=j; k<=j+(r[i]-l[i]); ++k) {
    //             jc += a[j]*b[k];
    //             // cout << "[Debug] jc+=" << a[j] << "*" << b[k] << "j=" << j << "k=" << k << endl;
    //         }
    //     }
    //     cout << jc << endl;
    //     jc=0;
    // }
    return 0;
}
//at least 8 pts