Maximum Sum Non-Decreasing Subsequence

You are given an array of n integers and an integer k. Your task is to find a non-decreasing subsequence of length k with the maximum possible sum. A subsequence is a sequence that is derived from the array by selecting some elements (not necessarily contiguous) and then sorting them in non-decreasing order.

In other words, if you denote the chosen subsequence elements by \(x_1, x_2, \ldots, x_k\), your goal is to maximize \(\sum_{i=1}^{k} x_i\) while ensuring \(x_1 \le x_2 \le \ldots \le x_k\). It is guaranteed that a solution exists.

inputFormat

The input is read from standard input (stdin) and consists of three parts:

1. The first line contains an integer \(n\), the number of elements in the array.
2. The second line contains \(n\) space-separated integers representing the array elements.
3. The third line contains an integer \(k\), the required length of the subsequence.

outputFormat

Output to standard output (stdout) a single line containing the subsequence of length \(k\) with the maximum sum. The chosen subsequence should be printed in non-decreasing order, with each element separated by a single space.

## sample

5
4 2 3 1 5
3

3 4 5

</p>