题目描述

通过几年的努力，Byteasar 最终拿到了飞行员驾驶证。为了庆祝这一事实，他打算买一架飞机并且绕 Byteotia 星球赤道飞行一圈。但不幸的是赤道非常长所以需要中途加几次油。现在已知赤道上面所有飞机场，所有飞机从飞机场起飞降落也可以加油。因为买飞机是个十分重大的决定，Byteasar 决定寻求你的帮助。他将会让你模拟不同的飞行路线。自然这些飞机一次能走的航程是不同的。对于每次模拟，他想要知道最少需要降落多少次（包括最后一次）。需要注意的是起点可以任意选取。

输入格式

第一行包含两个整数 $n$ 和 $s$（$2\le n\le 1\ 000\ 000$，$1\le s\le 100$），用一个空格隔开，分别表示赤道上的机场数量和 Byteasar 正在考虑的飞机型号数量。

第二行包含 $n$ 个正整数 $l_1,l_2,\cdots,l_n$（$l_1+l_2+\cdots+l_n\le 10^9$），用单个空格隔开，表示赤道上相邻机场之间的距离。

其中 $l_i$ 表示第 $i$ 个机场到第 $(i+1)$ 个机场的距离（若 $i=n$，则表示第 $n$ 个机场到第 $1$ 个机场的距离），单位为千米。

第三行包含 $s$ 个整数 $d_1,d_2,\cdots,d_s$（$1\le d_i\le l_1+l_2+\cdots+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