#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

vec<int> mult(vec<int>& A,vec<int>& B){
    vec<int> C(A.size());
    for(int i=0;i<A.size();i++) C[i] = B[A[i]];
    return C;
}

vec<int> pow(vec<int>& A,ll n){
    if(n==1) return A;
    vec<int> R = pow(A,n>>1);
    R = mult(R,R);
    if(n&1) R = mult(A,R);
    return R;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vec<int> X(N);
    vec<int> D(N-1);
    for(int i=0;i<N;i++){
        cin >> X[i];
        if(i) D[i-1] = X[i]-X[i-1];
    }
    vec<int> perm(N-1);
    iota(perm.begin(),perm.end(),0);
    int M;
    ll K;
    cin >> M >> K;
    for(int i=0;i<M;i++){
        int a;
        cin >> a;
        a -= 2;
        swap(perm[a],perm[a+1]);
    }
    auto res = pow(perm,K);
    ll s = X[0];
    for(int i=0;i<N;i++){
        cout << s << "\n";
        if(i!=N-1) s += D[res[i]];
    }
}
#include <bits/stdc++.h>
using namespace std;

int MAX_N=262144*2;
vector<int64_t> seg(MAX_N*2-1);
int64_t qu(int a,int b,int k,int l, int r){
  if(r<=a||b<=l){
    return 0;
  }
  else if(a<=l&&r<=b){
    return seg[k];
  }
  else{
    int64_t X=qu(a,b,k*2+1,l,(l+r)/2);
    int64_t Y=qu(a,b,k*2+2,(l+r)/2,r);
    return X+Y;
  }
}
void pu(int64_t a,int b){
  int D=MAX_N-1+b;
  while(D>0){
    seg[D]+=a;
    D--;
    D/=2;
  }
  seg[0]+=a;
}

int main() {
  int N,Q;
  cin>>N>>Q;
  vector<int> p(N);
  for(int i=0;i<N;i++){
    cin>>p[i];
    p[i]--;
  }
  vector<tuple<int,int,int>> q(Q);
  for(int i=0;i<Q;i++){
    int a,b;
    cin>>a>>b;
    q[i]=make_tuple(b,a,i);
  }
  sort(q.begin(),q.end());
  vector<int> la(N,-1);
  vector<int> an(Q);
  int W=0;
  for(int i=0;i<Q;i++){
    int a,b,c;
    tie(a,b,c)=q[i];
    while(W<a){
      if(la[p[W]]!=-1){
        pu(-1,la[p[W]]);
      }
      la[p[W]]=W;
      pu(1,W);
      W++;
    }
    an[c]=qu(b-1,a,0,0,MAX_N);
  }
  for(int i=0;i<Q;i++){
    cout<<an[i]<<endl;
  }
}