pratos.cpp

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int mod=1000000007;

bool comp(pair<int,int> a, pair<int,int> b){
    return a.first*b.second+a.second<b.first*a.second+b.second;
}

int fast_exp(int base, int exp){
    if(exp==0)return 1;
    if(exp==1)return base;

    int aux=fast_exp(base, exp/2);
    aux=(aux*aux)%mod;
    if(exp&1)aux=(aux*base)%mod;

    return aux;
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int,int>> feiticos(n);

    for(int i=0; i<n; i++){
        cin >> feiticos[i].first;
    }

    for(int i=0; i<n; i++){
        cin >> feiticos[i].second;
    }

    vector<pair<int,int>> refeicoes(m);

    for(int i=0; i<m; i++){
        cin >> refeicoes[i].first;
    }

    for(int i=0; i<m; i++){
        cin >> refeicoes[i].second;
    }

    sort(feiticos.begin(), feiticos.end());
    sort(refeicoes.begin(), refeicoes.end(), comp);

    int prod=1, soma=0;
    for(auto x:refeicoes){
        prod=(prod*x.first)%mod;
        soma=(soma*x.first+x.second)%mod;
    }

    vector<pair<int,pair<int,int>>> limiar;

    limiar.push_back({0, feiticos[0]});

    for(int i=1; i<n; i++){
        int mn=0;
        while(limiar.size()){
            int a1=(limiar.back().second.second-feiticos[i].second+feiticos[i].first-limiar.back().second.first-1), a2=(feiticos[i].first-limiar.back().second.first);
            if(a2==0){
                limiar.pop_back();
                continue;
            }
            mn=a1/a2;
            if(mn<=limiar.back().first)limiar.pop_back();
            else break;
        }
        limiar.push_back({mn, feiticos[i]});
    }

    vector<pair<int,int>> pot2(30);
    pot2[0]=feiticos.back();
    for(int i=1; i<30; i++){
        int a=pot2[i-1].first, b=pot2[i-1].second;
        pot2[i]=make_pair((a*a)%mod, (a*b+b)%mod);
    }

    int q;
    cin >> q;

    while(q--){
        int val;
        cin >> val;

        int qtd=k;

        while(qtd>0){
            qtd--;
            auto ptr=upper_bound(limiar.begin(), limiar.end(), make_pair(val, make_pair(mod, mod)));
            ptr--;
            int melhor=ptr-limiar.begin();
            val%=mod;
            val=(val*limiar[melhor].second.first+limiar[melhor].second.second);
            if(melhor==limiar.size()-1)break;
        }
        val%=mod;

        for(int i=0; i<30; i++){
            if(qtd&(1<<i)){
                val=(pot2[i].first*val+pot2[i].second)%mod;
            }
        }
        val=(prod*val+soma)%mod;

        cout << val << '\n';
    }

    return 0;
}