题目描述

题目译自 Open Olympiad in Informatics 2017 Day1 T4 「Ваня и куртки / Vanya and Jackets」。

瓦尼亚又一次决定改变生活中的某些东西，这次他决定从提前规划未来 $n$ 天穿夹克的日程开始。

他阅读了多本关于夹克使用的教程，因此他知道不同的夹克适用于不同的温度范围。对于他的 $m$ 件夹克中的每一件，他确定了 $l_i$ 和 $r_i$，即第 $i$ 件夹克允许使用的最低和最高温度。

瓦尼亚知道未来 $n$ 天的天气预报——第 $j$ 天的温度为 $a_j$。由于瓦尼亚认为自己是个理性的人，他会根据天气穿衣，也就是说，在第 $j$ 天，他可以穿任何满足 $l_i \leq a_j \leq r_i$ 的夹克 $i$。此外，瓦尼亚认为自己时尚且有品位，因此无论如何都不会连续两天穿同一件夹克。

考虑到瓦尼亚的妈妈不允许他不穿夹克出门或同时穿多件夹克，请为未来 $n$ 天制定一个穿夹克的日程，满足瓦尼亚的所有要求。

输入格式

输入数据的第一行包含两个数字 $n$ 和 $m$ $(1 \leq n, m \leq 100000)$，分别表示天数和瓦尼亚衣柜中夹克的数量。

第二行包含 $n$ 个数字 $a_i$ $(0 \leq a_i \leq 10^{9})$，表示第 $i$ 天的温度。

接下来有 $m$ 行，第 $i$ 行包含两个数字 $l_i$ 和 $r_i$ $(0 \leq l_i \leq r_i \leq 10^{9})$，表示第 $i$ 件夹克的温度限制范围。

输出格式

如果存在一种方式为 $n$ 天中的每一天选择一件夹克，则在第一行输出 Yes，在第二行输出 $n$ 个数字 $b_i$，表示瓦尼亚在第 $i$ 天应穿的夹克编号。如果不存在这样的安排，则在唯一的一行中输出 No。夹克按照输入数据中的顺序从 $1$ 开始编号。

如果存在多个符合条件的穿夹克日程，可以输出其中任意一个。

4 4
25 25 30 50
10 40
20 30
70 100
50 50

Yes
2 1 2 4

在第一个样例中，除了答案 2 1 2 4 之外，1 2 1 4 也是正确的答案。

4 2
30 40 50 60
30 40
50 60

No

在第二个样例中，无法找到合适的安排，因为瓦尼亚不得不在第一天和第二天都穿第一件夹克。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。