经过多年的努力，Byteasar 终于拿到了飞行执照。为了庆祝，他打算买一架飞机，绕着 3-SATurn 行星（正如你所猜到的，这是 Byteotia 所在的行星）飞行。具体来说，Byteasar 计划沿着赤道飞行。不幸的是，赤道相当长，需要中途加油。每种飞机的航程（满油状态下）都是已知的。赤道沿途有若干个机场，飞机降落在机场时可以加油。由于购买飞机是一个重大决定，Byteasar 请求你的帮助。他准备向你提供一份他正在考虑的不同飞机型号的列表。自然地，它们的航程各不相同。对于每种飞机型号，他想知道为了完成旅程，他必须进行的最少降落次数（包括最后一次降落）。注意，对于每种飞机型号，旅程可以从任意一个机场开始。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $s$ ($2 \le n \le 1\,000\,000$, $1 \le s \le 100$)，由单个空格分隔，分别表示赤道上的机场数量和 Byteasar 正在考虑的飞机型号数量。

第二行包含 $n$ 个正整数 $l_{1},l_{2},\dots,l_{n}$ ($l_{1}+l_{2}+\dots+l_{n} \le 10^{9}$)，由单个空格分隔，指定了赤道上相邻机场之间的距离。数字 $l_{i}$ 表示第 $i$ 个机场与第 $i+1$ 个机场（若 $i=n$ 则为第 $n$ 个机场与第 $1$ 个机场）之间的距离，单位为千米。

第三行包含 $s$ 个整数 $d_{1},d_{2},\dots,d_{s}$ ($1 \le d_{i} \le l_{1}+l_{2}+\dots+l_{n}$)，由单个空格分隔。数字 $d_{i}$ 表示第 $i$ 种飞机型号的航程（单位为千米），即在降落加油前能飞行的最大距离。

在总分占比 $50\%$ 的测试点中，$n \le 100\,000$，其中占比 $20\%$ 的子任务满足 $n \le 1\,000$。

在另一个与上述测试点不相交的子任务中，占比 $18\%$，满足 $s \le 5$。

输出格式

你的程序应向标准输出打印 $s$ 行：第 $i$ 行应包含一个整数，即使用第 $i$ 种飞机沿赤道绕 3-SATurn 行星飞行一圈所需的最少飞行段数（即降落次数），起点机场可由你选择；如果该飞机无法完成旅程，则输出 NIE（波兰语，意为“不”）。

样例

输入 1

6 4
2 2 1 3 3 1
3 2 4 11

输出 1

4
NIE
3
2

粗实线显示了航程为 4 的飞机的最优航程，虚线显示了航程为 3 的飞机的最优航程。