1 から N までの整数を並び変えた、長さ N の順列 a_1, a_2, ..., a_N が与えられる。 また、この順列に対して Q 個のクエリが順に与えられる。i 番目のクエリでは次の操作をしなければならない。
なお、順列 L, R は空になることもあり得る。例えば L が空の時は、q_i \ \ R を R \ \ q_i に変更する。R が空のときについても同様である。
与えられた順列に対してこれら Q 個のクエリを順に処理した後の順列を一行に出力せよ。
N Q a_1 a_2 ... a_N q_1 q_2 ... q_Q
入力は全て整数である。
一行目には順列の要素数 N とクエリの回数 Q が空白区切りで与えられる。 二行目には 1 から N までの整数を並び変えた順列 a_1, a_2, ..., a_N が空白区切りで与えられる。 三行目にはクエリが Q 個、空白区切りで与えられる。q_i は i 番目のクエリを表す。
クエリを順にすべて処理した後の順列を一行に出力せよ。
5 2 1 5 3 2 4 5 2
4 5 1 2 3
5 1 1 2 3 4 5 5
5 1 2 3 4