小学的校长准备找一辆大巴，这样老师们就可以带着大家去郊游了。
如果大巴的油箱容量是 $m$，那么在满油的状态下大巴可以开 $m$ 公里。
郊游的路线是一个环，上面有 $n$ 个目标点，第 $i$ 个目标点到第 $i+1$ 个目标点（如果 $i=n$ 的话就是到第 $1$ 个地点） 的距离为 $l_i$ 公里。
校长可以任意确定大巴的起点，然后大巴会绕这个环一圈，最后回到起点结束。
在路上有可能大巴需要加油，大巴可以在任意一个目标点加油。为了不打扰同学们的旅行，法珞希望加油的次数尽可能少。
校长有 $k$ 种可选的大巴，第 $i$ 个大巴的油箱容量是 $m_i$。对于每一种大巴，校长想知道，它是否能完成这次旅行（不会在半路没油），如果能的话，最少需要加多少次油。
输入格式
第一行两个整数 $n,k$。
第二行 $n$ 个整数 $l_i$。
第三行 $k$ 个整数 $m_i$。
输出格式
对于每一种大巴，如果它不能到达终点，输出 "Invalid"（不含引号） ，否则输出最少的加油次数。
样例一
input
6 4
2 2 1 3 3 1
3 2 4 11output
4
Invalid
3
2样例二
见样例数据下载
限制与约定
对于 $20\texttt{%}$ 的数据，$1 \le n \le 1000$。
对于另外 $20\texttt{%}$ 的数据，$1 \le k \le 5$。
对于另外 $20\texttt{%}$ 的数据，$1 \le n \le 10^5$。
对于 $100\texttt{%}$ 的数据，$1 \le n \le 10^6$，$1 \le k \le 100$，$1 \le m_i,\sum l_i \le 10^9$。
时间限制：$4\texttt{s}$
空间限制：$512\texttt{MB}$
