#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdint.h>
#include <float.h>
#include <time.h>
#include <sys/time.h>
 
#define SEED64 88172645463325252ULL
 
typedef double val_t;
 
inline static double baka_sec_count(void) {
    struct timeval tv;
    gettimeofday(&tv, NULL);
	return (double)tv.tv_sec + ((double)tv.tv_usec / 1000000.0);
 
}
 
static uint64_t x = SEED64;
 
inline void seed64(uint64_t seed) {
	x = seed;
}
 
inline static uint64_t rand64(void) {
	x = x ^ (x << 13);
	x = x ^ (x >> 7);
	return x = x ^ (x << 17);
}
 
inline static val_t* alloc_data(int n_) {
	val_t* p = (val_t*)malloc(sizeof(val_t) * n_);
 
	for (int i = 0; i < n_; ++i) {
		p[i] = rand64();
	}
 
	return p;
}
 
inline static val_t* alloc_clone_data(double* p_, int n_) {
	val_t* p = (val_t*)malloc(sizeof(val_t) * n_);
	memcpy(p, p_, sizeof(val_t) * n_);
	return p;
}
 
inline static void free_data(double* p_) {
	free(p_);
}
 
// ahoselect ここから
 
inline static void aho_select(val_t* arr_, int n_, val_t* top_, int k_) {
 
	for (int i = 0; i < k_; ++i) {
		top_[i] = -DBL_MAX;
	}
 
	for (int i = 0; i < n_; ++i) {
		for (int j = 0; j < k_; ++j) {
			if (top_[j] < arr_[i]) {
				for (int l = k_ - 1; l > j; --l) {
					top_[l] = top_[l - 1];
				}
				top_[j] = arr_[i];
				break;
			}
		}
	}
}
 
// ahoselect ここまで
 
 
// quickselect ここから
 
#define SEED32 2463534242
 
static uint32_t y = SEED32;
 
inline void seed32(uint32_t seed) {
	y = seed;
}
 
inline static uint32_t rand32() {
	y = y ^ (y << 13);
	y = y ^ (y >> 17);
	return y = y ^ (y << 15);
}
 
inline static val_t* partition(val_t* p_left_, val_t* p_right_) {
 
	val_t* const p_pivot = p_left_ + (rand32() % (p_right_ - p_left_));
	val_t tmp;
	tmp = *p_pivot; *p_pivot = *p_right_; *p_right_ = tmp;
 
	val_t const* const p_prev_right = p_right_ - 1;
 
	for (val_t* p = p_left_; p < p_prev_right; ++p) {
		if (*p > *p_right_) {
			tmp = *p; *p = *p_left_; *p_left_ = tmp;
			++p_left_;
		}
	}
	tmp = *p_right_; *p_right_ = *p_left_; *p_left_ = tmp;
	return p_left_;
}
 
inline static void quickselect(val_t* p_left_, val_t* p_right_, val_t* k_) {
 
	while (p_left_ < p_right_) {
		val_t* p_pivot = partition(p_left_, p_right_);
		if (p_pivot > k_) {
			p_right_ = p_pivot - 1;
		} else if (p_pivot < k_) {
			p_left_ = p_pivot + 1;
		} else {
			break;
		}
	}
}
 
// quickselect ここまで
 
