Number Removal

Number Removal

Time limit: 1 s.
Memory limit: 256 MB

In a long hallway, there is a line of students represented by an array \(A\). Each student is holding a number.

A mischievous teacher comes in with a list of \(Q\) commands. Each command contains a number \(X\). Whenever the teacher calls out a number \(X\), the leftmost student holding that number quietly leaves the line. If no student is holding that number, nothing happens.

The teacher goes through all the commands one by one.

At the end, the remaining students stay in line, still in their original order.

Your task is to determine which students are left after all the teacher’s commands are completed.

Input

The first line contains two integers \(N\) and \(Q\). \((1 \le N, Q \le 2 \cdot 10^5)\)

The second line contains \(N\) integers \(A_1, A_2, ..., A_N\). \((1 \le A_i \le 10^9)\)

The third line contains \(Q\) integers \(X_1, X_2, ..., X_Q\). \((1 \le X_i \le 10^9)\)

Output

In a single print the remaining students in order from left to right.

Scoring

Group Constraints Points
\(1\) \(A_i = 1\) \(21\)
\(2\) \(1 \le N, Q \le 2 \cdot 10^3\) \(17\)
\(3\) \(X_i = 1\) \(28\)
\(4\) \(A_i \le 10^5\) \(11\)
\(5\) — \(23\)

Example

Input

7 4
2 5 4 2 1 3 4
5 9 4 2

Output

2 1 3 4 

Note

For the sample [2, 5, 4, 2, 1, 3, 4] These are the operations step by step:

1. [2, 4, 2, 1, 3, 4]   (remove 5)

2. [2, 4, 2, 1, 3, 4]   (9 not present)

3. [2, 2, 1, 3, 4]   (remove 4)

4. [2, 1, 3, 4]   (remove 2)

Solution

For every value, store the indices where it occurs, in increasing order. On command \(X\), remove the first stored index for \(X\) if one exists. Mark that array position as removed.

Every index is inserted and removed at most once. With a hash map, the expected complexity is \(O(N+Q)\) time and \(O(N)\) memory.

#include <deque>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<long long> a(n);
    unordered_map<long long, deque<int>> positions;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        positions[a[i]].push_back(i);
    }

    vector<bool> removed(n, false);

    while (q--) {
        long long x;
        cin >> x;

        auto it = positions.find(x);
        if (it != positions.end() && !it->second.empty()) {
            removed[it->second.front()] = true;
            it->second.pop_front();
        }
    }

    for (int i = 0; i < n; i++) {
        if (!removed[i]) {
            cout << a[i] << ' ';
        }
    }
    cout << '\n';
}