---
{"category_name":"easy","problem_code":"SUBMEDIA","problem_name":"Meet In The Median","problemComponents":{"constraints":"- $1 \\leq T \\leq 30$\n- $1 \\leq K \\leq N \\leq 2 \\times 10^5$\n- $1 \\leq A_i \\leq 10^9$\n- Sum of $N$ over all test cases won\u0027t exceed $5 \\times 10^5$","constraintsState":true,"subtasks":"- 30 points : $1 \\leq R \\leq 10000$\n- 70 points : $1 \\leq R \\leq 10^9$\n","subtasksState":false,"inputFormat":"- The first line will contain $T$, the number of test cases. The description of test cases follow.\n- The first line of each test case consists of two space-separated integers $N$, the length of the sequence, and $K$, the length of the subsequence to be found.\n- The second line of each test case consists of $N$ **distinct** space-separated integers $A_i$, the elements of the sequence.\n","inputFormatState":true,"outputFormat":"- For each test case, output two lines.\n- The first line should consist of the median of the subsequence with the maximum median.\n- The second line should consist of $K$ space-separated integers, representing a subsequence with that median. If there are multiple such subsequences, print any.\n","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"1\n5 3\n1 4 3 6 5","output":"5\n1 6 5","explanation":"","isDeleted":false}}},"video_editorial_url":"","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"hitch_hiker42","problem_tester":"","date_added":"30-08-2021","tags":{"0":"cdmn2021","1":"greedy","2":"hitch_hiker42","3":"simple"},"problem_difficulty_level":"Simple","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/SUBMEDIA","time":{"view_start_date":1630603800,"submit_start_date":1630603800,"visible_start_date":1630603800,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=SUBMEDIA","is_proctored":false,"visitedContests":{},"layout":"problem"}
---
You're given a sequence of $N$ **distinct** integers. You need to find a subsequence of length $K$ with the maximum possible median.
The median of a sequence is the value of the element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is selected. For example, if the sequence is $[3, 4, 2, 1, 5]$, then the median is $3$ since after sorting, it will look like $[1, 2, 3, 4, 5]$ and $3$ is the only middle element. The median of $[4, 2, 1, 5]$ is $2$ since after sorting, the value $2$ is the left of the two middle elements $2$ and $4$.
A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, if the sequence is $[2, 1, 4, 5, 7]$, then $[1, 5, 7]$, $[2, 1, 4]$, $[5]$ are some valid subsequences but $[4, 1, 2]$, $[1, 6, 7]$ are not.
<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>