- Practice
- Algorithms
- Dynamic Programming
- Super Kth LIS

# Super Kth LIS

# Super Kth LIS

Given an array of integers (), find all possible increasing subsequences of maximum length, . Then print the lexicographically longest increasing subsequence as a single line of space-separated integers; if there are less than subsequences of length , print .

Two subsequences and are considered to be *different* if there exists at least one such that .

**Input Format**

The first line contains space-separated integers, and , respectively.

The second line consists of space-separated integers denoting respectively.

**Constraints**

**Scoring**

- for of the test data.
- for of the test data.

**Output Format**

Print a single line of space-separated integers denoting the lexicographically longest increasing subsequence; if there are less than subsequences of length , print .

**Note:** is the length of longest increasing subsequence in the array.

**Sample Input 0**

```
5 3
1 3 1 2 5
```

**Sample Output 0**

```
1 3 5
```

**Sample Input 1**

```
5 2
1 3 2 4 5
```

**Sample Output 1**

```
1 3 4 5
```

**Explanation**

*Sample Case 0:*

The longest possible increasing subsequences in lexicographical order are:

Notice that the first and second subsequences appear the same; they are actually both *different* because the in the first subsequence comes from array element , and the in the second subsequence comes from array element . Because , we print the one () as a single line of space-separated integers.

*Sample Case 1:*

The longest possible increasing subsequences in lexicographical order are:

Because , we print the one () as a single line of space-separated integers.