Eugeny loves listening to music. He has n songs in his play list. We know that song number i has the duration of t_{i} minutes. Eugeny listens to each song, perhaps more than once. He listens to song number i c_{i} times. Eugeny's play list is organized as follows: first song number 1 plays c_1 times, then song number 2 plays c_2 times, ..., in the end the song number n plays c_{n} times.

Eugeny took a piece of paper and wrote out m moments of time when he liked a song. Now for each such moment he wants to know the number of the song that played at that moment. The moment x means that Eugeny wants to know which song was playing during the x-th minute of his listening to the play list.

Help Eugeny and calculate the required numbers of songs.


-----Input-----

The first line contains two integers n, m (1 ≤ n, m ≤ 10^5). The next n lines contain pairs of integers. The i-th line contains integers c_{i}, t_{i} (1 ≤ c_{i}, t_{i} ≤ 10^9) — the description of the play list. It is guaranteed that the play list's total duration doesn't exceed 10^9 $(\sum_{i = 1}^{n} c_{i} \cdot t_{i} \leq 10^{9})$.

The next line contains m positive integers v_1, v_2, ..., v_{m}, that describe the moments Eugeny has written out. It is guaranteed that there isn't such moment of time v_{i}, when the music doesn't play any longer. It is guaranteed that v_{i} < v_{i} + 1 (i < m).

The moment of time v_{i} means that Eugeny wants to know which song was playing during the v_{i}-th munite from the start of listening to the playlist.


-----Output-----

Print m integers — the i-th number must equal the number of the song that was playing during the v_{i}-th minute after Eugeny started listening to the play list.


-----Examples-----
Input
1 2
2 8
1 16

Output
1
1

Input
4 9
1 2
2 1
1 1
2 2
1 2 3 4 5 6 7 8 9

Output
1
1
2
2
3
4
4
4
4

Difficulty: EASY
Tags: Sorting

Amortized analysis

Implementation
Skill types: Sorting

Amortized analysis

Starter code:

Solutions:
from bisect import bisect_left as b
(n, m) = map(int, input().split())
lis = [0]
cur = 0
for _ in range(n):
	(c, t) = map(int, input().split())
	cur += c * t
	lis.append(cur)
v = list(map(int, input().split()))
for i in v:
	print(b(lis, i))


(n, m) = list(map(int, input().split()))
arr = []
for i in range(n):
	(c, t) = list(map(int, input().split()))
	arr.append(c * t)
(i, p) = (0, 0)
v = [int(x) for x in input().split()]
for j in v:
	while p < j:
		(p, i) = (p + arr[i], i + 1)
	print(i)


import sys
import string
from collections import Counter, defaultdict
from math import fsum, sqrt, gcd, ceil, factorial
from operator import *
from itertools import accumulate
from bisect import *
inf = float('inf')
flush = lambda : sys.stdout.flush
comb = lambda x, y: factorial(x) // factorial(y) // factorial(x - y)
en = lambda x: list(enumerate(x))
ip = lambda : input()
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
(n, k) = r()
arr = [rr() for _ in range(n)]
brr = rr()
crr = [0]
for (i, j) in arr:
	crr += (crr[-1] + i * j,)
for i in brr:
	print(bisect(crr, i - 1))


(n, m) = map(int, input().split())
lol = []
mem = 0
for i in range(n):
	(c, t) = map(int, input().split())
	mem += c * t
	lol.append(mem)
v = list(map(int, input().split()))
for k in v:
	l = 0
	r = n - 1
	if k <= lol[0]:
		print(1)
	else:
		while l < r - 1:
			s = (l + r) // 2
			if lol[s] < k:
				l = s
			else:
				r = s
		print(r + 1)


from bisect import bisect_left as bs
(n, m) = map(int, input().split())
a = [0]
for i in range(1, n + 1):
	(c, t) = map(int, input().split())
	a.append(c * t + a[i - 1])
v = map(int, input().split())
for i in v:
	print(bs(a, i))


(n, m) = map(int, input().split())
v = [0 for i in range(n + 1)]
for i in range(1, n + 1):
	(c, t) = map(int, input().split())
	v[i] = c * t + v[i - 1]
mi = [int(i) for i in input().split()]
for i in mi:
	l = 1
	r = n + 1
	while l < r:
		mid = (l + r) // 2
		if i > v[mid]:
			l = mid + 1
		else:
			r = mid
	print(l)


(n, j) = map(int, input().split())
songs = []
for i in range(n):
	(c, t) = map(int, input().split())
	songs.append(c * t)
moments = map(int, input().split())
time = 0
song = 0
for m in moments:
	while time < m:
		time += songs[song]
		song += 1
	print(song)


I = lambda : [int(i) for i in input().split()]
(n, m) = I()
l = []
temp = I()
l.append(temp[0] * temp[1])
for _ in range(1, n):
	k = I()
	l.append(l[_ - 1] + k[0] * k[1])
s = I()
j = 0
for i in s:
	if i < l[j]:
		print(j + 1)
	else:
		while i > l[j]:
			j += 1
		print(j + 1)


(n, m) = map(int, input().split())
nmus = []
tmus = []
ultimo = 0
for i in range(n):
	(c, t) = map(int, input().split())
	nmus.append(i)
	if i == 0:
		tmus.append(c * t)
	else:
		tmus.append(c * t + tmus[i - 1])