int main(int argc, char* argv[]) {
 
	double s;
	double e;
	clock_t us;
	clock_t ue;
	val_t* p1;
	val_t* p2;
	val_t* top;
	size_t u_elems;
	size_t u_topss;
 
	// 上位3件
	u_elems = 0;
	u_topss = 0;
	fprintf(stderr, "上位3件\n");
	fprintf(stderr, "要素数,抽出数,ｱﾎ(t),ｱﾎ(c),ｴﾚｶﾞﾝﾄ(t),ｴﾚｶﾞﾝﾄ(c)\n");
	for (int i = 0; i < 100; ++i) {
		u_elems += 10000;
		u_topss = 3;
 
		p1 = alloc_data(u_elems);
		p2 = alloc_clone_data(p1, u_elems);
		top = (val_t*)malloc(u_topss * sizeof(val_t));
 
		s = baka_sec_count();
		us = clock();
		aho_select(p1, u_elems, top, u_topss);
		ue = clock();
		e = baka_sec_count();
		fprintf(stderr, "%u,%u,%.04lf,%.04lf", u_elems, u_topss, e - s, (double)(ue - us) / CLOCKS_PER_SEC);
 
		s = baka_sec_count();
		us = clock();
		quickselect(p2, p2 + u_elems - 1, p2 + u_topss - 1);
		ue = clock();
		e = baka_sec_count();
		fprintf(stderr, ",%.04lf,%.04lf\n", e - s, (double)(ue - us) / CLOCKS_PER_SEC);
 
		free_data(p1);
		free_data(p2);
		free(top);
	}
 
	seed64(SEED64);
 
	// 上位3%
	u_elems = 0;
	u_topss = 0;
	fprintf(stderr, "上位3%\n");
	fprintf(stderr, "要素数,抽出数,ｱﾎ(t),ｱﾎ(c),ｴﾚｶﾞﾝﾄ(t),ｴﾚｶﾞﾝﾄ(c)\n");
	for (int i = 0; i < 100; ++i) {
		u_elems += 10000;
		u_topss += 300;
 
		p1 = alloc_data(u_elems);
		p2 = alloc_clone_data(p1, u_elems);
		top = (val_t*)malloc(u_topss * sizeof(val_t));
 
		s = baka_sec_count();
		us = clock();
		aho_select(p1, u_elems, top, u_topss);
		ue = clock();
		e = baka_sec_count();
		fprintf(stderr, "%u,%u,%.04lf,%.04lf", u_elems, u_topss, e - s, (double)(ue - us) / CLOCKS_PER_SEC);
 
		s = baka_sec_count();
		us = clock();
		quickselect(p2, p2 + u_elems - 1, p2 + u_topss - 1);
		ue = clock();
		e = baka_sec_count();
		fprintf(stderr, ",%.04lf,%.04lf\n", e - s, (double)(ue - us) / CLOCKS_PER_SEC);
 
		free_data(p1);
		free_data(p2);
		free(top);
	}
 
	return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPG1lbW9yeS5oPgojaW5jbHVkZSA8c3RkaW50Lmg+CiNpbmNsdWRlIDxmbG9hdC5oPgojaW5jbHVkZSA8dGltZS5oPgojaW5jbHVkZSA8c3lzL3RpbWUuaD4KCiNkZWZpbmUgU0VFRDY0IDg4MTcyNjQ1NDYzMzI1MjUyVUxMCgp0eXBlZGVmIGRvdWJsZSB2YWxfdDsKIAppbmxpbmUgc3RhdGljIGRvdWJsZSBiYWthX3NlY19jb3VudCh2b2lkKSB7CiAgICBzdHJ1Y3QgdGltZXZhbCB0djsKICAgIGdldHRpbWVvZmRheSgmdHYsIE5VTEwpOwoJcmV0dXJuIChkb3VibGUpdHYudHZfc2VjICsgKChkb3VibGUpdHYudHZfdXNlYyAvIDEwMDAwMDAuMCk7CiAKfQoKc3RhdGljIHVpbnQ2NF90IHggPSBTRUVENjQ7CgppbmxpbmUgdm9pZCBzZWVkNjQodWludDY0X3Qgc2VlZCkgewoJeCA9IHNlZWQ7Cn0KCmlubGluZSBzdGF0aWMgdWludDY0X3QgcmFuZDY0KHZvaWQpIHsKCXggPSB4IF4gKHggPDwgMTMpOwoJeCA9IHggXiAoeCA+PiA3KTsKCXJldHVybiB4ID0geCBeICh4IDw8IDE3KTsKfQogCmlubGluZSBzdGF0aWMgdmFsX3QqIGFsbG9jX2RhdGEoaW50IG5fKSB7Cgl2YWxfdCogcCA9ICh2YWxfdCopbWFsbG9jKHNpemVvZih2YWxfdCkgKiBuXyk7CiAKCWZvciAoaW50IGkgPSAwOyBpIDwgbl87ICsraSkgewoJCXBbaV0gPSByYW5kNjQoKTsKCX0KIAoJcmV0dXJuIHA7Cn0KCmlubGluZSBzdGF0aWMgdmFsX3QqIGFsbG9jX2Nsb25lX2RhdGEoZG91YmxlKiBwXywgaW50IG5fKSB7Cgl2YWxfdCogcCA9ICh2YWxfdCopbWFsbG9jKHNpemVvZih2YWxfdCkgKiBuXyk7CgltZW1jcHkocCwgcF8sIHNpemVvZih2YWxfdCkgKiBuXyk7CglyZXR1cm4gcDsKfQoKaW5saW5lIHN0YXRpYyB2b2lkIGZyZWVfZGF0YShkb3VibGUqIHBfKSB7CglmcmVlKHBfKTsKfQoKLy8gYWhvc2VsZWN0IOOBk+OBk+OBi+OCiQoKaW5saW5lIHN0YXRpYyB2b2lkIGFob19zZWxlY3QodmFsX3QqIGFycl8sIGludCBuXywgdmFsX3QqIHRvcF8sIGludCBrXykgewogCglmb3IgKGludCBpID0gMDsgaSA8IGtfOyArK2kpIHsKCQl0b3BfW2ldID0gLURCTF9NQVg7Cgl9CiAKCWZvciAoaW50IGkgPSAwOyBpIDwgbl87ICsraSkgewoJCWZvciAoaW50IGogPSAwOyBqIDwga187ICsraikgewoJCQlpZiAodG9wX1tqXSA8IGFycl9baV0pIHsKCQkJCWZvciAoaW50IGwgPSBrXyAtIDE7IGwgPiBqOyAtLWwpIHsKCQkJCQl0b3BfW2xdID0gdG9wX1tsIC0gMV07CgkJCQl9CgkJCQl0b3BfW2pdID0gYXJyX1tpXTsKCQkJCWJyZWFrOwoJCQl9CgkJfQoJfQp9CgovLyBhaG9zZWxlY3Qg44GT44GT44G+44GnCgoKLy8gcXVpY2tzZWxlY3Qg44GT44GT44GL44KJCgojZGVmaW5lIFNFRUQzMiAyNDYzNTM0MjQyCgpzdGF0aWMgdWludDMyX3QgeSA9IFNFRUQzMjsKCmlubGluZSB2b2lkIHNlZWQzMih1aW50MzJfdCBzZWVkKSB7Cgl5ID0gc2VlZDsKfQoKaW5saW5lIHN0YXRpYyB1aW50MzJfdCByYW5kMzIoKSB7Cgl5ID0geSBeICh5IDw8IDEzKTsKCXkgPSB5IF4gKHkgPj4gMTcpOwoJcmV0dXJuIHkgPSB5IF4gKHkgPDwgMTUpOwp9CgppbmxpbmUgc3RhdGljIHZhbF90KiBwYXJ0aXRpb24odmFsX3QqIHBfbGVmdF8sIHZhbF90KiBwX3JpZ2h0XykgewoKCXZhbF90KiBjb25zdCBwX3Bpdm90ID0gcF9sZWZ0XyArIChyYW5kMzIoKSAlIChwX3JpZ2h0XyAtIHBfbGVmdF8pKTsKCXZhbF90IHRtcDsKCXRtcCA9ICpwX3Bpdm90OyAqcF9waXZvdCA9ICpwX3JpZ2h0XzsgKnBfcmlnaHRfID0gdG1wOwoJCgl2YWxfdCBjb25zdCogY29uc3QgcF9wcmV2X3JpZ2h0ID0gcF9yaWdodF8gLSAxOwoKCWZvciAodmFsX3QqIHAgPSBwX2xlZnRfOyBwIDwgcF9wcmV2X3JpZ2h0OyArK3ApIHsKCQlpZiAoKnAgPiAqcF9yaWdodF8pIHsKCQkJdG1wID0gKnA7ICpwID0gKnBfbGVmdF87ICpwX2xlZnRfID0gdG1wOwoJCQkrK3BfbGVmdF87CgkJfQoJfQoJdG1wID0gKnBfcmlnaHRfOyAqcF9yaWdodF8gPSAqcF9sZWZ0XzsgKnBfbGVmdF8gPSB0bXA7CglyZXR1cm4gcF9sZWZ0XzsKfQoKaW5saW5lIHN0YXRpYyB2b2lkIHF1aWNrc2VsZWN0KHZhbF90KiBwX2xlZnRfLCB2YWxfdCogcF9yaWdodF8sIHZhbF90KiBrXykgewoKCXdoaWxlIChwX2xlZnRfIDwgcF9yaWdodF8pIHsKCQl2YWxfdCogcF9waXZvdCA9IHBhcnRpdGlvbihwX2xlZnRfLCBwX3JpZ2h0Xyk7CgkJaWYgKHBfcGl2b3QgPiBrXykgewoJCQlwX3JpZ2h0XyA9IHBfcGl2b3QgLSAxOwoJCX0gZWxzZSBpZiAocF9waXZvdCA8IGtfKSB7CgkJCXBfbGVmdF8gPSBwX3Bpdm90ICsgMTsKCQl9IGVsc2UgewoJCQlicmVhazsKCQl9Cgl9Cn0KCi8vIHF1aWNrc2VsZWN0IOOBk+OBk+OBvuOBpwoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIqIGFyZ3ZbXSkgewoKCWRvdWJsZSBzOwoJZG91YmxlIGU7CgljbG9ja190IHVzOwoJY2xvY2tfdCB1ZTsKCXZhbF90KiBwMTsKCXZhbF90KiBwMjsKCXZhbF90KiB0b3A7CglzaXplX3QgdV9lbGVtczsKCXNpemVfdCB1X3RvcHNzOwoKCS8vIOS4iuS9jTPku7YKCXVfZWxlbXMgPSAwOwoJdV90b3BzcyA9IDA7CglmcHJpbnRmKHN0ZGVyciwgIuS4iuS9jTPku7ZcbiIpOwoJZnByaW50ZihzdGRlcnIsICLopoHntKDmlbAs5oq95Ye65pWwLO+9se++jih0KSzvvbHvvo4oYyks7720776a7722776e776d776EKHQpLO+9tO++mu+9tu++nu++ne++hChjKVxuIik7Cglmb3IgKGludCBpID0gMDsgaSA8IDEwMDsgKytpKSB7CgkJdV9lbGVtcyArPSAxMDAwMDsKCQl1X3RvcHNzID0gMzsKCgkJcDEgPSBhbGxvY19kYXRhKHVfZWxlbXMpOwoJCXAyID0gYWxsb2NfY2xvbmVfZGF0YShwMSwgdV9lbGVtcyk7CgkJdG9wID0gKHZhbF90KiltYWxsb2ModV90b3BzcyAqIHNpemVvZih2YWxfdCkpOwoKCQlzID0gYmFrYV9zZWNfY291bnQoKTsKCQl1cyA9IGNsb2NrKCk7CgkJYWhvX3NlbGVjdChwMSwgdV9lbGVtcywgdG9wLCB1X3RvcHNzKTsKCQl1ZSA9IGNsb2NrKCk7CgkJZSA9IGJha2Ffc2VjX2NvdW50KCk7CgkJZnByaW50ZihzdGRlcnIsICIldSwldSwlLjA0bGYsJS4wNGxmIiwgdV9lbGVtcywgdV90b3BzcywgZSAtIHMsIChkb3VibGUpKHVlIC0gdXMpIC8gQ0xPQ0tTX1BFUl9TRUMpOwoKCQlzID0gYmFrYV9zZWNfY291bnQoKTsKCQl1cyA9IGNsb2NrKCk7CgkJcXVpY2tzZWxlY3QocDIsIHAyICsgdV9lbGVtcyAtIDEsIHAyICsgdV90b3BzcyAtIDEpOwoJCXVlID0gY2xvY2soKTsKCQllID0gYmFrYV9zZWNfY291bnQoKTsKCQlmcHJpbnRmKHN0ZGVyciwgIiwlLjA0bGYsJS4wNGxmXG4iLCBlIC0gcywgKGRvdWJsZSkodWUgLSB1cykgLyBDTE9DS1NfUEVSX1NFQyk7CgoJCWZyZWVfZGF0YShwMSk7CgkJZnJlZV9kYXRhKHAyKTsKCQlmcmVlKHRvcCk7Cgl9CgoJc2VlZDY0KFNFRUQ2NCk7CgoJLy8g5LiK5L2NMyUKCXVfZWxlbXMgPSAwOwoJdV90b3BzcyA9IDA7CglmcHJpbnRmKHN0ZGVyciwgIuS4iuS9jTMlXG4iKTsKCWZwcmludGYoc3RkZXJyLCAi6KaB57Sg5pWwLOaKveWHuuaVsCzvvbHvvo4odCks772x776OKGMpLO+9tO++mu+9tu++nu++ne++hCh0KSzvvbTvvprvvbbvvp7vvp3vvoQoYylcbiIpOwoJZm9yIChpbnQgaSA9IDA7IGkgPCAxMDA7ICsraSkgewoJCXVfZWxlbXMgKz0gMTAwMDA7CgkJdV90b3BzcyArPSAzMDA7CgoJCXAxID0gYWxsb2NfZGF0YSh1X2VsZW1zKTsKCQlwMiA9IGFsbG9jX2Nsb25lX2RhdGEocDEsIHVfZWxlbXMpOwoJCXRvcCA9ICh2YWxfdCopbWFsbG9jKHVfdG9wc3MgKiBzaXplb2YodmFsX3QpKTsKCgkJcyA9IGJha2Ffc2VjX2NvdW50KCk7CgkJdXMgPSBjbG9jaygpOwoJCWFob19zZWxlY3QocDEsIHVfZWxlbXMsIHRvcCwgdV90b3Bzcyk7CgkJdWUgPSBjbG9jaygpOwoJCWUgPSBiYWthX3NlY19jb3VudCgpOwoJCWZwcmludGYoc3RkZXJyLCAiJXUsJXUsJS4wNGxmLCUuMDRsZiIsIHVfZWxlbXMsIHVfdG9wc3MsIGUgLSBzLCAoZG91YmxlKSh1ZSAtIHVzKSAvIENMT0NLU19QRVJfU0VDKTsKCgkJcyA9IGJha2Ffc2VjX2NvdW50KCk7CgkJdXMgPSBjbG9jaygpOwoJCXF1aWNrc2VsZWN0KHAyLCBwMiArIHVfZWxlbXMgLSAxLCBwMiArIHVfdG9wc3MgLSAxKTsKCQl1ZSA9IGNsb2NrKCk7CgkJZSA9IGJha2Ffc2VjX2NvdW50KCk7CgkJZnByaW50ZihzdGRlcnIsICIsJS4wNGxmLCUuMDRsZlxuIiwgZSAtIHMsIChkb3VibGUpKHVlIC0gdXMpIC8gQ0xPQ0tTX1BFUl9TRUMpOwoKCQlmcmVlX2RhdGEocDEpOwoJCWZyZWVfZGF0YShwMik7CgkJZnJlZSh0b3ApOwoJfQoKCXJldHVybiAwOwp9CiA=