#include<bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
using pii = pair<int,int>;
const int inf = 2e9;
const int M = 1000004567;
const ld eps = 1e-9;
int n;
ll sum(vector <ll> &a){
    ll sum = 0;
    for(int i = 1; i <=n;i++){
        sum+=pow(a[i], i);
        if(sum >= M){
            sum-=M;
        }
    }
    return sum;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll q;
    cin >> n >> q;
    vector<ll> a(n+1, 0);
    for(int i =1; i <= n;i++){
        cin >> a[i];
    }
    while(q--){
        int z;
        cin >>z;
        vector<ll>qq(n+1);
        if(z == 1){
             for(int i = 1; i <= n;i++){
                qq[i] =  a[n-i+1];
             }
        }else if(z == 2){
            for(int i = 1; i <= n;i++){
                qq[i] =  n-a[i]+1;
             }
        }else{
            for(int i = 1; i <= n;i++){
                qq[a[i]] = i;
             }
        }
        cout << sum(qq) << " ";
        a = qq;
    }
}
