A Very Interesting Construction Problem

Tags:

Description

众所周知，如果给定一个长度为$n$序列，问它的最长上升子序列的长度是多少。我们可以用$O(n log n)$时间复杂度的算法去轻松解决这个问题。

那么现在来考虑这样一个问题，给定一个正整数$k$, 一个长度为$n-1$且仅由 ‘<’ 或 ‘>’ 构成的字符串$S$，$S$中第$i$个字符(下标由$1$开始)代表了第$i$个元素和第$i+1$个元素的大小关系，如果第$i$个字符是'>'则代表第$i$个元素要大于第$i+1$个元素，如果第$i$个字符是'<'则代表第$i$个元素要小于第$i+1$个元素。

现在要求让你构造一个$1$到$n$的全排列（长度为$n$的序列并且$1$到$n$之间的每个数都只出现过一次 比如 1 3 2 就是一个$1$到$3$的全排列而 1 2 2 不是）使得满足以下条件：

1. 序列中相邻两个数的大小关系要满足$S$中的比较结果。
2. 该序列的最长上升子序列的长度恰好等于$k$。

Input

第一行两个正整数 $n$, $k$ ($2 \le n \le 2·10^{5}，1 \le k \le n$)。

第二行一个长度为$n-1$的字符串$S$。

Output

如果存在这样的一个$1$到$n$全排列满足条件，则请先在第一行输出“YES”,然后在第二行输出该全排列。若不存在则输出"NO"即可。

Samples

Hint

最长上升子序列问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长上升子序列中的元素在原序列中不一定是连续的。(来自百度百科)

本题采用Special Judge，即答案可能不唯一，你输出的答案只要满足题目中要求的限制即会被判定为正确。如果输出的序列长度与要求的不符或是序列不满足题目要求的限制都会被判定为错误。

Author