题目描述

给定一个序列 $a_1,a_2,…,a_n$，从中找出恰好 $k$ 个不相交的连续子段，满足每一段的长度都是质数。假设其中第 $i$ 个子段的子段和是 $s_i$，你需要最大化 $\min(s_1,s_2,…,s_k)$。

输入格式

第一行包含一个正整数 $T$ ($1≤T≤100$)，表示测试数据的组数。

每组数据第一行包含两个正整数 $n,k$ ($2≤n≤200000, 1≤k≤n$)。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$ ($|a_i|≤1000$)。

输入数据保证 $∑n≤10^6$，且每个 $a_i$ 都是在 $[−1000,1000]$ 均匀随机生成得到（样例除外）。

输出格式

对于每组数据输出一行：若存在合法方案，输出一个整数，即 $\min(s_1,s_2,…,s_k)$ 的最大可能值；若无解，输出 $\text{impossible}$。

输入样例

4
6 1
1 1 4 5 1 4
6 1
-1 -1 -4 -5 -1 -4
6 3
-1 -1 -4 -5 -1 -4
2 2
0 0

输出样例

15
-2
-9
impossible