Andrewid the Android is a galaxy-famous detective. He is now chasing a criminal hiding on the planet Oxa-5, the planet almost fully covered with water.

The only dry land there is an archipelago of n narrow islands located in a row. For more comfort let's represent them as non-intersecting segments on a straight line: island i has coordinates [l_{i}, r_{i}], besides, r_{i} < l_{i} + 1 for 1 ≤ i ≤ n - 1.

To reach the goal, Andrewid needs to place a bridge between each pair of adjacent islands. A bridge of length a can be placed between the i-th and the (i + 1)-th islads, if there are such coordinates of x and y, that l_{i} ≤ x ≤ r_{i}, l_{i} + 1 ≤ y ≤ r_{i} + 1 and y - x = a. 

The detective was supplied with m bridges, each bridge can be used at most once. Help him determine whether the bridges he got are enough to connect each pair of adjacent islands.


-----Input-----

The first line contains integers n (2 ≤ n ≤ 2·10^5) and m (1 ≤ m ≤ 2·10^5) — the number of islands and bridges.

Next n lines each contain two integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ 10^18) — the coordinates of the island endpoints.

The last line contains m integer numbers a_1, a_2, ..., a_{m} (1 ≤ a_{i} ≤ 10^18) — the lengths of the bridges that Andrewid got.


-----Output-----

If it is impossible to place a bridge between each pair of adjacent islands in the required manner, print on a single line "No" (without the quotes), otherwise print in the first line "Yes" (without the quotes), and in the second line print n - 1 numbers b_1, b_2, ..., b_{n} - 1, which mean that between islands i and i + 1 there must be used a bridge number b_{i}. 

If there are multiple correct answers, print any of them. Note that in this problem it is necessary to print "Yes" and "No" in correct case.


-----Examples-----
Input
4 4
1 4
7 8
9 10
12 14
4 5 3 8

Output
Yes
2 3 1 

Input
2 2
11 14
17 18
2 9

Output
No

Input
2 1
1 1
1000000000000000000 1000000000000000000
999999999999999999

Output
Yes
1 



-----Note-----

In the first sample test you can, for example, place the second bridge between points 3 and 8, place the third bridge between points 7 and 10 and place the first bridge between points 10 and 14.

In the second sample test the first bridge is too short and the second bridge is too long, so the solution doesn't exist.

Source: codeforces | Difficulty: HARD
Tags: Sorting

Data structures

Greedy algorithms


Solutions:
import unittest
import sys
import re
import heapq

class Fug:

	def __init__(self, args):
		self.list = args[0]
		self.alist = args[1]
		self.gn = len(self.list) - 1
		self.asrt = sorted(((n, i) for (i, n) in enumerate(self.alist)))
		self.gaps = []
		prevli = self.list[0]
		for i in range(self.gn):
			li = self.list[i + 1]
			min = li[0] - prevli[1]
			max = li[1] - prevli[0]
			self.gaps.append((min, max, i))
			prevli = li
		self.gsrt = sorted(self.gaps)
		self.gmin = [n[0] for n in self.gsrt]
		self.result = [None] * self.gn
		self.heap = []

	def iterate(self):
		j = 0
		for (b, i) in self.asrt:
			while j < self.gn and self.gmin[j] <= b:
				it = self.gsrt[j]
				heapq.heappush(self.heap, (it[1], it[0], it[2]))
				j += 1
			if self.heap:
				(mmax, mmin, mi) = self.heap[0]
				if mmin <= b and mmax >= b:
					self.result[mi] = i + 1
					heapq.heappop(self.heap)
			yield

	def calculate(self):
		for it in self.iterate():
			pass
		for n in self.result:
			if n is None:
				return 'No'
		answer = ' '.join([str(n) for n in self.result])
		return 'Yes\n' + answer

def get_inputs(test_inputs=None):
	it = iter(test_inputs.split('\n')) if test_inputs else None

	def uinput():
		if it:
			return next(it)
		else:
			return input()
	num = [int(s) for s in uinput().split()]
	list = [[int(s) for s in uinput().split()] for i in range(num[0])]
	alist = [int(s) for s in uinput().split()]
	inputs = [list, alist]
	return inputs

def calculate(test_inputs=None):
	return Fug(get_inputs(test_inputs)).calculate()

