// DA_serie03.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <string>
#include <iostream>
#include <string>
using namespace std;
static int currentsize=0;
void merge(int in[], int l, int m, int r);
void sort(int *in);
int main()
{
int testcases ;
for ( cin >> testcases ; testcases > 0 ; testcases-- ) {
int *values=NULL;
cin >> currentsize;
values = new int[currentsize];
int element;
cin >> element;
int length;
cin >> length;
for (int i = 2; i<currentsize;i++) cin >> values[i-2];
int median = medianOfMedian(values,false);
sort(values);
int found = values[element];
cout << found << " "<<median << "\n";
delete [] values;
}
//system("pause");
return 0;
}
static int medianOfMedian(int* in, bool second){
int length = sizeof(in);
if (length<6) return -1; //no medianofmedian, only a median
// CHEAT? this is the real median of medians instead of again the median of medians of more groups of 5.
if (second) {
sort(in);
return in[length/2];
}
int* currentgroup=new int[5]; //to save the groups of 5
int nrmedians = (length%5==0)?length/5:length/5+1;
int* medians=new int[nrmedians]; //to save all the medians
/* loop through numbers, make groups of five, sort them and compute their medians*/
for (int s = 0;s<nrmedians;s++){
int j=0;
if (s==nrmedians-1) currentgroup= new int[length-s*5];
while (j<5&&j+s*5<length) {
currentgroup[j]=in[s*5+j];
j++;
}
sort(currentgroup);
if (j==5||j==4) medians[s]=currentgroup[2];
else if (j==3||j==2) medians[s]=currentgroup[1];
else medians[s]=currentgroup[0];
}
if (nrmedians<6) {
sort(medians);
if (nrmedians==5||nrmedians==4) return medians[2];
else if (nrmedians==3||nrmedians==2) return medians[1];
else return medians[0];
} else return medianOfMedian(medians,true);
}
static void merge(int *in, int l, int m, int r) {
int *out = new int[currentsize];
int i = l;
int j = m + 1;
int k = l;
while (i <= m && j <= r) {
// vergleiche von Folgeleementen
if (in[i] < in[j]) {
out[k] = in[i];
i++;
} else {
out[k] = in[j];
j++;
}
k++;
}
if (i > m) {
for (int h = l; h < j; h++) {
in[h] = out[h];
}
// for (int h = j; h<=r;h++){
// out[h]=in[h];
// k++;
// }
} else {
for (int h = i; h <= m; h++) {
out[k + h - i] = in[h];
}
for (int h = l; h <= r; h++) {
in[h] = out[h];
}
}
delete [] out;
}
static void sort(int *in) {
int ll = 0, rr = 0, mm = 0;
int l = 0;
int r = sizeof(in);
do {
rr = l - 1;
while (rr < r) {
ll = rr + 1;
mm = ll;
while (mm < r && in[mm + 1] > in[mm]) {
mm++;
}
if (mm < r) {
rr = mm + 1;
while (rr < r && in[rr + 1] > in[rr]) {
rr++;
}
merge(in, ll, mm, rr);
} else {
rr = mm;
}
}
} while (ll != l);
}