Problem: B: Pivots

problem

Given a permutation of length N, a_1, a_2, ..., a_N, which is a permutation of integers from 1 to N. Also, Q queries are given in order for this permutation. In the i-th query, you have to do the following:

* The value q_i (1 \ leq q_i \ leq N) is given. In the permutation \\ {a_1, a_2, ..., a_N \\}, where L is the permutation on the left side of q_i and R is the permutation on the right side of q_i, the original permutation L \\ q_i \\ R is R \\ Change to q_i \\ L. That is, when q_ {i} = a_j, the permutations \\ {a_1, ..., a_ {j-1}, a_j, a_ {j + 1}, ..., a_N \\} are \\ { Change to a_ {j + 1}, ..., a_N, a_j, a_1, ..., a_ {j-1} \\}.



The permutations L and R may be empty. For example, if L is empty, change q_i \\ R to R \\ q_i. The same is true when R is empty.

Output the permutation after processing these Q queries in order for the given permutation on one line.

Input format


N Q
a_1 a_2 ... a_N
q_1 q_2 ... q_Q


All inputs are integers.

The first row gives the number of elements in the permutation N and the number of queries Q, separated by blanks. In the second line, permutations a_1, a_2, ..., a_N, in which integers from 1 to N are rearranged, are given separated by blanks. The third line gives Q queries, separated by blanks. q_i represents the i-th query.

Constraint

* 1 \ leq N \ leq 10 ^ 5
* 1 \ leq Q \ leq 10 ^ 5
* 1 \ leq a_i \ leq N
* a_i is different
* 1 \ leq q_i \ leq N



Output format

Output the permutation after processing all the queries in order on one line.

Input example 1


5 2
1 5 3 2 4
5 2


Output example 1


4 5 1 2 3

* The first query changes the permutation to \\ {3, 2, 4, 5, 1 \\}.
* The second query changes the permutation to \\ {4, 5, 1, 2, 3 \\}.



Input example 2


5 1
1 2 3 4 5
Five


Output example 2


5 1 2 3 4





Example

Input

5 2
1 5 3 2 4
5 2


Output

4 5 1 2 3

Solution (in CPP):

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


#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)

int n,q;
int a[125252];

int bef[125252], aft[125252];

int main(){
  scanf("%d%d",&n,&q);
  REP(i,n)scanf("%d",a+i),a[i]--;
  if(n==1){
    printf("%d\n",a[0]+1);
    return 0;
  }
  REP(i,n)bef[i] = aft[i] = -1;
  REP(i,n-1){
    int x = a[i];
    int y = a[i+1];
    aft[x] = y;
    bef[y] = x;
  }
  int headval = a[0];
  int tailval = a[n-1];
  while(q--){
    int x;
    scanf("%d",&x);
    x--;
    if(headval == x){
      // [head=x] / [nxt, ..., tail]
      // -> [nxt, ..., tail] - [x]
      int nxt = aft[x];
      aft[x] = bef[nxt] = -1;
      aft[tailval] = x;
      bef[x] = tailval;
      headval = nxt;
      tailval = x;
    }else if(tailval == x){
      // [head, ..., bef] / [tail=x]
      // -> [x] - [head, ..., bef]
      int prv = bef[x];
      bef[x] = aft[prv] = -1;
      bef[headval] = x;
      aft[x] = headval;
      headval = x;
      tailval = prv;
    }else{
      // [head, ..., s] / [x] / [t, ..., tail]
      // -> [t, ..., tail] - [x] - [head, ..., s]
      int s = bef[x];
      int t = aft[x];
      bef[x] = aft[s] = -1;
      aft[x] = bef[t] = -1;
      aft[tailval] = x;
      bef[x] = tailval;
      bef[headval] = x;
      aft[x] = headval;
      headval = t;
      tailval = s;
    }
  }
  int cur = headval;
  REP(i,n){
    printf("%d%c",cur+1,i==n-1?'\n':' ');
    cur = aft[cur];
  }
  return 0;
}