class unitTests(unittest.TestCase):

	def test_sample_tests(self):
		test = '4 4\n1 4\n7 8\n9 10\n12 14\n4 5 3 8'
		self.assertEqual(calculate(test), 'Yes\n2 3 1')
		self.assertEqual(get_inputs(test), [[[1, 4], [7, 8], [9, 10], [12, 14]], [4, 5, 3, 8]])
		test = '5 5\n1 1\n2 7\n8 8\n10 10\n16 16\n1 1 5 6 2'
		self.assertEqual(calculate(test), 'Yes\n1 2 5 4')
		test = '2 2\n11 14\n17 18\n2 9'
		self.assertEqual(calculate(test), 'No')
		test = '2 1\n1 1\n1000000000000000000 1000000000000000000' + '\n999999999999999999'
		self.assertEqual(calculate(test), 'Yes\n1')
		test = '5 9\n1 2\n3 3\n5 7\n11 13\n14 20\n2 3 4 10 6 2 6 9 5'
		self.assertEqual(calculate(test), 'Yes\n1 6 3 2')
		size = 20000
		test = str(size) + ' ' + str(size) + '\n'
		x = size * 1000
		for i in range(size):
			x += 2
			test += str(x) + ' ' + str(x + 1) + '\n'
		for i in range(size):
			test += str(2) + ' '
		self.assertEqual(calculate(test)[0], 'Y')

	def test_Fug_class__basic_functions(self):
		d = Fug([[[1, 5], [7, 8], [9, 10], [12, 14]], [4, 5, 3, 8]])
		self.assertEqual(d.list[0][0], 1)
		self.assertEqual(d.alist[0], 4)
		self.assertEqual(d.asrt[0], (3, 2))
		self.assertEqual(d.gaps[0], (2, 7, 0))
		self.assertEqual(d.gsrt[0], (1, 3, 1))
		iter = d.iterate()
		next(iter)
		self.assertEqual(d.gmin, [1, 2, 2])
		self.assertEqual(d.heap, [(5, 2, 2), (7, 2, 0)])

def __starting_point():
	sys.setrecursionlimit(100000)
	if sys.argv[-1] == '-ut':
		unittest.main(argv=[' '])
	print(calculate())
__starting_point()


import heapq
(n, m) = [int(x) for x in input().split()]
(l1, r1) = [int(x) for x in input().split()]
req = []
start = []
for i in range(n - 1):
	(l2, r2) = [int(x) for x in input().split()]
	req.append((l2 - r1, r2 - l1, i))
	(l1, r1) = (l2, r2)
have = [int(x) for x in input().split()]
for i in range(m):
	have[i] = (have[i], i)
have.sort()
req.sort()
now = []
i = 0
j = 0
slen = len(req)
hlen = len(have)
ans = [0] * (n - 1)
while j < hlen:
	if i < slen and req[i][0] <= have[j][0]:
		heapq.heappush(now, (req[i][1], req[i][2]))
		i += 1
	else:
		try:
			x = heapq.heappop(now)
		except IndexError:
			j += 1
			continue
		if x[0] < have[j][0]:
			break
		else:
			ans[x[1]] = have[j][1]
			j += 1
if i < slen or len(now) != 0 or j < hlen:
	print('No')
else:
	print('Yes')
	print(' '.join([str(x + 1) for x in ans]))


import unittest
import sys
import re
import bisect

