Description

After striving for many years, Byteasar has finally obtained a pilot license. To celebrate, he intends to buy an airplane and fly around the planet 3-SATurn (where Byteotia is located), specifically along the equator. The equator is long, so refueling is necessary.

There are airports along the equator, and a plane can refuel when it lands at one. Each airplane model has a known flight range on a full tank. Byteasar is considering several different models, which naturally differ in flight range. For each model, determine the minimum number of landings (including the final one) needed to complete a full lap along the equator, starting at an airport of choice. If it is impossible to complete the journey with a given model, report that as well. Note that the starting airport may be chosen independently for each model.

Input Format

The first line contains two integers $n$ and $s$ ($2 \le n \le 1\,000\,000$, $1 \le s \le 100$), separated by a single space, denoting the number of airports along the equator and the number of airplane models Byteasar is considering.

The second line contains $n$ positive integers $l_1, l_2, \cdots, l_n$ ($l_1 + l_2 + \cdots + l_n \le 10^9$), separated by single spaces, specifying the distances between successive airports along the equator. The number $l_i$ is the distance between the $i$-th and $(i+1)$-st airports (or between the $n$-th and the first if $i = n$), in kilometers.

The third line contains $s$ integers $d_1, d_2, \cdots, d_s$ ($1 \le d_i \le l_1 + l_2 + \cdots + l_n$), separated by single spaces. The number $d_i$ is the $i$-th airplane model’s flight range in kilometers, i.e., the maximum distance it can fly before landing and refueling.

Output Format

Print $s$ lines. The $i$-th line should contain a single integer, namely, the minimum number of flight segments (and thus also landings) necessary to fly the $i$-th airplane around the planet 3-SATurn along the equator, starting at an airport of choice, or the word NIE (Polish for “no”) if it is impossible to complete the journey with this airplane.

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

4
NIE
3
2

Hint

After several years of effort, Byteasar finally obtained a pilot license. To celebrate, he plans to buy an airplane and fly a lap around the equator of the planet Byteotia. Unfortunately, the equator is very long, so he needs to refuel en route. All airports along the equator are known, and an airplane can refuel when it lands at an airport. Because buying an airplane is a major decision, Byteasar seeks your help. He will ask you to simulate different flight routes. Naturally, different airplanes have different ranges per full tank. For each simulation, he wants to know the minimum number of landings required (including the final one). Note that the starting point can be chosen arbitrarily.

Translated by ChatGPT 5