Problem D: 卡牌游戏 II

Problem D: 卡牌游戏 II

Time Limit: 4 Sec  Memory Limit: 128 MB
Submit: 33  Solved: 3
[Submit][Status][Web Board]

Description

菜哭武最近得到了一套卡牌,每天都喜欢拉着自己的同事们做一些游戏。这次,他拿出了N张,上面印着整数的卡牌,上面的数字依次是a1,a2,a3……an

他知道,从这里面取任意多张牌,一共有2N种方法,除了什么都不取的那一种,其他的可以计算出这些卡牌上面数字的和,现在他想知道,这2N-1种方法里,数字和最小的K种都是多少。希望你能帮帮他啊。

Input

题目包含多组数据。

输入的第一行有一个整数T (1≤T≤10) 代表有T组数据。

对于每组数据分为两行:          

第一行有两个整数NK (其中1≤N≤200000, 1≤K≤min2N-1, 200000 )

第二行有N个整数,分别是a1,a2,a3……an (-108ai108)

Output

对于每组数据,输出的第一行为Case #x: ,其中x是数据编号(从1开始),

第二行输出一个非负整数,为正常需要输出的K的数字的和 Mod 99989的结果。

Sample Input

2
2 1 
1 1 
3 3
-1 0 1

Sample Output

Case #1:
1
Case #2:
99987

HINT


本题因为输出较大,在OJ评测会出现输出超限的问题,现场赛时采用了手工评测。现在已修改输出格式,请各位注意。 

[Submit][Status]