SMPSEQ4 - Fun with Sequences (Act 2)


You are given a sorted sequence of n integers S = s1, s2, ..., sn and a sorted sequence of m integers Q = q1, q2, ..., qm. Please, print in the ascending order all such si that belongs to Q.

Input data specification

In the first line you are given one integer 2<=n<=100, and in the following line n integers:
-100 <= si <= 100, si <= si+1.

In the third line you are given one integer 2<=m<=100, and in the following line m integers:
-100 <= qi <= 100, qi <= qi+1.

Output data specification

The sequence of requested integers separated by spaces.

Example

Input:
5
-2 -1 0 1 4
6
-3 -2 -1 1 2 3
Output:
-2 -1 1 

hide comments
srujana31: 2021-01-28 03:20:16

using binary search gives time complexity- n(logm). Is this correct?

rmaduzia: 2020-12-24 13:10:06

Take care Binary Search is best solution, but not gonna work in duplicated values

ameybhavsar: 2020-05-09 15:33:30

Solve SMPSEQ3 to solve this problem.

rahatkhan99: 2019-11-28 06:50:39

at first you need to solve the previous question..

ironman4: 2018-08-25 13:09:00

I have used binary search. It's not working for me. Can anyone tell me what might be wrong with my code?

dawid_zwiewka: 2017-07-14 23:56:46

Compares to this http://www.spoj.com/problems/SMPSEQ3/ I added only one character in my code which is "!"... Problem would be more interesting if there were more test cases and/or numbers in sequences. For n, m <= 100 brute force is quick enough.


Added by:kuszi
Date:2013-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64