momentos = input().split()
for i in range(m):
	for j in range(ultimo, n + 1):
		if int(momentos[i]) <= int(tmus[j]):
			print(j + 1)
			ultimo = j
			break


(n, m) = map(int, input().split())
d = []
for i in range(n):
	(a, b) = map(int, input().split())
	d.append(a * b)
x = list(map(int, input().split()))
(a, b) = (0, 0)
s = 0
while b != len(x):
	if s + d[a] >= x[b]:
		print(a + 1)
		b += 1
	else:
		s += d[a]
		a += 1


import math
import itertools
import collections

def getdict(n):
	d = {}
	if type(n) is list:
		for i in n:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	else:
		for i in range(n):
			t = ii()
			if t in d:
				d[t] += 1
			else:
				d[t] = 1
	return d

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def wr(arr):
	return ' '.join(map(str, arr))

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def revn(n):
	m = 0
	while n > 0:
		m = m * 10 + n % 10
		n = n // 10
	return m
(n, m) = mi()
(c, t) = mi()
pl = [0] * n
pl[0] = c * t
for i in range(1, n):
	(c, t) = mi()
	pl[i] += pl[i - 1] + c * t
v = li()
j = 0
for i in range(m):
	while v[i] > pl[j]:
		j += 1
	print(j + 1)


entrada1 = list(map(int, input().split()))
n = entrada1[0]
m = entrada1[1]
reps = []
duracao = []
timestamps = []
tempo = 0
for i in range(n):
	entrada = list(map(int, input().split()))
	reps.append(entrada[0])
	duracao.append(entrada[1])
	tempo += reps[i] * duracao[i]
	timestamps.append(tempo)
moments = list(map(int, input().split()))
i = 0
j = 0
while True:
	if moments[j] <= timestamps[i]:
		print(i + 1)
		j += 1
	else:
		i += 1
	if j >= m or i >= n:
		break


def main():
	primeira_linha = input()
	primeira_linha = primeira_linha.split()
	n_musicas = int(primeira_linha[0])
	n_anotacoes = int(primeira_linha[1])
	repeticao_musica = []
	tempo_musica = []
	for i in range(n_musicas):
		entrada = input()
		entrada = entrada.split()
		repeticao_musica.append(int(entrada[0]))
		tempo_musica.append(int(entrada[1]))
	entrada = input()
	entrada = entrada.split()
	anotacoes = list(map(lambda x: int(x), entrada))
	j = 0
	tempo = 0
	lista_tempo = [0]
	for i in range(n_musicas):
		tempo += repeticao_musica[i] * tempo_musica[i]
		lista_tempo.append(tempo)
	i = 1
	while i <= n_musicas:
		if anotacoes[j] <= lista_tempo[i] and anotacoes[j] >= lista_tempo[i - 1]:
			print(i)
			j += 1
		else:
			i += 1
		if j == n_anotacoes:
			break
main()


(n, m) = (int(x) for x in input().split(' '))
music = []
for _ in range(n):
	(x, y) = (int(x) for x in input().split(' '))
	music.append(x * y)
moments = [int(x) for x in input().split(' ')]
dormpointer = 0
roompointer = 0
totalsum = 0
for l in moments:
	while l - totalsum > music[dormpointer]:
		totalsum += music[dormpointer]
		dormpointer += 1
	print(dormpointer + 1)


def search(arr, x, n):
	(low, high) = (0, n - 1)
	if x <= arr[low]:
		return 1
	while low < high:
		mid = (low + high) // 2
		if x == arr[mid]:
			return mid + 1
		elif abs(low - high) == 1:
			return high + 1
		elif x > arr[mid]:
			low = mid
		elif x < arr[mid]:
			high = mid
(n, m) = list(map(int, input().split()))
temp = []
for i in range(n):
	(a, b) = list(map(int, input().split()))
	if i == 0:
		temp.append(a * b)
	else:
		temp.append(temp[-1] + a * b)
query = list(map(int, input().split()))
cnt = 0
for i in query:
	find = i
	while temp[cnt] < find:
		cnt += 1
	print(cnt + 1)


from sys import stdin, stdout

def c_r(arr, target):
	(l, r) = (-1, len(arr))
	while l + 1 < r:
		m = (l + r) // 2
		if arr[m] >= target:
			r = m
		else:
			l = m
	return r

def main():
	(n, m) = map(int, stdin.readline().strip().split())
	p_s = []
	for i in range(n):
		(c, t) = map(int, stdin.readline().strip().split())
		if p_s:
			p_s.append(p_s[-1] + c * t)
		else:
			p_s.append(c * t)
	Q = list(map(int, stdin.readline().strip().split()))
	outputs = []
	for i in Q:
		outputs.append(c_r(p_s, i) + 1)
	for output in outputs:
		print(output)
main()


(n, m) = map(int, input().split())
song_end = [None] * n
for i in range(n):
	(c, t) = map(int, input().split())
	song_end[i] = (song_end[i - 1] if i > 0 else 0) + c * t
moments = list(map(int, input().split()))
curr_song = 0
res = []
for mom in moments:
	while mom > song_end[curr_song]:
		curr_song += 1
	res.append(str(curr_song + 1))
print('\n'.join(res))


