Background

zsy 是一个普通的小朋友，他最喜欢的东西就是数，每天早晨他都需要食用大量的数。有一天……

Description

zsy 在吃早餐，他真是无聊透了，他发现这些数十分混乱，于是想求得它们的正序与倒序。为了表达方便，他把分别这些数编号为 $a_1,a_2,a_3,\cdots,a_n$。可是 zsy 太小了，只有 $\sqrt{-1}$ 岁，所以请你来帮助他。

Input

两行。
第一行一个正整数 $n$。
第二行 $n$ 个正整数，即 $a_1 , ... , a_n$。

Output

两行。
第一行输出正序排序后的数。
第二行输出逆序排序后的数。

Samples

10
2 5 3 88 43 22 676 124 556 114514

2 3 5 22 43 88 124 556 676 114514
114514 676 556 124 88 43 22 5 3 2

Limitation

$1 \leq n \leq 10^8$

$-10^6 \leq a_i \leq 10^6$