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;
//type
typedef long long ll;
#define pii pair<int, int>
#define vi vector<int>
//x * y * 1.0 can cause overflow
//constant
#define inf (int)(1e9+7)
#define mod (ll)(1e9+7)
#define eps 1e-10
//omission
#define eb emplace_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define all(v) v.begin(), v.end()
//manip
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define UNIQUE(v) v.erase(unique(v.begin(), v.end(), v.end());
#define ceil(a, b) a / b + !!(a % b)
template<class T> T power(T a, T b)
{return b ? power(a * a % inf, b / 2) * (b % 2 ? a : 1) % inf : 1;}
#define LB(v, x) (int)(lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (int)(upper_bound(v.begin(), v.end(), x) - v.begin())
//loop
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep3(i, st, n) for (int i = st; i < n; ++i)
//algorithm
//double pointer, l start, how many adds, can be 0 -> init r = l, sum = 0
//bfs, not x, y, i, j
//not !(i % 2), i % 2 == 0
//check sample again


bool zero(string a) {
    if (a[0] == '0' && SZ(a) >= 2) return 0;
    return 1;
}

int main() {
    //cast caution
    //look constraints always
    cin.tie(0); ios::sync_with_stdio(false);
    
    
    
    int N, Q; cin >> N >> Q;
    int a[N]; rep(i, N) {cin >> a[i]; a[i]--;}
    if (N == 1) {
        cout << a[0] + 1 << endl;
        return 0;
    }
    vector<pii> v(N);
    v[a[0]].F = -1;
    v[a[0]].S = a[1];
    v[a[N - 1]].S = -1;
    v[a[N - 1]].F = a[N - 2];
    rep3(i, 1, N - 1) {
        v[a[i]].F = a[i - 1];
        v[a[i]].S = a[i + 1];
    }
    
    //rep(i, N) cout << v[i].F << " " << v[i].S << endl;
    
    
    int lead = a[0], last = a[N - 1];
    
    rep(i, Q) {
        int q; cin >> q; q--;
        //a ... b c d ... e
        int a = lead; //af = v[a].F, as = v[a].S;
        int b = v[q].F; //bf = v[b].F, bs = v[b].S;
        int c = q; //cf = v[c].F, cs = v[c].S;
        int d = v[q].S; //df = v[d].F, ds = v[d].S;
        int e = last; //ef = v[e].F, es = v[e].S;
        
        //qが最後尾なら
        if (v[c].S == -1) {
            v[a].F = c;
            v[b].S = -1;
            v[c].S = a; v[c].F = -1;
            lead = c; last = b;
        } else if (v[c].F == -1) {
            v[c].F = e; v[c].S = -1;
            v[d].F = -1;
            v[e].S = c;
            lead = d; last = c;
        } else {
            v[a].F = c;
            v[b].S = -1;
            v[c].F = e; v[c].S = a;
            v[d].F = -1;
            v[e].S = c;
            lead = d; last = b;
        }
        
    }
    
    //rep(i, N) cout << v[i].F << " " << v[i].S << endl;
    
    //return 0;
    
    int now = lead;
    
    while (v[now].S != -1) {
        cout << now + 1 << " ";
        now = v[now].S;
        
    }
    cout << last + 1 << endl;
    
}

/*
 10^5個のqueryに答える
 毎回10^5個並び替えるわけにはいかない
 
 最小限何を変えたらいいか
 ある数で、手前と直後
 これは一部だけ変わる
 
 
 
 
 */