from sys import stdin, stdout
(n, m) = map(int, stdin.readline().split())
ts = []
ts.append(0)
for i in range(n):
	(j, k) = map(int, stdin.readline().split())
	ts.append(ts[i] + j * k)
i = 0
j = 1
V = list(map(int, stdin.readline().split()))
for v in V:
	if ts[i] <= v <= ts[j]:
		print(i + 1)
	elif ts[j] < v:
		while ts[j] < v:
			i += 1
			j += 1
		print(i + 1)


from sys import stdin, stdout
import bisect as bs
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	(n, q) = lst()
	a = [0]
	for i in range(n):
		(t, d) = lst()
		a += [a[-1] + t * d]
	for v in lst():
		print(bs.bisect_left(a, v))


(n, m) = map(int, input().split())
arr = [0]
(k, l) = (0, 0)
for i in range(n):
	(c, t) = map(int, input().split())
	arr.append(arr[i] + c * t)
ara = list(map(int, input().split()))
for j in range(m):
	while ara[j] > arr[l]:
		l += 1
	print(l)


import bisect
(n, m) = map(int, input().split())
T = [0] * n
for i in range(n):
	(t, c) = map(int, input().split())
	T[i] = t * c
m = list(map(int, input().split()))
for i in range(1, n):
	T[i] += T[i - 1]
for i in range(len(m)):
	i = bisect.bisect_left(T, m[i], 0, n)
	print(i + 1)


def main():
	music_times = []
	(n, m) = map(int, input().split())
	for i in range(n):
		(c, t) = map(int, input().split())
		if i == 0:
			music_times.append(c * t)
		else:
			music_times.append(c * t + music_times[i - 1])
	fav_moments = [int(i) for i in input().split(' ')]
	(i, j) = (0, 0)
	while j < m and i < n:
		if fav_moments[j] <= music_times[i]:
			j += 1
			print(i + 1)
		else:
			i += 1
main()


(n, m) = map(int, input().split())
s = []
for i in range(n):
	(a, b) = map(int, input().split())
	s.append(a * b)
q = list(map(int, input().split()))
a = 0
b = 0
su = s[0]
while b < m:
	if q[b] > su:
		a += 1
		su += s[a]
	else:
		print(a + 1)
		b += 1


from bisect import bisect_right, bisect_left
(n, q) = map(int, input().split())
a = []
s = 0
for i in range(n):
	(x, y) = map(int, input().split())
	s += x * y
	a.append(s)
x = [int(n) for n in input().split()]
for i in x:
	print(bisect_left(a, i) + 1)


from bisect import bisect_left as pos
(n, m) = map(int, input().split())
track = [0]
for i in range(1, n + 1):
	(c, t) = map(int, input().split())
	track.append(c * t + track[i - 1])
moment = map(int, input().split())
[print(pos(track, i)) for i in moment]


(n, _) = input().split()
n = int(n)
songs = []
for i in range(n):
	(c, t) = input().split()
	songs.append((int(c), int(t)))
moments = list(map(lambda x: int(x), input().split()))
i = 1
now = songs[i - 1][0] * songs[i - 1][1]
for m in moments:
	while now < m:
		i += 1
		now += songs[i - 1][0] * songs[i - 1][1]
	print(i)


(n, m) = map(int, input().split())
l = []
x = 0
for i in range(n):
	(c, t) = map(int, input().split())
	x += c * t
	l.append(x)
l1 = list(map(int, input().split()))
ans = []
for i in range(m):
	beg = 0
	end = n - 1
	while beg <= end:
		mid = (end + beg) // 2
		j = mid - 1
		if l1[i] <= l[mid]:
			if mid == 0:
				ans.append(mid + 1)
				break
			elif l1[i] > l[mid - 1]:
				ans.append(mid + 1)
				break
			else:
				end = mid - 1
		else:
			beg = mid + 1
for i in range(m):
	print(ans[i])


s = input()
(n, m) = list(map(int, s.split(' ')))
l = [0]
for i in range(n):
	s = input()
	(t1, t2) = list(map(int, s.split(' ')))
	l.append(l[-1] + t1 * t2)
xs = list(map(int, input().split(' ')))
j = 0
i = 0
while i < m:
	if xs[i] <= l[j]:
		print(j)
		i += 1
	else:
		j += 1


(n, m) = list(map(int, input().split()))
(c, t) = ([], [])
for _ in range(n):
	(nc, nt) = list(map(int, input().split()))
	c.append(nc)
	t.append(nt)
ms = list(map(int, input().split()))
cur_x = 0
cur_y = 0
cur_st = 0
ans = []
for i in range(len(ms)):
	while cur_st < ms[i] and cur_x < len(c):
		cur_x += 1
		cur_st += c[cur_x - 1] * t[cur_x - 1]
	ans.append(cur_x)
print('\n'.join(map(str, ans)))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, m) = kk()
ls = [0] * n
for i in range(n):
	(a, b) = kk()
	ls[i] = a * b
i = ct = 0
ar = []
for t in kk():
	while t > ct:
		ct += ls[i]
		i += 1
	ar.append(i)
print('\n'.join(map(str, ar)))


(n, m) = [int(p) for p in input().split()]
sm = []
for i in range(n):
	(c, t) = [int(p) for p in input().split()]
	if not sm:
		sm.append(c * t)
	else:
		sm.append(sm[-1] + c * t)
