/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君は長さ N の整数列 A=(A_1,A_2,\ldots,A_N) を持っています。
A は広義単調増加であることが保証されます。
高橋君はこの整数列に対して M 回操作を行います。 i 回目 (1\leq i\leq M) の操作では、次の操作を行います。
数列 A が B_i を要素として持つならば、そのような要素を 1 つ選び、削除する。 そのような要素が存在しないならば何もしない。
A は広義単調増加であるため、操作後の列は要素の選び方によらず一意であり、再び広義単調増加となることに注意せよ。
M 回の操作を行なった後の A を求めてください。
広義単調増加 とは
数列 X=(X_1,X_2,\ldots,X_K) が広義単調増加であるとは、 任意の i (1\leq i\leq K-1) について、 X_i\leq X_{i+1} をみたすことを指します。制約
- 1 \leq N \leq 100
- 1 \leq M \leq 100
- 1 \leq A_i,B_i \leq 10^9
- 整数列 A は広義単調増加である。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
出力
操作後の A の各要素を、順に空白区切りで一行に出力せよ。
操作後の A が空ならば、何も出力しないようにせよ。
入力例 1
8 5 1 2 2 3 3 3 5 6 2 2 7 3 2
出力例 1
1 3 3 5 6
最初、A は A=(1,2,2,3,3,3,5,6) です。
操作は次のように行われます。
- A から 2 を 1 つ削除し、操作後の A は A=(1,2,3,3,3,5,6) となります。
- A から 2 を 1 つ削除し、操作後の A は A=(1,3,3,3,5,6) となります。
- A は 7 を要素として持たないため、何も行いません。操作後の A は A=(1,3,3,3,5,6) のままです。
- A から 3 を 1 つ削除し、操作後の A は A=(1,3,3,5,6) となります。
- A は 2 を要素として持たないため、何も行いません。操作後の A は A=(1,3,3,5,6) のままです。
よって、すべての操作の後、A=(1,3,3,5,6) であるため、要素をこの順に空白区切りで出力します。
入力例 2
1 2 1 1 1
出力例 2
操作後の A は空となるため、何も出力しません。
Score : 200 points
Problem Statement
Takahashi has an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.
It is guaranteed that A is non-decreasing.
Takahashi performs M operations on this integer sequence. In the i-th operation (1\leq i\leq M), he performs the following operation:
If the sequence A contains B_i as an element, select one such element and delete it. If no such element exists, do nothing.
Note that since A is non-decreasing, the sequence after the operation is uniquely determined regardless of the choice of element, and remains non-decreasing.
Find A after performing M operations.
What is non-decreasing?
A sequence X=(X_1,X_2,\ldots,X_K) is non-decreasing if X_i\leq X_{i+1} holds for all i (1\leq i\leq K-1).Constraints
- 1 \leq N \leq 100
- 1 \leq M \leq 100
- 1 \leq A_i,B_i \leq 10^9
- The integer sequence A is non-decreasing.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
Output
Output the elements of A after the operations, in order, separated by spaces on a single line.
If A is empty after the operations, output nothing.
Sample Input 1
8 5 1 2 2 3 3 3 5 6 2 2 7 3 2
Sample Output 1
1 3 3 5 6
Initially, A is A=(1,2,2,3,3,3,5,6).
The operations are performed as follows:
- Delete one 2 from A, and A becomes A=(1,2,3,3,3,5,6) after the operation.
- Delete one 2 from A, and A becomes A=(1,3,3,3,5,6) after the operation.
- Since A does not contain 7 as an element, do nothing. A remains A=(1,3,3,3,5,6) after the operation.
- Delete one 3 from A, and A becomes A=(1,3,3,5,6) after the operation.
- Since A does not contain 2 as an element, do nothing. A remains A=(1,3,3,5,6) after the operation.
Therefore, after all operations, A=(1,3,3,5,6), so output the elements in this order separated by spaces.
Sample Input 2
1 2 1 1 1
Sample Output 2
A becomes empty after the operations, so output nothing.