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: interview

Starter code:

Solutions:
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

#CF302B
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 )


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


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()

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 = 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))

# -*- coding: utf-8 -*-
"""
Created on Tue Nov  3 20:30:05 2015

@author: kevin
"""

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)


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 = list(map(int, s.split()))
            now += c * t
        res.append(i)
    print('\n'.join(map(str, res)))


def __starting_point():
    main()

__starting_point()

n, m = list(map(int, input().split()))
song_end = [None] * n
for i in range(n):
    c, t = list(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))


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

for j in range(m):
    while ara[j]>s[l]:
        l+=1
    print(l)



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

for j in range(m):
    while ara[j]>s[l]:
        l+=1
    print(l)


n,m=list(map(int,input().split()))
A=[]
for i in range(n):
	c,t=list(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)


R=lambda:list(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())
s=[0]
k=0
l=0
for i in range(n):
    c,t=map(int,input().split())
    s.append(s[i]+c*t)
   # print(s[i])
ara= [int(x) for x in input().split()]

for j in range(m):
    while ara[j]>s[l]:
        l+=1
    print(l)

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  # could be 1 kek

intervals = []
cur_time = start_time
for i in range(0, len(songs)):
  song = songs[i] # times, duration
  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 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  # could be 1 kek

intervals = []
cur_time = start_time
for i in range(0, len(songs)):
  song = songs[i] # times, duration
  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 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  # could be 1 kek

intervals = []
cur_time = start_time
for i in range(0, len(songs)):
  song = songs[i] # times, duration
  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 sys
# sys.stdin=open('F:\\C\\Script\\input.txt','r')
# sys.stdout=open('F:\\C\\Script\\output.txt','w')
# sys.stdout.flush()

# MOD = 1000000007
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])
# print (l)
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=list(map(int,input().split()))

A=[]

for i in range(n):

	c,t=list(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)





# Made By Mostafa_Khaled


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)


n, m = list(map(int, input().split()))
arr = []
for i in range(n):
    c, t = list(map(int, input().split()))
    arr += [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
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)


# from dust i have come, dust i will be

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)

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