time = [int(p) for p in input().split()]
i = 0
j = 0
while j < len(time):
	if sm[i] >= time[j]:
		print(i + 1)
		j += 1
	else:
		i += 1


(n, m) = map(int, input().split())
p = []
q = []
for _ in range(n):
	(c, t) = map(int, input().split())
	p.append(c * t)
v = list(map(int, input().split()))
for i in range(1, n):
	p[i] = p[i] + p[i - 1]
j = 0
for i in v:
	l = j
	h = n - 1
	while l <= h:
		mid = (l + h) // 2
		if mid == 0 and i <= p[mid]:
			j = mid
			print(mid + 1)
			break
		if i > p[mid - 1] and i <= p[mid]:
			j = mid
			print(mid + 1)
			break
		elif i > p[mid]:
			l = mid + 1
		else:
			h = mid - 1


(n, m) = list(map(int, input().split()))
inps = []
for i in range(n):
	(c, t) = list(map(int, input().split()))
	inps.append(c * t)
p = i = 0
for v in list(map(int, input().split())):
	while p < v:
		p += inps[i]
		i += 1
	print(i)


R = lambda : map(int, input().split())
(n, m) = R()
A = []
while n > 0:
	n -= 1
	(c, t) = R()
	A.append(c * t)
i = p = 0
for v in R():
	while p < v:
		p += A[i]
		i += 1
	print(i)


(n, m) = map(int, input().split())
time = 0
ans = 1
l = []
for i in range(n):
	l.append([int(j) for j in input().split()])
check = list(map(int, input().split()))
j = 0
i = 0
while i < m:
	if check[i] - time <= l[j][0] * l[j][1]:
		print(j + 1)
		i += 1
	else:
		time += l[j][0] * l[j][1]
		j += 1


tableautaille = input().split(' ')
n = int(tableautaille[0])
m = int(tableautaille[1])
tabfinal = []
for i in range(n):
	tab = input().split(' ')
	c = int(tab[0])
	t = int(tab[1])
	tabfinal += [c * t]
tableau = input().split(' ')
res = 0
indice = 0
for i in range(m):
	search = int(tableau[i])
	while search > res + tabfinal[indice]:
		res += tabfinal[indice]
		indice += 1
	print(indice + 1)


from bisect import bisect_left as pos
(n, m) = map(int, input().split())
line = [0]
for i in range(1, n + 1):
	(c, t) = map(int, input().split())
	line.append(c * t + line[i - 1])
mom = list(map(int, input().split()))
print('\n'.join([str(pos(line, i)) for i in mom]))


(n, m) = map(int, input().split())
s = [0]
k = 0
l = 0
for i in range(n):
	(c, t) = map(int, input().split())
	s.append(s[i] + c * t)
ara = [int(x) for x in input().split()]
for j in range(m):
	while ara[j] > s[l]:
		l += 1
	print(l)


(n, m) = map(int, input().split())
song_change = [0]
for i in range(n):
	prod = 1
	for x in map(int, input().split()):
		prod *= x
	song_change.append(song_change[-1] + prod)
querry = list(map(int, input().split()))
for i in range(m):
	l = 1
	r = n
	ans = -1
	while l <= r:
		mid = l + (r - l) // 2
		if song_change[mid] < querry[i]:
			ans = mid
			l = mid + 1
		else:
			r = mid - 1
	if ans == -1:
		print(1)
	else:
		print(ans + 1)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase
from fractions import *

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, m) = value()
time = [0]
for i in range(n):
	(c, t) = value()
	time.append(c * t + time[-1])
a = array()
for i in a:
	ind = bisect_left(time, i)
	print(ind)


from bisect import insort, bisect_left
nm = input().split()
n = int(nm[0])
m = int(nm[1])
r = 0
l = []
li = []
for i in range(n):
	ct = input().split()
	c = int(ct[0])
	t = int(ct[1])
	l.append(r + c * t)
	r = r + c * t
li = list(map(int, input().split()))
for i in range(len(li)):
	k = bisect_left(l, li[i])
	print(k + 1)


import bisect
(n, m) = map(int, input().split())
totalTimes = []
for _ in range(n):
	(c, t) = map(int, input().split())
	totalTimes.append(c * t)
moments = list(map(int, input().split()))
sum_total = [0]
for i in range(n):
	sum_total.append(sum_total[-1] + totalTimes[i])
for j in range(m):
	song = bisect.bisect_left(sum_total, moments[j])
	print(song)


(n, m) = map(int, input().split())
a = {}
l = 0
o = []
for i in range(n):
	(pro, profi) = map(int, input().split())
	a[l + 1] = i + 1
	o.append(l + 1)
	l = pro * profi + l
ewgeniq = list(map(int, input().split()))
l = 0
for i in range(m):
	while l < len(o) and ewgeniq[i] >= o[l]:
		l += 1
	print(a[o[l - 1]])


import bisect
(n, m) = map(int, input().split())
s = [0]
for _ in range(n):
	(c1, c2) = map(int, input().split())
	s.append(s[-1] + c1 * c2)
p = list(map(int, input().split()))
for i in p:
	print(bisect.bisect_left(s, i))


from sys import stdin

