Limits 1s, 512 MB

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 33 months of hard work finally he made a game. In his game, there was a scene where there were nn buildings of different heights (A1,A2,A3,.,An)(A_1, A_2, A_3, …., A_n) in a row. He places 22 robots PP and QQ on top of the KthK^{th} building, so the initial height of the two robots is the height of the KthK^{th} building. Robots PP & QQ had different characteristics than each other.

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

  • Robot QQ can only move to the left buildings ii such that, height of the ithi^{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 PP and QQ including its starting position.

Input

The first line contains two integers  nn and KK — the number of the buildings and the starting position of the Robot PP and QQ respectively.

The next line will contain the heights of the nn buildings (A1,A2,A3,.,An).(A_1, A_2, A_3, …., A_n).

1n1051\leq n \leq 10^5

1Kn1 \leq K \leq n

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

Output

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

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

Samples

InputOutput
7 4
1 4 3 2 1 6 7
2 6 7 
2 1 

Robot PP will start at 4th4^{th} building, then it will move to 5th5^{th} building but its characteristics does not allow to land there. So, PP will move to the 6th6^{th} building and can land there. It will continue its journey so on. likewise, Robot QQ follows its characteristics to land on maximum number of buildings.

InputOutput
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.

Submit

Login to submit.

Statistics

84% Solution Ratio
Anamul1210Earliest, 5M ago
Modhusudon1687Fastest, 0.0s
emon192002Lightest, 5.2 MB
rudro25Shortest, 550B
Toph uses cookies. By continuing you agree to our Cookie Policy.