#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_) for(int V_=(A_), V_##_END=(B_); V_>=V_##_END; V_--)
#ifdef _WIN32
#define long __int64
#endif
#if defined(_LOCAL_)
#undef assert
#define assert(expr) ({ if(!(expr)) asm("int3"); 0; })
#endif
using namespace std;
const long MOD=1092515507;
int n,qn;
struct X{ long val,cnt; };
X operator*(X x,X y){ return !x.cnt||!y.cnt?X{0,0}:X{x.val+y.val,x.cnt*y.cnt%MOD}; }
X operator+(X x,X y){ return x.val>y.val ? x : x.val<y.val ? y : X{x.val,(x.cnt+y.cnt)%MOD}; }
struct Mat{
    X A[100][100];
};
struct Vec{ X A[100]; };
Mat operator*(const Mat& x,const Mat& y){
    Mat z; memset(&z,0,sizeof(z));
    RNG(k,0,99){
        RNG(i,0,99){
            RNG(j,0,99) z.A[i][j]=z.A[i][j]+x.A[i][k]*y.A[k][j];
        }
    }
    return z;
}
Vec operator*(const Vec& x,const Mat& y){
    Vec z; memset(&z,0,sizeof(z));
    RNG(j,0,99){
        RNG(i,0,99) z.A[j]=z.A[j]+x.A[i]*y.A[i][j];
    }
    return z;
}
struct{ int w; long v; } A[110];
X F[110];
Mat B,Bp[30];
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
#else
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>qn;
    RNG(i,1,n) cin>>A[i].w;
    RNG(i,1,n) cin>>A[i].v;
    F[0]={0,1};
    RNG(w,1,100){
        RNG(i,1,n){
            if(A[i].w<=w) F[w]=F[w]+(F[w-A[i].w]*X{A[i].v,1});
        }
    }
    RNG(i,0,98) B.A[i][i+1]={0,1};
    RNG(i,1,n) B.A[A[i].w-1][99]=B.A[A[i].w-1][99]+X{A[i].v,1};
    Bp[0]=B;
    RNG(i,1,29) Bp[i]=Bp[i-1]*Bp[i-1];
    auto put_ans=[](X x){
        if(!x.cnt) cout<<"-1 -1\n";
        else cout<<x.val<<" "<<x.cnt<<"\n";
    };
    RNG(_,1,qn){
        int w; cin>>w;
        if(w<=99){ put_ans(F[w]); continue; }
        w-=99;
        Vec x; copy_n(F,100,x.A);
        RNG(i,0,29){
            if((w>>i)&1)
                x=x*Bp[i];
        }
        put_ans(x.A[99]);
    }
}