def get_closest_binary(num, l):
	if num > l[-1]:
		return len(l)
	elif num < l[0]:
		return 0
	else:
		m = 0
		ma = len(l) - 1
		while ma - m > 1:
			if num > l[m + (ma - m) // 2]:
				m += (ma - m) // 2
			else:
				ma -= (ma - m) // 2 + 1
		if num > l[ma]:
			return ma
		else:
			return m
(n, m) = map(int, stdin.readline().rstrip().split(' '))
s = [0] * (n + 1)
for i in range(n):
	(x, y) = map(int, stdin.readline().rstrip().split(' '))
	s[i + 1] = s[i] + x * y
l = list(map(int, stdin.readline().rstrip().split(' ')))
for i in l:
	print(get_closest_binary(i, s) + 1)


(n, m) = input().split(' ')
(n, m) = (int(n), int(m))
x = [[int(i) for i in input().split(' ')] for j in range(n)]
y = [int(i) for i in input().split(' ')]
y.sort()
t = 0
index = 0
r = []
for i in range(len(x)):
	t += x[i][0] * x[i][1]
	while index < len(y) and t >= y[index]:
		r.append(i + 1)
		index += 1
	if index >= len(y):
		break
print('\n'.join([str(i) for i in r]))


import bisect as bs
(n, m) = map(int, input().split())
a = []
z = 0
for _ in range(n):
	(c, k) = map(int, input().split())
	z += c * k
	a.append(z)
b = list(map(int, input().split()))
for _ in range(m):
	print(bs.bisect_left(a, b[_]) + 1)


mod = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
from bisect import *
(n, m) = f()
l = [0]
for _ in range(n):
	(c, t) = f()
	l.append(l[-1] + c * t)
for i in il():
	x = bisect_right(l, i)
	print(x - 1 if l[x - 1] == i else x)


def get_sum(sub_list):
	t = 0
	for (v, i) in sub_list:
		t += v
	return t

def get_time(sub_list, time):
	t = 0
	for (v, i) in sub_list:
		t += v
		if t >= time:
			return i
	return -1

def main():
	inlist = input().split(' ')
	(n, m) = (int(inlist[0]), int(inlist[1]))
	expanded_playlist = [[]]
	seconds_per_section = 8000
	head = 0
	for i in range(0, n):
		inlist = input().split(' ')
		(ci, ti) = (int(inlist[0]), int(inlist[1]))
		total_time = ti * ci
		while total_time >= seconds_per_section - get_sum(expanded_playlist[head]):
			inc_amount = seconds_per_section - get_sum(expanded_playlist[head])
			expanded_playlist[head] += [(inc_amount, i + 1)]
			total_time -= inc_amount
			head += 1
			expanded_playlist += [[]]
		expanded_playlist[head] += [(total_time, i + 1)]
	for vi in input().split(' '):
		vi = int(vi)
		section = vi // seconds_per_section
		internal_time = vi % seconds_per_section
		print('{}'.format(get_time(expanded_playlist[section], internal_time)))
main()


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a / gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def Bs(a, x):
	i = 0
	j = 0
	left = 1
	right = k
	flag = False
	while left < right:
		mi = (left + right) // 2
		if a[mi] <= x:
			left = mi + 1
			i += 1
		else:
			right = mi
			j += 1
	if left > 0 and a[left - 1] == x:
		return (i - 1, j)
	else:
		return (-1, -1)

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = lint()
	return n

def bstemp(n, k):
	l = 1
	r = n + 1
	while l < r:
		mid = (l + r) // 2
		if mid * (mid + 1) * 5 // 2 + k <= 4 * 60:
			l = mid + 1
		else:
			r = mid
	return l

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	if n > 2:
		l.append(n)
	return l
(n, m) = lint()
s = []
r = 0
for _ in range(n):
	(c, t) = lint()
	r += c * t
	s.append(r)
num = lint()
(l, r) = (0, n - 1)
for i in num:
	(l, r) = (0, n - 1)
	while l < r:
		mid = l + (r - l) // 2
		if s[mid] >= i:
			r = mid
		else:
			l = mid + 1
	print(r + 1)


r = input().split(' ')
n = int(r[0])
m = int(r[1])
s = []
for i in range(0, n):
	r = input().split(' ')
	s.append(int(r[0]) * int(r[1]))
	if i > 0:
		s[i] += s[i - 1]
r = input().split(' ')
ct = 0
for i in range(0, m):
	v = int(r[i])
	while s[ct] < v:
		ct += 1
	print(ct + 1)


from sys import stdin
import math

def binSearch(arr, low, high, x):
	if low == high:
		return low
	mid = (low + high) // 2
	if arr[mid] == x:
		return mid
	if arr[mid] < x:
		return binSearch(arr, mid + 1, high, x)
	else:
		return binSearch(arr, low, mid, x)
(n, m) = list(map(int, stdin.readline().rstrip().split(' ')))
prefixArr = [0]
for _ in range(n):
	(ci, ti) = list(map(int, stdin.readline().rstrip().split(' ')))
	prefixArr.append(prefixArr[-1] + ci * ti)
arr = list(map(int, stdin.readline().rstrip().split(' ')))
for ele in arr:
	print(binSearch(prefixArr, 0, len(prefixArr) - 1, ele))


def f():
	(n, m) = map(int, input().split())
	d = [0] * (n + 1)
	for i in range(1, n + 1):
		(a, b) = map(int, input().split())
		d[i] = d[i - 1] + a * b
	t = list(map(int, input().split()))
	j = 0
	for i in range(1, n + 1):
		while t[j] <= d[i]:
			t[j] = i
			j += 1
			if j == m:
				print('\n'.join((str(k) for k in t)))
				return
f()


(n, m) = [int(i) for i in input().split()]
c = []
t = []
for i in range(n):
	song = input().split()
	c.append(int(song[0]))
	t.append(int(song[1]))
req = [int(i) for i in input().split()]
req_index = total_length = 0
for i in range(len(c)):
	total_length += c[i] * t[i]
	while req_index < len(req):
		if req[req_index] <= total_length:
			print(i + 1)
			req_index += 1
		else:
			break
	if req_index == len(req):
		break


(n, m) = map(int, input().split())
l = []
for _ in range(n):
	l.append(list(map(int, input().split())))
b = list(map(int, input().split()))
a = [0] * n
a[0] = l[0][0] * l[0][1]
for i in range(1, n):
	a[i] = a[i - 1] + l[i][0] * l[i][1]
a = [0] + a
index = 0
for i in range(m):
	x = b[i]
	while x > a[index]:
		index += 1
	print(index)


def main():
	from sys import stdin
	l = stdin.read().splitlines()
	(it, res, now) = (iter(enumerate(l)), [], 0)
	next(it)
	for v in map(int, l[-1].split()):
		while now < v:
			(i, s) = next(it)
			(c, t) = map(int, s.split())
			now += c * t
		res.append(i)
	print('\n'.join(map(str, res)))
main()


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))
(n, m) = mints()
a = [0]
s = 0
for i in range(n):
	(c, t) = mints()
	s += c * t
	a.append(s)
