最初有一个包含 $n$ 个整数的数组 $a$，其位置编号从 $1$ 到 $n$。
对该数组执行了恰好 $q$ 次查询。在第 $i$ 次查询中，选择了一个区间 $(l_i, r_i)$（满足 $1 lt.eq l_i lt.eq r_i lt.eq n$），并将位置从 $l_i$ 到 $r_i$（含）的所有元素的值更改为 $i$。查询的顺序不可更改，且所有 $q$ 次查询均被应用。同时已知，从 $1$ 到 $n$ 的每个位置至少被一个区间覆盖。
我们本可以向你提出一个问题：检查某个给定数组（由 $n$ 个取值在 $1$ 到 $q$ 之间的整数组成）是否可以通过上述查询得到。但我们决定这对你来说太简单了。
因此，我们对此问题进行了增强：在该数组中选择了一个位置集合（可能为空），并将这些位置上的元素值设为 $0$。
你的任务是判断该数组是否可以通过上述查询得到。如果可以，请还原该数组。
如果有多个可能的数组，请输出其中任意一个。
第一行包含两个整数 $n$ 和 $q$（$1 lt.eq n, q lt.eq 2 dot.op 10^5$）——数组的元素个数和对其执行的查询次数。
第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$0 lt.eq a_i lt.eq q$）——最终的数组。如果某个位置 $j$ 的元素等于 $0$，则该位置的值可以是 $1$ 到 $q$ 之间的任意整数。
如果数组 $a$ 可以通过执行 $q$ 次查询得到，则输出 "_YES_"。每个查询选择的区间 $(l_i, r_i)$（$1 lt.eq l_i lt.eq r_i lt.eq n$）彼此独立，且从 $1$ 到 $n$ 的每个位置都必须至少被一个区间覆盖。
否则输出 "_NO_"。
如果可以得到某个数组，则在第二行输出 $n$ 个整数——第 $i$ 个数应等于结果数组中第 $i$ 个元素的值，且必须在 $1$ 到 $q$ 之间。该数组必须可通过恰好执行 $q$ 次查询得到。
如果有多个可能的数组，请输出其中任意一个。
在第一个示例中，你可以将 $0$ 替换为 $1$，但不能替换为 $3$。
在第二个示例中，在第 $10$ 次查询之前，选择什么区间并不重要，此时区间为 $(1, 3)$。
第三个示例展示了查询顺序不可更改的事实：你不能先将 $(1, 3)$ 设为 $6$，然后再将 $(2, 2)$ 设为 $5$。$5$ 的区间必须在 $6$ 的区间之前应用。
第四个示例中有许多正确的结果数组。
## Input
第一行包含两个整数 $n$ 和 $q$（$1 lt.eq n, q lt.eq 2 dot.op 10^5$）——数组的元素个数和对其执行的查询次数。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$0 lt.eq a_i lt.eq q$）——最终的数组。如果某个位置 $j$ 的元素等于 $0$，则该位置的值可以是 $1$ 到 $q$ 之间的任意整数。
## Output
如果数组 $a$ 可以通过执行 $q$ 次查询得到，则输出 "_YES_"。每个查询选择的区间 $(l_i, r_i)$（$1 lt.eq l_i lt.eq r_i lt.eq n$）彼此独立，且从 $1$ 到 $n$ 的每个位置都必须至少被一个区间覆盖。否则输出 "_NO_"。如果可以得到某个数组，则在第二行输出 $n$ 个整数——第 $i$ 个数应等于结果数组中第 $i$ 个元素的值，且必须在 $1$ 到 $q$ 之间。该数组必须可通过恰好执行 $q$ 次查询得到。如果有多个可能的数组，请输出其中任意一个。
[samples]
## Note
在第一个示例中，你可以将 $0$ 替换为 $1$，但不能替换为 $3$。在第二个示例中，在第 $10$ 次查询之前，选择什么区间并不重要，此时区间为 $(1, 3)$。第三个示例展示了查询顺序不可更改的事实：你不能先将 $(1, 3)$ 设为 $6$，然后再将 $(2, 2)$ 设为 $5$。$5$ 的区间必须在 $6$ 的区间之前应用。第四个示例中有许多正确的结果数组。
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ denote the length of the array and the number of queries.
Let $ A = (a_1, a_2, \dots, a_n) $ be the given array, where $ a_i \in \{0, 1, 2, \dots, q\} $.
Let $ S = \{ i \in \{1, \dots, n\} \mid a_i = 0 \} $ be the set of positions with unknown (zero) values.
For each query $ i \in \{1, \dots, q\} $, there exists a segment $ [l_i, r_i] \subseteq [1, n] $ such that all positions in $ [l_i, r_i] $ are assigned value $ i $ during the $ i $-th query.
Queries are applied sequentially in order $ 1 $ to $ q $, and each position $ j \in [1, n] $ must be covered by at least one segment.
**Constraints**
1. $ 1 \leq n, q \leq 2 \cdot 10^5 $
2. $ 0 \leq a_i \leq q $ for all $ i \in \{1, \dots, n\} $
3. Every position $ j \in \{1, \dots, n\} $ is covered by at least one query segment.
4. For any two queries $ i < j $, if position $ k $ is covered by both $ [l_i, r_i] $ and $ [l_j, r_j] $, then the final value at $ k $ is $ j $ (due to sequential overwrite).
**Objective**
Determine whether there exists an assignment $ b = (b_1, \dots, b_n) $ such that:
- $ b_i = a_i $ for all $ i \notin S $,
- $ b_i \in \{1, \dots, q\} $ for all $ i \in S $,
- There exist segments $ [l_1, r_1], \dots, [l_q, r_q] $ such that applying queries $ 1 $ to $ q $ in order yields $ b $.
Additionally, if such $ b $ exists, output any valid $ b $.
**Key Necessary Conditions**
Let $ f(j) $ be the final value at position $ j $ (i.e., $ b_j $).
Then:
- For each $ i \in \{1, \dots, q\} $, the set $ \{ j \mid f(j) = i \} $ must form a contiguous interval.
- If $ i < j $ and both $ f(k_1) = i $, $ f(k_2) = j $, and $ f(k_3) = i $ for some $ k_1 < k_2 < k_3 $, then the assignment is invalid (since query $ j $ would overwrite $ i $ in between, preventing $ i $ from appearing again later).
- For each $ i \in \{1, \dots, q\} $, if $ i $ appears in $ b $, then all occurrences of $ i $ must be contiguous, and no larger-indexed query value may appear *between* two occurrences of $ i $.
- The maximum value appearing in $ b $ must be $ q $, and it must appear in at least one position.
- For each $ i \in \{1, \dots, q\} $, define $ L_i = \min\{ j \mid b_j = i \} $, $ R_i = \max\{ j \mid b_j = i \} $. Then $ [L_i, R_i] \subseteq [L_{i+1}, R_{i+1}] $ is **not** required, but if $ L_j < L_i < R_j $ for some $ j > i $, then $ R_i $ must be $ \leq R_j $, and no position between $ L_i $ and $ R_i $ may have a value $ > i $ unless it is overwritten by $ j > i $.
**Reconstruction Strategy (Implicit)**
- For each $ i \in \{1, \dots, q\} $, define $ \text{first}_i = \min \{ j \mid a_j = i \} $, $ \text{last}_i = \max \{ j \mid a_j = i \} $ (if none, then $ \text{first}_i = \text{last}_i = \infty $).
- For each zero position $ j $, assign it the value of the **last** query $ i $ such that $ \text{first}_i \leq j \leq \text{last}_i $ and $ i $ is maximal among such queries. If no such $ i $ exists, assign $ q $ (if $ q $ appears somewhere) or the largest $ i $ such that $ \text{first}_i \leq j \leq \text{last}_i $, but this must be consistent with the non-overwrite constraint.
- Validate: For every $ i \in \{1, \dots, q\} $, the set $ \{ j \mid b_j = i \} $ is an interval, and for every $ i < j $, if $ \text{first}_j < \text{first}_i < \text{last}_j $, then $ \text{last}_i \leq \text{last}_j $.
**Final Formal Statement**
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $.
Let $ A = (a_1, \dots, a_n) \in \{0, 1, \dots, q\}^n $.
Let $ B = (b_1, \dots, b_n) \in \{1, \dots, q\}^n $ be a completion of $ A $, i.e., $ b_i = a_i $ if $ a_i \neq 0 $, and $ b_i \in \{1, \dots, q\} $ otherwise.
**Constraints**
1. For each $ i \in \{1, \dots, q\} $, define $ I_i = \{ j \in \{1, \dots, n\} \mid b_j = i \} $. Then $ I_i $ is a contiguous interval.
2. For all $ i < j $, if $ I_i \cap I_j \neq \emptyset $, then $ I_i \subseteq I_j $.
3. $ I_q \neq \emptyset $.
4. $ \bigcup_{i=1}^q I_i = \{1, \dots, n\} $.
**Objective**
Determine whether there exists a completion $ B $ satisfying (1)–(4). If yes, output any such $ B $. Otherwise, output "NO".