#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### Title

### Problem Statement

You are given an integer sequence `A` of length `N` and an integer `K`.
You will perform the following operation on this sequence `Q` times:

- Choose a contiguous subsequence of length
`K`, then remove the smallest element among the`K`elements contained in the chosen subsequence (if there are multiple such elements, choose one of them as you like).

Let `X` and `Y` be the values of the largest and smallest element removed in the `Q` operations. You would like `X-Y` to be as small as possible.
Find the smallest possible value of `X-Y` when the `Q` operations are performed optimally.

### Constraints

`1 ≤ N ≤ 2000``1 ≤ K ≤ N``1 ≤ Q ≤ N-K+1``1 ≤ A`_{i}≤ 10^{9}- All values in input are integers.

### Input

Input is given from Standard Input in the following format:

NKQA_{1}A_{2}...A_{N}

### Output

Print the smallest possible value of `X-Y`.

### Sample Input 1

5 3 2 4 3 1 5 2

### Sample Output 1

1

In the first operation, whichever contiguous subsequence of length `3` we choose, the minimum element in it is `1`.
Thus, the first operation removes `A _{3}=1` and now we have

`A=(4,3,5,2)`. In the second operation, it is optimal to choose

`(A`as the contiguous subsequence of length

_{2},A_{3},A_{4})=(3,5,2)`3`and remove

`A`. In this case, the largest element removed is

_{4}=2`2`, and the smallest is

`1`, so their difference is

`2-1=1`.

### Sample Input 2

10 1 6 1 1 2 3 5 8 13 21 34 55

### Sample Output 2

7

### Sample Input 3

11 7 5 24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784

### Sample Output 3

451211184

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 48 | 1s | 256MB | Average |

2 | 0 | 3 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o removemq -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512