j = 0
for i in mints():
	while not (i - 1 >= a[j] and i - 1 < a[j + 1]):
		j += 1
	print(j + 1)


import bisect
I = lambda : map(int, input().rstrip().split())
(n, m) = I()
dp = [0]
for _ in range(n):
	(c, t) = I()
	dp.append(dp[-1] + c * t)
v = list(I())
for x in v:
	print(bisect.bisect_left(dp, x))


(n, m) = map(int, input().split())
A = []
for i in range(n):
	(c, t) = map(int, input().split())
	A.append(c * t)
i = p = 0
for v in [int(x) for x in input().split()]:
	while p < v:
		(p, i) = (p + A[i], i + 1)
	print(i)


string = input().split()
numList = list(map(int, string))
n = numList[0]
m = numList[1]
count = 0
moments = []
last = 0
for i in range(n):
	music = list(map(int, input().split()))
	moments.append(count + music[0] * music[1])
	count = count + music[0] * music[1]
times = list(map(int, input().split()))
for i in range(m):
	for j in range(last, n):
		if times[i] <= moments[j]:
			print(j + 1)
			last = j
			break


(n, m) = list(map(int, input().split()))
songs = []
for i in range(n):
	(c, t) = list(map(int, input().split()))
	songs.append(c * t)
bb = list(map(int, input().split()))
song = 1
prev = 0
for m in bb:
	while songs[song - 1] + prev < m:
		prev += songs[song - 1]
		song += 1
	print(song)


def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def MAP2():
	return map(float, input().split())

def LIST():
	return list(map(int, input().split()))

def STRING():
	return input()
import string
import sys
from heapq import heappop, heappush
from bisect import *
from collections import deque, Counter, defaultdict
from math import *
from itertools import permutations, accumulate
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
(n, m) = MAP()
last = -1
y = []
for i in range(n):
	(c, t) = MAP()
	x = c * t
	if last == -1:
		last = x
		y.append(x)
	else:
		y.append(x + last)
		last = last + x
q = LIST()
h = len(y)
ans = []
for i in range(m):
	z = q[i]
	(l, r) = (0, h - 1)
	while l <= r:
		mid = l + (r - l) // 2
		if y[mid] >= z:
			r = mid - 1
		else:
			l = mid + 1
	ans.append(l + 1)
for i in ans:
	print(i)


def bs(l, h):
	while l < h:
		m = (l + h + 1) // 2
		if a[m] < i:
			l = m
		else:
			h = m - 1
	return l
(n, m) = map(int, input().split())
(c, t) = map(int, input().split())
l = c * t
a = [0]
for _ in range(n - 1):
	(c, t) = map(int, input().split())
	a.append(l)
	l = a[-1] + c * t
b = map(int, input().split())
for i in b:
	print(bs(0, n - 1) + 1)


import bisect
from itertools import accumulate
(n, m) = map(int, input().split())
ans = []
for i in range(n):
	(c, t) = map(int, input().split())
	ans.append(c * t)
p = []
p = list(accumulate(ans))
m = list(map(int, input().split()))
for i in range(0, len(m)):
	print(bisect.bisect_left(p, m[i]) + 1)


import bisect

def precalc():
	pref[0] = songs[0]
	for i in range(1, n):
		pref[i] = pref[i - 1] + songs[i]
(n, m) = map(int, input().split())
pref = [0] * n
songs = []
for i in range(n):
	(c, t) = map(int, input().split())
	songs.append(c * t)
