Ivar the Boneless is a great leader. He is trying to capture Kattegat from Lagertha. The war has begun and wave after wave Ivar's warriors are falling in battle.

Ivar has $n$ warriors, he places them on a straight line in front of the main gate, in a way that the $i$-th warrior stands right after $(i-1)$-th warrior. The first warrior leads the attack.

Each attacker can take up to $a_i$ arrows before he falls to the ground, where $a_i$ is the $i$-th warrior's strength.

Lagertha orders her warriors to shoot $k_i$ arrows during the $i$-th minute, the arrows one by one hit the first still standing warrior. After all Ivar's warriors fall and all the currently flying arrows fly by, Thor smashes his hammer and all Ivar's warriors get their previous strengths back and stand up to fight again. In other words, if all warriors die in minute $t$, they will all be standing to fight at the end of minute $t$.

The battle will last for $q$ minutes, after each minute you should tell Ivar what is the number of his standing warriors.


-----Input-----

The first line contains two integers $n$ and $q$ ($1 \le n, q \leq 200\,000$) — the number of warriors and the number of minutes in the battle.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) that represent the warriors' strengths.

The third line contains $q$ integers $k_1, k_2, \ldots, k_q$ ($1 \leq k_i \leq 10^{14}$), the $i$-th of them represents Lagertha's order at the $i$-th minute: $k_i$ arrows will attack the warriors.


-----Output-----

Output $q$ lines, the $i$-th of them is the number of standing warriors after the $i$-th minute.


-----Examples-----
Input
5 5
1 2 1 2 1
3 10 1 1 1

Output
3
5
4
4
3

Input
4 4
1 2 3 4
9 1 10 6

Output
1
4
4
1



-----Note-----

In the first example:   after the 1-st minute, the 1-st and 2-nd warriors die.  after the 2-nd minute all warriors die (and all arrows left over are wasted), then they will be revived thus answer is 5 — all warriors are alive.  after the 3-rd minute, the 1-st warrior dies.  after the 4-th minute, the 2-nd warrior takes a hit and his strength decreases by 1.  after the 5-th minute, the 2-nd warrior dies.

Difficulty: interview

Starter code:

Solutions:
from itertools import accumulate
from bisect import bisect_right
import sys

n, q = list(map(int, sys.stdin.readline().split()))
a = list(map(int, sys.stdin.readline().split()))
k = list(map(int, sys.stdin.readline().split()))

s = list(accumulate(a))

sofar = 0
for x in k:
    sofar += x
    if sofar >= s[-1]:
        sofar = 0
    sys.stdout.write(str(n - bisect_right(s, sofar)) + '\n')


import sys
import math
import bisect
import itertools

n,q = list(map(int,sys.stdin.readline().strip().split(' ')))
a = list(map(int,sys.stdin.readline().strip().split(' ')))
prefix_sum = list(itertools.accumulate(a))
k = list(map(int,sys.stdin.readline().strip().split(' ')))

k_sum = 0
for q0 in range(q):
	k_sum += k[q0]
	idx = bisect.bisect_left(prefix_sum, k_sum)
	if idx < n and prefix_sum[idx] == k_sum:
		idx += 1
	if idx == n:
		print(n)
		k_sum = 0
	else:
		print(n-idx)


from bisect import bisect_right

N, Q = map(int, input().split())
A = list(map(int, input().split()))
K = list(map(int, input().split()))

for i in range(1, N):
    A[i] += A[i-1]

ans = []
plus = 0
for q in range(Q):
    idx = bisect_right(A, K[q]+plus)
    if idx == N:
        ans.append(N)
        plus = 0
    else:
        ans.append(N-idx)
        plus += K[q]

for q in range(Q):
    print(ans[q])

import bisect

N,Q = list(map(int,input().split()))
ws = list(map(int,input().split()))
qs = list(map(int,input().split()))

cums = [0]
for w in ws:
    cums.append(cums[-1] + w)

damage = 0
for q in qs:
    damage += q
    if damage >= cums[-1]:
        damage = 0
        print(N)
    else:
        i = bisect.bisect(cums,damage)
        print(N-i+1)


import bisect

n, q = list(map(int, input().split()))
a, k, curA, curK = [], [], 0, 0

for s in input().split():
    curA += int(s)
    a.append(curA)

for s in input().split():
    curK += int(s)
    index = bisect.bisect(a, curK)

    if index == n:
        print(n)
        curK = 0
    else:
        print(n - index)
    


from bisect import bisect
n,q=map(int,input().split())
a=list(map(int,input().split()))
a.reverse()
s=sum(a)
for i in range(1,n):
	a[i]+=a[i-1]
k=list(map(int,input().split()))
tmp=0
for i in range(q):
	tmp+=k[i]
	if tmp>=s: tmp=0
	print(bisect(a,s-tmp-1)+1)

import bisect