class Fastlist(object):

	def __init__(self, l=[], load=5000, sorted=0):
		self._load = load
		self._sorted = sorted
		self._lists = []
		self._starts = []
		self._mins = []
		self._insert_list()
		self._irev = 0
		self.extend(l)

	def _index_location(self, index):
		if len(self._lists[0]) == 0:
			raise IndexError('List index out of range')
		if index == 0:
			return (0, 0)
		if index == -1:
			return (len(self._lists) - 1, len(self._lists[-1]) - 1)
		if self._sorted:
			raise RuntimeError('No index access to the sorted list, exc 0, -1')
		length = len(self)
		if index < 0:
			index = length + index
		if index >= length:
			raise IndexError('List index out of range')
		il = bisect.bisect_right(self._starts, index) - 1
		return (il, index - self._starts[il])

	def _insert_list(self, il=None):
		if il is None:
			il = len(self._lists)
		self._lists.insert(il, [])
		if self._sorted:
			if il == 0:
				self._mins.insert(il, None)
			else:
				self._mins.insert(il, self._lists[il - 1][-1])
		elif il == 0:
			self._starts.insert(il, 0)
		else:
			start = self._starts[il - 1] + len(self._lists[il - 1])
			self._starts.insert(il, start)

	def _del_list(self, il):
		del self._lists[il]
		if self._sorted:
			del self._mins[il]
		else:
			del self._starts[il]

	def _rebalance(self, il):
		illen = len(self._lists[il])
		if illen >= self._load * 2:
			self._insert_list(il)
			self._even_lists(il)
		if illen <= self._load * 0.2:
			if il != 0:
				self._even_lists(il - 1)
			elif len(self._lists) > 1:
				self._even_lists(il)

	def _even_lists(self, il):
		tot = len(self._lists[il]) + len(self._lists[il + 1])
		if tot < self._load * 1:
			self._lists[il] += self._lists[il + 1]
			self._del_list(il + 1)
			if self._sorted:
				self._mins[il] = self._lists[il][0]
		else:
			half = tot // 2
			ltot = self._lists[il] + self._lists[il + 1]
			self._lists[il] = ltot[:half]
			self._lists[il + 1] = ltot[half:]
			if self._sorted:
				self._mins[il] = self._lists[il][0]
				self._mins[il + 1] = self._lists[il + 1][0]
			else:
				self._starts[il + 1] = self._starts[il] + len(self._lists[il])

	def _obj_location(self, obj, l=0):
		if not self._sorted:
			raise RuntimeError('No by value access to an unserted list')
		il = 0
		if len(self._mins) > 1 and obj > self._mins[0]:
			if l:
				il = bisect.bisect_left(self._mins, obj) - 1
			else:
				il = bisect.bisect_right(self._mins, obj) - 1
		if l:
			ii = bisect.bisect_left(self._lists[il], obj)
		else:
			ii = bisect.bisect_right(self._lists[il], obj)
		if ii == len(self._lists[il]) and il != len(self._lists) - 1:
			ii = 0
			il += 1
		return (il, ii)

	def insert(self, index, obj):
		(il, ii) = self._index_location(index)
		self._lists[il].insert(ii, obj)
		for j in range(il + 1, len(self._starts)):
			self._starts[j] += 1
		self._rebalance(il)

	def append(self, obj):
		if len(self._lists[-1]) >= self._load:
			self._insert_list()
		self._lists[-1].append(obj)
		if self._sorted and self._mins[0] is None:
			self._mins[0] = self._lists[0][0]

	def extend(self, iter):
		for n in iter:
			self.append(n)

	def pop(self, index=None):
		if index is None:
			index = -1
		(il, ii) = self._index_location(index)
		item = self._lists[il].pop(ii)
		if self._sorted:
			if ii == 0 and len(self._lists[il]) > 0:
				self._mins[il] = self._lists[il][0]
		else:
			for j in range(il + 1, len(self._starts)):
				self._starts[j] -= 1
		self._rebalance(il)
		return item

	def clear(self):
		self._lists.clear()
		self._starts.clear()
		self._mins.clear()
		self._insert_list()

	def as_list(self):
		return sum(self._lists, [])

	def insort(self, obj, l=0):
		(il, ii) = self._obj_location(obj, l)
		self._lists[il].insert(ii, obj)
		if ii == 0:
			self._mins[il] = obj
		self._rebalance(il)

	def add(self, obj):
		if self._sorted:
			self.insort(obj)
		else:
			self.append(obj)

	def insort_left(self, obj):
		self.insort(obj, l=1)

	def lower_bound(self, obj):
		(self._il, self._ii) = self._obj_location(obj, l=1)
		return self

	def upper_bound(self, obj):
		(self._il, self._ii) = self._obj_location(obj)
		return self

	def __str__(self):
		return str(self.as_list())

	def __setitem__(self, index, obj):
		if isinstance(index, int):
			(il, ii) = self._index_location(index)
			self._lists[il][ii] = obj
		elif isinstance(index, slice):
			raise RuntimeError('Slice assignment is not supported')

	def __getitem__(self, index):
		if isinstance(index, int):
			(il, ii) = self._index_location(index)
			return self._lists[il][ii]
		elif isinstance(index, slice):
			rg = index.indices(len(self))
			if rg[0] == 0 and rg[1] == len(self) and (rg[2] == 1):
				return self.as_list()
			return [self.__getitem__(index) for index in range(*rg)]

	def __iadd__(self, obj):
		if self._sorted:
			[self.insort(n) for n in obj]
		else:
			[self.append(n) for n in obj]
		return self

	def __delitem__(self, index):
		if isinstance(index, int):
			self.pop(index)
		elif isinstance(index, slice):
			rg = index.indices(len(self))
			[self.__delitem__(rg[0]) for i in range(*rg)]

	def __len__(self):
		if self._sorted:
			return sum([len(l) for l in self._lists])
		return self._starts[-1] + len(self._lists[-1])

	def __contains__(self, obj):
		if self._sorted:
			it = self.lower_bound(obj)
			return not it.iter_end() and obj == it.iter_getitem()
		else:
			for n in self:
				if obj == n:
					return True
			return False

	def __bool__(self):
		return len(self._lists[0]) != 0

	def __iter__(self):
		self._il = self._ii = self._irev = 0
		return self

	def __reversed__(self):
		self._il = len(self._lists) - 1
		self._ii = len(self._lists[self._il]) - 1
		self._irev = 1
		return self

	def __next__(self):
		if self._il in (-1, len(self._lists)) or len(self._lists[0]) == 0:
			raise StopIteration('Iteration stopped')
		item = self._lists[self._il][self._ii]
		if not self._irev:
			self._ii += 1
			if self._ii == len(self._lists[self._il]):
				self._il += 1
				self._ii = 0
		else:
			self._ii -= 1
			if self._ii == 0:
				self._il -= 1
				self._ii = len(self._lists[self._il])
		return item

	def iter_getitem(self):
		return self._lists[self._il][self._ii]

	def iter_end(self):
		return self._il == len(self._lists) - 1 and self._ii == len(self._lists[self._il])

	def iter_del(self):
		self.iter_pop()

	def iter_pop(self):
		item = self._lists[self._il].pop(self._ii)
		if self._sorted:
			if self._ii == 0 and len(self._lists[self._il]) > 0:
				self._mins[self._il] = self._lists[self._il][0]
		else:
			for j in range(self._il + 1, len(self._starts)):
				self._starts[j] -= 1
		self._rebalance(self._il)
		return item

