REMDUP3 - Remove Duplicates 3

Shubhankar is throwing a party tonight. But there is a slight problem. He ordered a packet of toffees. Fussy he is, he had given strict orders to the shopkeeper that in the packet all toffees should be of different kind. That is no more than one toffee of each variety should be there.

Each type of toffee has a unique identification number written on it. He has received the packet from the shopkeeper but he wants to check the same. He starts taking out toffee from the packet one by one saying the ID number of the toffee and if a toffee with same ID has been seen earlier he will throw that toffee.

Tell ID number of the toffees that are finally left. Also print the reverse of that.

Input

First line will contain the number of toffees N. N <= 1000000.

The next N lines will contain N numbers A[1..N]. 0 <= A[i] <= 10^6

Output

Print all the unique toffee ID's in relative order.

Also print the reverse of the unique toffee ID's in relative order.

Example

Input:
6
1
2
1
5
2
3

Output:
1 2 5 3
3 5 2 1

Added by:Rajesh Kumar
Date:2014-08-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2018-08-15 06:32:03
Last AC on 2014-08-23, pretty sure the testfile has been broken since.
2014-09-03 15:33:03 गाैरव
getting wa everytime @rajesh kumar give any tricky test cases please :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.