time = [int(i) for i in input().split()]
precalc()
for i in range(m):
	print(bisect.bisect_left(pref, time[i]) + 1)


import sys

def dist(x1, y1, x2, y2):
	return abs(x2 - x1) + abs(y2 - y1)
(n, m) = [int(x) for x in sys.stdin.readline().strip().split(' ')]
songs = []
for i in range(n):
	cur = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	songs.append(cur)
queries = [int(x) for x in sys.stdin.readline().strip().split(' ')]
start_time = 0
intervals = []
cur_time = start_time
for i in range(0, len(songs)):
	song = songs[i]
	times = song[0]
	dur = song[1]
	new_time = cur_time + times * dur
	intervals.append(new_time)
	cur_time = new_time
queries = sorted(queries)
idx = 0
for q in queries:
	while q > intervals[idx]:
		idx += 1
	print(idx + 1)


import operator as op
import itertools as it
import bisect as bs
(n, m) = map(int, input().split())
a = list(it.accumulate([op.mul(*map(int, input().split())) for _ in range(n)]))
ans = []
for t in map(int, input().split()):
	ans.append(str(bs.bisect_left(a, t) + 1))
print('\n'.join(ans))


song = list()
(n, m) = map(int, input().split())
song.append(0)
for i in range(n):
	(note, times) = map(int, input().split())
	total_time = song[i] + note * times
	song.append(total_time)
eugeny_moments = list(map(int, input().split()))
counter = 0
for i in range(m):
	while True:
		check = eugeny_moments[i] - song[counter]
		if check > 0:
			counter += 1
		else:
			break
	print(counter)


I = [int(i) for i in input().split()]
(n, m, pl, s) = (I[0], I[1], [], 0)
for i in range(n):
	I = [int(i) for i in input().split()]
	s += I[0] * I[1]
	pl.append(s)
M = [int(i) for i in input().split()]
index = 0
for i in M:
	for j in range(index, n):
		if i <= pl[j]:
			print(j + 1)
			index = j
			break


(n, m) = map(int, input().split())
track = []
for i in range(n):
	(c, t) = map(int, input().split())
	track.append(c * t)
moment = [int(i) for i in input().split()]
(i, j) = (0, 0)
s = 0
ans = []
while i < n and j < m:
	if moment[j] <= s + track[i]:
		ans.append(i + 1)
		j += 1
	else:
		s += track[i]
		i += 1
print(*ans, sep='\n')


(n, m) = map(int, input().split())
S = 0
A = [0]
for i in range(n):
	(c, t) = map(int, input().split())
	S += c * t
	A.append(S)

def search_index(x, A):
	l = -1
	r = len(A)
	while r - l > 1:
		m = int((l + r) / 2)
		if A[m] < x:
			l = m
		else:
			r = m
	if r == len(A):
		return False
	return r
B = list(map(int, input().split()))
C = []
for i in range(len(B)):
	C.append(search_index(B[i], A))
for i in range(len(C)):
	print(C[i])


def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def MAP2():
	return map(float, input().split())

def LIST():
	return list(map(int, input().split()))

def STRING():
	return input()
import string
import sys
from heapq import heappop, heappush
from bisect import *
from collections import deque, Counter, defaultdict
from math import *
from itertools import permutations, accumulate
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
(n, m) = MAP()
a = []
last = 0
for i in range(n):
	(x, y) = MAP()
	z = x * y
	a.append(last + z)
	last += z
arr = LIST()
ans = []
for i in range(m):
	k = arr[i]
	ans.append(bisect_left(a, k) + 1)
for i in ans:
	print(i)


(n, m) = map(int, input().split())
(d, t) = ([0] * (n + 1), [0] * m)
for i in range(1, n + 1):
	(a, b) = map(int, input().split())
	d[i] = d[i - 1] + a * b
i = 1
for (j, v) in enumerate(map(int, input().split())):
	while v > d[i]:
		i += 1
	t[j] = i
print('\n'.join((str(i) for i in t)))


def main(n, m, c, t, moments):
	s = 0
	answer = []
	last = 0
	for i in range(n):
		s += c[i] * t[i]
		while last < m:
			item = moments[last]
			if item <= s:
				answer.append(i + 1)
			else:
				break
			last += 1
		if last >= m:
			break
	s = ''
	for a in answer:
		s += str(a) + '\n'
	return s[:-1]

def init():
	(n, m) = list(map(int, input().split()))
	c = []
	t = []
	for i in range(n):
		(q, w) = list(map(int, input().split()))
		c.append(q)
		t.append(w)
	moments = list(map(int, input().split()))
	print(main(n, m, c, t, moments))
init()


nm = str(input())
nms = nm.split(' ')
n = int(nms[0])
m = int(nms[1])
ar = [0] * n
for i in range(n):
	ct = str(input())
	cts = ct.split(' ')
	ar[i] = ar[i - 1] + int(cts[0]) * int(cts[1])
v = str(input())
vs = v.split(' ')
curr = 0
for i in range(m):
	p = int(vs[i])
	for j in range(curr, n):
		if p <= ar[j]:
			print(j + 1)
			curr = j
			break


def busca(lista, ind, valor, soma):
	verdade = True
	while verdade:
		if soma >= valor:
			return [ind, soma]
		soma += lista[ind]
		ind += 1

