Kakashi's Game

Kakashi is a student of CSE at DIU. In his OOP course, he needs to submit a project as the final lab task. So he decided to make a game as a project. After $3$ months of hard work finally he made a game. In his game, there was a scene where there were $n$ buildings of different heights $(A_1, A_2, A_3, …., A_n)$ in a row. He places $2$ robots $P$ and $Q$ on top of the $K^{th}$ building, so the initial height of the two robots is the height of the $K^{th}$ building. Robots $P$ & $Q$ had different characteristics than each other.

• Robot $P$ can only move to the right buildings $i$ such that, height of the $i^{th}$ building is not lower than it’s previous landed building.

• Robot $Q$ can only move to the left buildings $i$ such that, height of the $i^{th}$ building is not higher than it’s previous landed building.

Both robots have to land on the maximum number of buildings they can.

Now, Kakashi wants to test this part of his game to ensure that the game is working well without any bugs before submitting it. So he wants your help to determine the landed buildings height for both Robots $P$ and $Q$ including its starting position.

Input

The first line contains two integers  $n$ and $K$ — the number of the buildings and the starting position of the Robot $P$ and $Q$ respectively.

The next line will contain the heights of the $n$ buildings $(A_1, A_2, A_3, …., A_n).$

$1\leq n \leq 10^5$

$1 \leq K \leq n$

$1 \leq A_i \leq 10^{15}$

Output

First line of the output will contain heights of the landed buildings of robot $P$.

Second line of the output will contain heights of the landed buildings of robot $Q$.

Samples

Input	Output
7 4 1 4 3 2 1 6 7	2 6 7 2 1
Robot $P$ will start at $4^{th}$ building, then it will move to $5^{th}$ building but its characteristics does not allow to land there. So, $P$ will move to the $6^{th}$ building and can land there. It will continue its journey so on. likewise, Robot $Q$ follows its characteristics to land on maximum number of buildings.

Input	Output
11 5 2 13 23 16 18 21 37 33 12 34 42	18 21 37 42 18 16 13 2

Be careful about the newline (‘\n’) at the end.