For a multiset $S = \{x_0, x_1, \ldots, x_{m-1}\}$ of size $m$, let its elements sorted in non-increasing order be $y_0 \ge y_1 \ge \cdots \ge y_{m-1}$. Define its median $\operatorname{Median}(S)$ as its $\lceil m/2 \rceil$-th largest element, namely $\operatorname{Median}(S) = y_{\lceil m/2 \rceil-1}$. Note: the definition of median in this problem may differ from the usual definition.

You are given a sequence $[a_0, a_1, \ldots, a_{n-1}]$ of length $n$ and a positive integer $k$ ($k \le n$). A partition is defined as follows: choose a strictly increasing sequence of $k-1$ indices $0 < b_1 < \cdots < b_{k-1} < n$. This divides the original sequence into $k$ segments, whose index intervals are $[0,b_1), [b_1,b_2), \ldots, [b_{k-1},n)$, respectively.

Define the balance of a partition as follows. For each segment, compute the median of the multiset formed by all its elements. The median of the multiset formed by these $k$ medians is the balance of the partition. Formally, for a partition $b_1, \ldots, b_{k-1}$, let $b_0 = 0$ and $b_k = n$. Let the median of the multiset of all elements in segment $i$ ($0 \le i < k$) be $c_i = \operatorname{Median}(\{a_{b_i}, a_{b_i+1}, \ldots, a_{b_{i+1}-1}\})$. The balance of this partition is $\operatorname{Median}(\{c_0, \ldots, c_{k-1}\})$.

Find the maximum balance over all partitions.

Implementation Details

You do not need to, and should not, implement the main function.

Ensure that your submitted source file includes the header median.h, by adding the following code at the beginning of your program:

#include "median.h"

Implement the following two functions in your submitted source file median.cpp:

void init(int c, int t);

• $c$ and $t$ denote the test point number and the number of test cases, respectively. $c = 0$ means that the test point is an example.
• For each test point, this function is called by the grader exactly once when the program starts running.

int median(int n, int k, std::vector<int> a);

• $n$, $k$, and $a$ denote the sequence length, the number of segments in the partition, and the given sequence, respectively.
• This function must return the maximum balance.
• For each test point, this function is called by the grader exactly $t$ times.

The file template_median.cpp in this problem's directory provides example code. You may refer to it when implementing your own code.

Testing Your Program

You can use the following command in this problem's directory to compile your program into an executable:

g++ grader.cpp median.cpp -o median -O2 -std=c++14 -static

For the resulting executable median:

• The executable reads data from standard input in the following format:

  • The first line contains two non-negative integers $c$ and $t$.

  • The test cases follow in order. For each test case:

    • The first line contains two positive integers $n$ and $k$.
    • The second line contains $n$ positive integers $a_0, a_1, \ldots, a_{n-1}$.

• The executable writes data to standard output in the following format:

  • For each test case, output one line containing a positive integer: the maximum balance.

Examples

Input 1

0 2
10 4
6 5 1 9 2 3 10 7 4 8
10 5
5 7 3 10 8 2 9 1 6 4

Output 1

9
8

Note

For the first test case, one partition attaining the maximum balance is $b_1 = 3$, $b_2 = 5$, $b_3 = 7$. It divides the original sequence into four segments $[6,5,1]$, $[9,2]$, $[3,10]$, $[7,4,8]$, whose element medians are $5,9,10,7$, respectively. Therefore, the balance of this partition is $\operatorname{Median}(\{5,9,10,7\}) = 9$.

For the second test case, one partition attaining the maximum balance is $b_1 = 2$, $b_2 = 4$, $b_3 = 6$, $b_4 = 8$. It divides the original sequence into five segments $[5,7]$, $[3,10]$, $[8,2]$, $[9,1]$, $[6,4]$, whose element medians are $7,10,8,9,6$, respectively. Therefore, the balance of this partition is $\operatorname{Median}(\{7,10,8,9,6\}) = 8$.

Example 2

See median/median2.in and median/median2.ans in the contestant directory.

This example satisfies the constraints of test point $6$.

Example 3

See median/median3.in and median/median3.ans in the contestant directory.

This example satisfies the constraints of test point $9$.

Example 4

See median/median4.in and median/median4.ans in the contestant directory.

This example satisfies the constraints of test point $14$.

Example 5

See median/median5.in and median/median5.ans in the contestant directory.

This example satisfies the constraints of test points $18$ through $20$.

Constraints

Let $N$ be the sum of $n$ over all test cases in a single test point. For all test cases:

• $1 \le t \le 20$;
• $5 \le n \le 10^6$, $2 \le k \le n$, $N \le 10^6$;
• For every $0 \le i < n$, $1 \le a_i \le n$.

Special property A: for every $0 \le i < n$, $a_i \le 2$.