This task is a harder version of task Monotonicity from the third stage of 17th Polish OI. It wasn't used in the contest itself.
For an integer sequence $a_1,a_2,…,a_n$ we define its monotonicity scheme as the sequence $s_1,s_2,…,s_{n-1}$ of symbols <, > or =. The symbol $s_i$ represents the relation between $a_i$ and $a_{i+1}$. For example, the monotonicity scheme of the sequence 2,4,3,3,5,3 is <, >, =, <, >.
We say that an integer sequence $b_1,b_2,…,b_{n+1}$ with monotonicity scheme $s_1,s_2,…,s_n$, realizes another monotonicity scheme $s'_1,s'_2,…,s'_k$ if for every $i=1,2,…,n$ it holds that $s_i=s'_{(i-1) \bmod k} + 1$. In other words, the sequence $s_1,s_2,…,s_n$ can be obtained by repeating the sequence $s'_1,s'_2,…,s'_k$ and removing appropriate suffix from that repetition. For example, the sequence 2,4,3,3,5,3 realizes each and every one of the following schemes:
<,>,=<,>,=,<,><,>,=,<,>,<,<,=<,>,=,<,>,=,>,>
as well as many others.
An integer sequence $a_1,a_2,…,a_n$ and a monotonicity scheme $s_1,s_2,…,s_k$ are given. Your task is to find the longest subsequence $a_{i_1},a_{i_2},…,a_{i_m}$ ($1 ≤ i_1 < i_2 < … < i_m ≤ n$) of the former that realizes the latter.
Input
The first line of the standard input holds two integers $n$ and $k$ ($1 ≤ n ≤ 20\,000$, $1 ≤ k ≤ 100$), separated by a single space, denoting the lengths of the sequences ($a_i$) and monotonicity scheme ($s_j$) respectively.
The second input line gives the sequence ($a_i$), i.e, it holds $n$ integers $a_i$ separated by single spaces ($1 ≤ a_i ≤ 1\,000\,000$).
Finally, the third lines gives the monotonicity scheme ($s_j$), i.e., it holds $k$ symbols $s_j$ of the form <, > or = separated by single spaces.
Output
In the first line of the standard output your program should print out a single integer $m$, the maximum length of a subsequence of $a_1,a_2,…,a_n$ that realizes the scheme $s_1,s_2,…,s_k$.
In the second line it should print out any such subsequence $a_{i_1},a_{i_2},…,a_{i_m}$, separating its elements by single spaces.
Example
Input
7 3 2 4 3 1 3 5 3 < > =
Output
6 2 4 3 3 5 3