Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3295
War of 218

Time Limit: 1 Second      Memory Limit: 32768 KB

There're 2N (1 <= N <= 10) QSes fighting for the job of admin in 218. It's hard for Fire to select who to be the admin, so he holds up a strange contest.

Before the contest, each QS has a skill value Vi (Vi varies from person to person). And there's N rounds in the contest, that means they play single elimination rounds (refer to Single Elimination Tournament) in pairs. Moreover, ith QS beat the jth QS down, if and only if Vi > Vj.

Please help the Kth (0 <= K < 2N) QS to calculate the minimum and the maximum he/she can win.

Input

There're multiple test cases.

For each test case, there're two integers N, K in the first line, then 2N positive integers in the second line indicating V1, ..., V2N, and all of the skill values are less than 231.

Output

For each test case, output two integers indicating the minimal and the maximal number of wins that the Kth player can achieve.

Sample Input

2 1
7 5 3 6

Sample Output

0 1

Author: OUYANG, Jialin
Source: ZOJ Monthly, January 2010
Submit    Status