Array Intersection

Given two arrays of integers, the task is to compute the intersection of these arrays, preserving the order of elements as they appear in the first array. In other words, given two arrays \(A\) and \(B\), output a new array that contains every element \(a \in A\) such that \(a\) is also in \(B\). Each element in \(A\) should appear in the output as many times as it occurs in \(A\) if it exists in \(B\).

Note that the solution should process the arrays in \(O(n)\) or acceptable time complexity, using techniques like converting one of the arrays into a set for efficient look-up.

inputFormat

The input is given via standard input with the following format:

• The first line contains an integer \(n\), representing the number of elements in the first array.
• The second line contains \(n\) space-separated integers.
• The third line contains an integer \(m\), representing the number of elements in the second array.
• The fourth line contains \(m\) space-separated integers.

outputFormat

Output the intersection of the two arrays as a sequence of integers separated by a single space. If there is no common element, output an empty line.

4
1 2 3 4
4
3 4 5 6

3 4