def kthSmallest(arr, start, end, k):
    if(k > 0 and k <= end - start + 1):
        n = end - start + 1
        median = []
        i = 0
        while(i < n // 5):
            median.append(findMedian(arr, start + i * 5, 5))
            i = i + 1

        if(i * 5 < n):
            median.append(findMedian(arr, start + i * 5, n % 5))
            i = i + 1

        if(i == 1):
            medOfMed = median[i-1]
        else:
            medOfMed = kthSmallest(median, 0, i-1, i // 2)

        pos = partition(arr, start, end, medOfMed)

        if(pos - start == k - 1):
            return arr[pos]
        if(pos - start > k - 1):
            return kthSmallest(arr, start, pos - 1, k)
        return kthSmallest(arr, pos + 1, end, k - pos + start - 1)
    return 0

def swap(arr, a, b):
    temp = arr[a]
    arr[a] = arr[b]
    arr[b] = temp

def partition(arr, start, end, pivot):
    for i in range(start, end):
        if(arr[i] == pivot):
            swap(arr, end, i)
            break

    pivot = arr[end]
    i = start
    for j in range(start, end):
        if(arr[j] <= pivot):
            swap(arr, i, j)
            i = i + 1
    swap(arr, i, end)
    return i

def findMedian(arr, start, n):
    list = []
    for i in range(start, start + n):
        list.append(arr[i])

    list.sort()

    return list[n//2]

def test(k):
    arr = [17, 4, 6, 3, 24, 28, 10]
    n = len(arr)
    print("Array:", arr)
    print("K:", k)
    print(k, "th smallest element:", kthSmallest(arr, 0, n - 1, k))