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