n, q = [int(v) for v in input().split()]
va = [int(v) for v in input().split()]
vk = [int(v) for v in input().split()]

for i in range(1, n):
    va[i] += va[i - 1]

ans = []
curr = 0
for k in vk:
    curr += k
    it = bisect.bisect_right(va, curr)
    if it == n:
        ans.append(n)
        curr = 0
    else:
        ans.append(n - it)

print('\n'.join(str(v) for v in ans))


from bisect import bisect_right as br

n, q = list(map(int, input().split()))
stn = list(map(int, input().split()))
arro = list(map(int, input().split()))

cum = []
s = 0
for i in range(n):
    s += stn[i]
    cum.append(s)

s1 = 0
ans = 0
for i in range(q):
    if ans == 0:
        s1 = arro[i]
    else:
        s1 += arro[i]
    ind = br(cum, s1)
    ans = n - ind
    if ans == 0:
        print(n)
    else:
        print(ans)
    


# -*- coding: utf-8 -*-
"""
Created on Fri Apr 27 00:39:17 2018

@author: shubham
"""
def Low(a, l, r, x):
    while l<r:
        mid = (l+r)//2
        if a[mid] >= x:
            r = mid
        else:
            l = mid+1
    if a[l]<=x:
        return l
    else:
        return l-1


n, q = list(map(int, input().split()))
a = list(map(int, input().split()))
k = list(map(int, input().split()))
p = [0]*n
p[0] = a[0]
for i in range(1, n):
    p[i]=p[i-1]+a[i]
t = 0
for i in range(q):
    t+=k[i]
    ans = Low(p, 0, n-1, t)
    if ans == -1 or ans == n-1:
        print(n)
    else:
        print(n-ans-1)
    if ans == n-1:
        t = 0
    


from bisect import bisect_left
from itertools import accumulate

n,q = input().split()

n = int(n)
q = int(q)

a = list(map(int, input().split()))
k = list(map(int, input().split()))

reqArrows = sum(a)
prevArrows = 0
accuA = list(accumulate(a))
accuK = list(accumulate(k))

for i in range(q):
	prevArrows += k[i]
	if prevArrows >= reqArrows:
		print(n)
		prevArrows = 0
	else:
		x = bisect_left(accuA,  prevArrows)
		if accuA[x] == prevArrows:
			print(n-x-1)
		else:
			print(n-x)

import bisect

def find_ge(a, key):
    '''Find smallest item greater-than or equal to key.
    Raise ValueError if no such item exists.
    If multiple keys are equal, return the leftmost.
    '''
    i = bisect.bisect_left(a, key)
    if i == len(a):
        return -1
    return i

n, q = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
k = [int(x) for x in input().split()]
result = [0] * (q+1)
result[0] = n
s = [0]*n
s[0] = a[0]
for i in range(1, n):
    s[i] = s[i-1] + a[i]

remain = 0
attack = 0
for i in range(1, q + 1):
    attack += k[i-1]

    ge = find_ge(s, attack)

    if ge >= 0:
        remain = s[ge] - attack
        #print(remain, s[ge], i)
        if remain > 0: result[i] = n-ge
        else: result[i] = n-ge-1
        if result[i] == 0:
            result[i] = n
            attack = 0
    else:
        result[i] = n
        attack = 0
        remain = 0
    '''
    else:
        # all soldiers died
        remain -= k[i-1]
        attack = 0
        if remain > 0: result[i] = n-ge
        else: result[i] = n-ge-1
    '''

print('\n'.join(str(x) for x in result[1:]))


import bisect

n,q=list(map(int,input().split()))
a=list(map(int,input().split()))
s=[0,]
for i in a:
    s.append(s[-1]+i)

k=list(map(int,input().split()))
tb=0
for i in range(q):
    tb+=k[i]
    if tb>=s[-1]:
        tb=0
        print(n)
    else:
        ans=bisect.bisect_right(s,tb)
        print(n-ans+1)


#!/usr/bin/env python3

import bisect

[n, q] = list(map(int, input().strip().split()))
ais = list(map(int, input().strip().split()))
kis = list(map(int, input().strip().split()))

iais = [0 for _ in range(n + 1)]
for i in range(n):
	iais[i + 1] = iais[i] + ais[i]


def bsearch(v, xmin, xmax):
	while xmax - xmin > 1:
		xmid = (xmin + xmax) // 2
		if v >= iais[xmid]:
			xmin = xmid
		else:
			xmax = xmid
	return xmin

def lsearch(v, xmin, xmax):
	x = xmin
	while x + 1 < xmax and v >= iais[x + 1]:
		x += 1
	return x