class Fug:

	def __init__(self, args):
		self.gsrt = args[0]
		self.asrt = args[1]
		self.gn = args[2]
		self.result = [0] * self.gn
		self.a = Fastlist(self.asrt, load=500, sorted=1)

	def calculate(self):
		for i in range(self.gn):
			g = self.gsrt[i]
			it = self.a.lower_bound((g[1], 0))
			if not it.iter_end():
				alb = it.iter_getitem()
				if alb[0] > g[0]:
					return 'No'
				self.result[g[2]] = alb[1] + 1
				it.iter_del()
			else:
				return 'No'
		answer = 'Yes\n' + ' '.join((str(n) for n in self.result))
		return answer

def get_inputs(test_inputs=None):
	it = iter(test_inputs.split('\n')) if test_inputs else None

	def uinput():
		if it:
			return next(it)
		else:
			return sys.stdin.readline()
	num = [int(s) for s in uinput().split()]
	gaps = []
	prevli = [int(s) for s in uinput().split()]
	for i in range(num[0] - 1):
		li = [int(s) for s in uinput().split()]
		min = li[0] - prevli[1]
		max = li[1] - prevli[0]
		gaps.append((max, min, i))
		prevli = li
	alist = [(int(s), i) for (i, s) in enumerate(uinput().split())]
	inputs = [sorted(gaps), sorted(alist), num[0] - 1]
	return inputs

def calculate(test_inputs=None):
	return Fug(get_inputs(test_inputs)).calculate()

class unitTests(unittest.TestCase):

	def test_sample_tests(self):
		test = '4 4\n1 4\n7 8\n9 10\n12 14\n4 5 3 8'
		self.assertEqual(calculate(test), 'Yes\n2 3 1')
		self.assertEqual(get_inputs(test), [[(3, 1, 1), (5, 2, 2), (7, 3, 0)], [(3, 2), (4, 0), (5, 1), (8, 3)], 3])
		test = '5 5\n1 1\n2 7\n8 8\n10 10\n16 16\n1 1 5 6 2'
		self.assertEqual(calculate(test), 'Yes\n1 2 5 4')
		test = '2 2\n11 14\n17 18\n2 9'
		self.assertEqual(calculate(test), 'No')
		test = '2 1\n1 1\n1000000000000000000 1000000000000000000' + '\n999999999999999999'
		self.assertEqual(calculate(test), 'Yes\n1')
		test = '5 9\n1 2\n3 3\n5 7\n11 13\n14 20\n2 3 4 10 6 2 6 9 5'
		self.assertEqual(calculate(test), 'Yes\n1 6 3 2')
		size = 200000
		test = str(size) + ' ' + str(size) + '\n'
		x = size * 1000
		for i in range(size):
			test += str(x) + ' ' + str(x + i + 1) + '\n'
			x += 2 * (i + 1)
		for i in reversed(range(size)):
			test += str(i) + ' '
		self.assertEqual(calculate(test)[0], 'Y')

	def test_Fug_class__basic_functions(self):
		d = Fug([[(1, 3, 1), (2, 5, 2), (3, 7, 0)], [(3, 2), (4, 0), (5, 1), (8, 3)], 3])
		self.assertEqual(d.asrt[0], (3, 2))
		self.assertEqual(d.gsrt[0], (1, 3, 1))
sys.setrecursionlimit(100000)
if sys.argv[-1] == '-ut':
	unittest.main(argv=[' '])
sys.stdout.write(calculate())