Intersection of Two Sorted Arrays

Problem Statement

Given two sorted arrays, your task is to compute their intersection. The intersection of two arrays is defined as the set of elements that appear in both arrays. The resulting list should also be sorted in non-decreasing order and must not contain duplicates.

You are expected to design an algorithm that runs in linear time, i.e. \(O(n + m)\), where \(n\) and \(m\) are the lengths of the two arrays respectively.

inputFormat

The input is given via standard input (stdin) and has the following format:

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

outputFormat

Print the intersection of the two arrays as a sequence of sorted unique integers separated by a single space to standard output (stdout). If there is no intersection, output an empty line.

## sample

5
1 3 4 5 7
4
2 3 5 6

3 5

</p>