Intersection of Two Sorted Arrays

Given two sorted arrays, your task is to find their intersection. The arrays are guaranteed to be sorted in non-decreasing order and may contain duplicate elements. Your result should only contain distinct elements present in both arrays. You are required to implement an algorithm that runs efficiently by taking advantage of the sorted nature of the arrays.

Note: The intersection should be printed in the same sorted order. If no common elements exist, output an empty line.

In mathematical terms, if we denote the two arrays as \(A = [a_1, a_2, \dots, a_n]\) and \(B = [b_1, b_2, \dots, b_m]\), you must find the set:

[ A \cap B = { x : x \text{ is in both } A \text{ and } B }]

inputFormat

The input is given through standard input (stdin) and consists of four lines:

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

outputFormat

Print the distinct intersection elements of the two arrays in one line, separated by spaces. If there are no common elements, print an empty line.

5
1 2 3 4 5
3
1 2 3

1 2 3