题目描述

题目译自 XXI Olimpiada Informatyczna — III etap Dookoła świata

Bajtazar 历经多年努力，终于拿到了梦寐以求的飞行执照！他兴奋地决定买架飞机，沿赤道环游字节城所在的 3-SATurn 星球，飞越每一个赤道点。然而，飞机需要加油是个大麻烦。每架飞机的满油飞行距离已知，只能在赤道上的机场加油，且必须降落。

买飞机可不是小事，Bajtazar 向你求助。他列出了不同型号的飞机，油箱容量各异。请你为每种型号计算环游世界所需的最少降落次数（包括最后降落）。每次旅行可从任意机场起飞。

输入格式

输入第一行包含两个整数 $n, s$ $(2 \leq n \leq 1000000, 1 \leq s \leq 100)$，分别表示赤道上机场数量和 Bajtazar 考虑购买的飞机型号数。

第二行包含 $n$ 个正整数 $l_1, l_2, \ldots, l_n$ $(l_1 + l_2 + \ldots + l_n \leq 10^9)$，$l_i$ 表示第 $i$ 个机场到第 $i+1$ 个机场（若 $i=n$，则到第 $1$ 个机场）的距离（公里）。

第三行包含 $s$ 个整数 $d_1, d_2, \ldots, d_s$ $(1 \leq d_i \leq l_1 + l_2 + \ldots + l_n)$，$d_i$ 表示第 $i$ 种飞机满油可飞行的距离（公里）。

输出格式

输出 $s$ 行，第 $i$ 行包含一个整数，表示第 $i$ 种飞机环游 3-SATurn 赤道的最少飞行次数（从任意机场起飞），若无法完成环游输出 NIE。

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

4
NIE
3
2

图中粗实线表示油箱容量为 $4$ 的飞机的最佳路线，需 $4$ 次降落；虚线表示容量为 $3$ 的飞机的路线，需 $3$ 次降落。

附加样例

1. $n=8, s=3$，小型测试，覆盖多种边界情况；
2. $n=24, s=8$，每相邻两个机场距离为 $1$；
3. $n=1000000, s=100$，最大规模测试。

数据范围与提示

对于 $20\%$ 的数据，$n \leq 1000$。
对于 $50\%$ 的数据，$n \leq 100000$。
对于另外 $18\%$ 的数据，$s \leq 5$。