thrs = (iais[-1] // n + 1) * 440



s = 0
tot = iais[-1]
prevr = 0
for k in kis:
	s += k
	if s >= tot:
		print (n)
		s = 0
		prevr = 0
	else:
		r = bisect.bisect_right(iais, s, prevr) - 1
		print(n - r)
		prevr = r



#!/usr/bin/env python3

import bisect

[n, q] = list(map(int, input().strip().split()))
ais = list(map(int, input().strip().split()))
kis = list(map(int, input().strip().split()))

iais = [0 for _ in range(n + 1)]
for i in range(n):
	iais[i + 1] = iais[i] + ais[i]


s = 0
tot = iais[-1]
r = 0
for k in kis:
	s += k
	if s >= tot:
		print (n)
		s = 0
		r = 0
	else:
		r = bisect.bisect_right(iais, s, r) - 1
		print(n - r)



from itertools import accumulate

from math import inf


def sum(p):
    return h[p] - h[ind] + val


def check(p):
    return sum(p) >= el


def binSearch(a, b):
    left, right = a - 1, b + 1

    while right - left > 1:
        mid = (left + right) // 2

        if check(mid):
            right = mid
        else:
            left = mid

    return right


n, q = list(map(int, input().split()))
a = list(map(int, input().split()))
k = list(map(int, input().split()))

h = [0] + list(accumulate(a)) + [inf]

ind = 1
val = a[0]

ans = list()
for i, el in enumerate(k):

    if el < val:
        val -= el

        ans.append(n + 1 - ind)

    elif el == val:
        ind += 1

        if ind == n + 1:
            ind = 1
            val = a[0]
            ans.append(n)

        else:
            val = a[ind - 1]
            ans.append(n + 1 - ind)

    else:
        b = binSearch(ind, n)

        delta = sum(b) - el

        if b == n + 1:
            ans.append(n)
            ind = 1
            val = a[0]

        elif delta == 0:
            ind = b + 1

            if ind == n + 1:
                ind = 1
                val = a[0]
                ans.append(n)

            else:
                val = a[ind - 1]
                ans.append(n + 1 - ind)

        else:
            ind = b
            val = delta
            ans.append(n + 1 - ind)

print('\n'.join(map(str, ans)))


import bisect

n,q = list(map(int, input().split()))
warrior = list(map(int, input().split()))
attacker = list(map(int, input().split()))
warriors_new = []
sm = 0
for i in warrior:
    sm+=i
    warriors_new.append(sm)
query = 0
ans = 0
for i in attacker:
    query+=i
    if query>=warriors_new[n-1]:
        query = 0
        ans = 0
    else:
        ans = bisect.bisect_right(warriors_new,query,ans)
    print(n-ans)


n, q = map(int, input().split())
a = list(map(int, input().split()))
k = list(map(int, input().split()))

def bins(arr, start, end, v):
    # find index of biggest value less than or equal to v
    s, e = start, end
    result = -1
    
    while s < e:
        m = (s + e) // 2

        if arr[m] >= v:
            e = m
        else:
            result = m
            s = m + 1

    return s if a[s] <= v else s - 1

for i in range(1, len(a)):
    a[i] += a[i - 1]

# arrow strength
s = 0
result = []

for ki in k:
    s += ki

    standing = n - bins(a, 0, len(a) - 1, s) - 1

    if standing > 0:
        result.append(standing)
    else:
        result.append(n)

    if s >= a[-1]:
        s = 0

print('\n'.join(map(str, result)))

n, q = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
K = [int(i) for i in input().split()]

A = a[:]
for i in range(1, n):
    A[i] += A[i-1]

def bs(A, key):
    lo, hi = 0, len(A)-1
    while lo <= hi:
        mid = (lo+hi) // 2
        if A[mid] == key:
            # print(A)
            # print(f'Found key = {key} *exactly* at mid = {mid}')
            return mid
        elif key < A[mid]:
            hi = mid-1
        elif A[mid] < key:
            lo = mid+1
    # print(A)
    # print(f'hi={hi} > lo={lo}. Returning hi')
    return hi

D = 0
for i in range(q):
    D += K[i]
    # print(f'Accumulated damage = {D}')
    j = bs(A, D)
    if j == n-1:
        # print('Resetting damage')
        D = 0
        j = -1
    print(n-(j+1))


from bisect import bisect as bs
n, q = map(int, input().split())
a = list(map(int, input().split()))
k = list(map(int, input().split()))
tmp = 0
sumA = []
for i in range(n):
    tmp += a[i]
    sumA.append(tmp)
# print(sumA)


def bin_search(left, right, v):
    if left > right:
        return left
    mid = (left + right) // 2
    if sumA[mid] == v:
        return mid
    elif sumA[mid] < v:
        return bin_search(mid+1, right, v)
    else:
        return bin_search(left, mid-1, v)



now = 0

ansList = []

for i in range(q):
    now += k[i]
    ans_id = bs(sumA, now)
    if ans_id == n:
        now = 0
        ans_id = 0
    ansList.append(n-ans_id)

print("\n".join(map(str, ansList)))