#include <iostream>
using namespace std;
int partition(int* liczba,char* znaki, int p, int r)
{
int pivot = liczba[r];
while ( p < r )
{
while ( liczba[p] > pivot )
p++;
while ( liczba[r] < pivot )
r--;
if ( liczba[p] == liczba[r] )
p++;
else if ( p < r ) {
int tmp = liczba[p];
char tmpch= znaki [p];
liczba[p] = liczba[r];
znaki[p] = znaki[r];
liczba[r] = tmp;
znaki[r] = tmpch;
}
}
return r;
}
int quick_select(int*liczba, char* znaki, int p, int r, int k)
{
if ( p == r ) return znaki[p];
int j = partition(liczba,znaki, p, r);
int length = j - p + 1;
if ( length == k ) return znaki[j];
else if ( k < length ) return quick_select(liczba,znaki, p, j - 1, k);
else return quick_select(liczba,znaki, j + 1, r, k - length);
}
int main()
{
int n,k;
char z;
cin>>n;
int *liczby=new int [n];
char *znaki=new char [n];
for(int i=0;i<n;++i)
{
cin>>liczby[i];
cin>>znaki[i];
}
cin>>k;
for ( int i =1; i <=k; i++)
{
if (i!=1)
{
cout<<endl;
}
z=quick_select(liczby, znaki, 0, n-1, i);
cout<<z;
}
delete [] liczby;
delete [] znaki;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCmludCBwYXJ0aXRpb24oaW50KiBsaWN6YmEsY2hhciogem5ha2ksIGludCBwLCBpbnQgcikKewogICAgaW50IHBpdm90ID0gbGljemJhW3JdOwoKICAgIHdoaWxlICggcCA8IHIgKQogICAgewogICAgICAgIHdoaWxlICggbGljemJhW3BdID4gcGl2b3QgKQogICAgICAgICAgICBwKys7CgogICAgICAgIHdoaWxlICggbGljemJhW3JdIDwgcGl2b3QgKQogICAgICAgICAgICByLS07CgogICAgICAgIGlmICggbGljemJhW3BdID09IGxpY3piYVtyXSApCiAgICAgICAgICAgIHArKzsKICAgICAgICBlbHNlIGlmICggcCA8IHIgKSB7CiAgICAgICAgICAgIGludCB0bXAgPSBsaWN6YmFbcF07CiAgICAgICAgICAgIGNoYXIgdG1wY2g9IHpuYWtpIFtwXTsKICAgICAgICAgICAgbGljemJhW3BdID0gbGljemJhW3JdOwogICAgICAgICAgICB6bmFraVtwXSA9IHpuYWtpW3JdOwogICAgICAgICAgICBsaWN6YmFbcl0gPSB0bXA7CiAgICAgICAgICAgIHpuYWtpW3JdID0gdG1wY2g7CiAgICAgICAgfQogICAgfQoKICAgIHJldHVybiByOwp9CgppbnQgcXVpY2tfc2VsZWN0KGludCpsaWN6YmEsIGNoYXIqIHpuYWtpLCBpbnQgcCwgaW50IHIsIGludCBrKQp7CiAgICBpZiAoIHAgPT0gciApIHJldHVybiB6bmFraVtwXTsKICAgIGludCBqID0gcGFydGl0aW9uKGxpY3piYSx6bmFraSwgcCwgcik7CiAgICBpbnQgbGVuZ3RoID0gaiAtIHAgKyAxOwogICAgaWYgKCBsZW5ndGggPT0gayApIHJldHVybiB6bmFraVtqXTsKICAgIGVsc2UgaWYgKCBrIDwgbGVuZ3RoICkgcmV0dXJuIHF1aWNrX3NlbGVjdChsaWN6YmEsem5ha2ksIHAsIGogLSAxLCBrKTsKICAgIGVsc2UgIHJldHVybiBxdWlja19zZWxlY3QobGljemJhLHpuYWtpLCBqICsgMSwgciwgayAtIGxlbmd0aCk7Cn0KCmludCBtYWluKCkKewoKICAgIGludCBuLGs7CiAgICBjaGFyIHo7CiAgICBjaW4+Pm47CiAgICBpbnQgKmxpY3pieT1uZXcgaW50IFtuXTsKICAgIGNoYXIgKnpuYWtpPW5ldyBjaGFyIFtuXTsKICAgIGZvcihpbnQgaT0wO2k8bjsrK2kpCiAgICB7CiAgICAgICAgY2luPj5saWN6YnlbaV07CiAgICAgICAgY2luPj56bmFraVtpXTsKICAgIH0KICAgIGNpbj4+azsKICAgIGZvciAoIGludCBpID0xOyBpIDw9azsgaSsrKQogICAgewogICAgICAgIGlmIChpIT0xKQogICAgICAgIHsKICAgICAgICAgICAgY291dDw8ZW5kbDsKICAgICAgICB9CiAgICAgICAgej1xdWlja19zZWxlY3QobGljemJ5LCB6bmFraSwgMCwgbi0xLCBpKTsKICAgICAgICBjb3V0PDx6OwogICAgfQogICAgZGVsZXRlIFtdIGxpY3pieTsKICAgIGRlbGV0ZSBbXSB6bmFraTsKICByZXR1cm4gMDsKfQ==