def main():
	(n, m) = [int(i) for i in input().split(' ')]
	out = []
	for i in range(n):
		(c, t) = [int(i) for i in input().split(' ')]
		out.append(c * t)
	soma = 0
	ind = 0
	for i in input().split(' '):
		(ind, soma) = busca(out, ind, int(i), soma)
		print(abs(ind))
main()


(n, m) = input().split(' ')
n = int(n)
m = int(m)
musicas = []
i = 0
while i < n:
	(ci, ti) = input().split(' ')
	musicas.append((int(ci), int(ti)))
	i += 1
tempos = input().split(' ')
tempo_atual = musicas[0][0] * musicas[0][1]
musica_atual = 0
i = 0
while i < m:
	tempo = int(tempos[i])
	if int(tempo) <= tempo_atual:
		print(musica_atual + 1)
	else:
		musica_atual += 1
		tempo_atual += musicas[musica_atual][0] * musicas[musica_atual][1]
		i -= 1
	i += 1


(n, m) = [int(i) for i in input().split()]
c = []
t = []
for i in range(n):
	(ci, ti) = [int(i) for i in input().split()]
	c.append(ci)
	t.append(ti)
v = [int(i) for i in input().split()]
times = [c[0] * t[0]]
for i in range(1, n):
	song_duration = c[i] * t[i]
	times.append(times[-1] + song_duration)
moment = 0
song = 0
while moment < m:
	if v[moment] <= times[song]:
		print(song + 1)
		moment += 1
	else:
		song += 1


(n, m) = map(int, input().split())
x = [0] * (n + 1)
for i in range(n):
	(c, t) = map(int, input().split())
	x[i] = (x[i - 1] if i else 0) + c * t
v = list(map(int, input().split()))
c = 0
for k in v:
	while k > x[c]:
		c += 1
	print(str(c + 1))


(n, m) = map(int, input().split())
lis = [0]
for i in range(1, n + 1):
	(l, r) = map(int, input().split())
	lis.append(l * r + lis[i - 1])
v = [int(x) for x in input().split()]
s = 1
for elem in v:
	while lis[s] < elem:
		s += 1
	print(s)


song = [0]
(n, m) = input().split()
(n, m) = (int(n), int(m))
for i in range(1, n + 1):
	(x, y) = input().split()
	(x, y) = (int(x), int(y))
	song.append(song[i - 1] + x * y)
count = 0
x = list(map(int, input().split()))
for i in range(m):
	while x[i] > song[count]:
		count = count + 1
	count = count - 1
	print(count + 1)


def bs(x):
	l = 0
	r = n
	while l + 1 < r:
		m = (l + r) // 2
		if x <= p[m]:
			r = m
		else:
			l = m
	if x <= p[l]:
		return l
	return r
(n, k) = map(int, input().split())
a = []
for i in range(n):
	(c, t) = map(int, input().split())
	a.append(c * t)
p = [a[0]]
for i in range(1, n):
	p.append(p[i - 1] + a[i])
for i in map(int, input().split()):
	print(bs(i) + 1)


import io
import math
(nancy, mike) = list(map(int, input().split()))
array = []
for i in range(nancy):
	(red, blue) = list(map(int, input().split()))
	array.append(red * blue)
counter = i = 0
for j in list(map(int, input().split())):
	while counter < j:
		counter += array[i]
		i += 1
	print(i)


(n, m) = map(int, input().split())
d = []
pre = 0
for i in range(n):
	(x, y) = map(int, input().split())
	u = pre + 1
	v = x * y + u - 1
	d.append((u, v, i + 1))
	pre = v
v = list(map(int, input().split()))
j = 0
for i in range(m):
	while d[j][1] < v[i]:
		j += 1
	print(d[j][2])


[n, m] = [int(i) for i in input().split()]
time_listening = []
for i in range(n):
	[c, t] = [int(i) for i in input().split()]
	time_listening.append(c * t)
moments = [int(i) for i in input().split()]
soma = time_listening[0]
atual = 1
for time in moments:
	while time > soma:
		soma += time_listening[atual]
		atual += 1
	print(atual)


import bisect
(n, m) = map(int, input().split())
ls = [0] * (n + 1)
for i in range(1, n + 1):
	(c, t) = map(int, input().split())
	ls[i] = ls[i - 1] + c * t
arr = list(map(int, input().split()))
for i in range(m):
	var = bisect.bisect_left(ls, arr[i])
	print(var)


from sys import stdin as sin

def aint():
	return int(input())

def amap():
	return map(int, sin.readline().split())

def alist():
	return list(map(int, sin.readline().split()))

def astr():
	return input()

def bins(l, low, high, k):
	while low <= high:
		mid = low + (high - low) // 2
		if l[mid] == k:
			return mid
		elif l[mid] < k:
			low = mid + 1
		else:
			high = mid - 1
	return high + 1
(n, m) = amap()
a = 0
l = []
for i in range(n):
	(c, t) = amap()
	a += c * t
	l.append(a)
v = alist()
for i in v:
	print(bins(l, 0, n - 1, i) + 1)


from bisect import bisect_left
I = lambda : map(int, input().split())
(n, _) = I()
T = [0]
for _ in range(n):
	(c, t) = I()
	T.append(T[-1] + c * t)
for t in I():
	print(bisect_left(T, t))