Find the k-th Smallest Element

You are given an array of integers and an integer k. Your task is to find the k-th smallest element in the array.

The problem can be solved efficiently using a modified version of the Quickselect algorithm. Note that the elements in the array may not be unique. The expected time complexity is on average O(n).

Note: The k-th smallest element means that if the array were sorted in non-decreasing order, it would be the element at position k (1-indexed). Use the following algorithm to achieve the result:

Let \( arr \) be the input array. Partition the array around a pivot element and recursively process the subarray that contains the k-th smallest element until the pivot index equals \( k-1 \). The partitioning is done similar to the one in the QuickSort algorithm.

Input/Output Requirements: Your program should read from stdin and write to stdout.

inputFormat

The first line contains a sequence of space-separated integers representing the array.

The second line contains an integer k (1 ≤ k ≤ n, where n is the number of elements in the array).

outputFormat

Output a single integer, which is the k-th smallest element in the array.

## sample

7 10 4 3 20 15
3

7

</p>