Untitled

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findMedian(vector<int> array) {
    sort(array.begin(), array.end());
    return array[array.size() / 2];
}

vector<int> divideArray(vector<int> v) {
    vector<int> medians;
    vector<int> temp;
    for (int i = 0; i < v.size(); i += 1) {
        temp.push_back(v[i]);
        if (temp.size() == 5 || i == v.size() - 1) {
            medians.push_back(findMedian(temp));
            temp.clear();
        }
    }
    return medians;
}

int findNumber(vector<int> &v, int k) {
    if (v.size() - 1 < k) {
        return -1;
    }

    if (v.size() <= 5) {
        sort(v.begin(), v.end());
        return v[k];
    }

    vector<int> medians = divideArray(v);
    int middleElement = findMedian(medians);

    vector<int> smaller, larger;
    int equal = 0;

    for (int num : v) {
        if (num < middleElement) {
            smaller.push_back(num);
        } else if (num > middleElement) {
            larger.push_back(num);
        } else {
            equal++;
        }
    }

    if (k < smaller.size()) {
        return findNumber(smaller, k);
    }
    if (k < smaller.size() + equal) {
        return middleElement;
    }
    return findNumber(larger, k - smaller.size() - equal);
}

int isNumberGood(int num) {
    int count = 0;

    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            count++;
            while (num % i == 0) {
                num /= i;
            }
        }
    }
    if (num > 1) {
        count++;
    }
    return count;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t, n, a, k;
    vector<int> v;

    cin >> t;

    for (int i = 0; i < t; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> a;
            if (isNumberGood(a) % 2 == 0) v.push_back(a);
        }
        cin >> k;
        if (v.size() - 1 < k) {
            cout << "BRAK DANYCH" << endl;
            v.clear();
            continue;
        }
        int result = findNumber(v, k);
        if (result != -1) cout << result << endl;
        v.clear();
    }

    return 0;
}