#3009. 「POI2010」单调性 2 Monotonicity 2

题目描述

本题是来自 POI 2010 第三阶段的单调性一题的加强版，但并没有在那次比赛中被使用。

译自 POI 2010 「Monotonicity 2」

对于一个整数序列 $a_1, a_2, \ldots, a_n$，我们定义其"单调序列"为一个由 $<$，$>$ 和 $=$ 组成的符号序列 $s_1, s_2, \ldots s_{n-1}$，其中符号 $s_i$ 表示 $a_i$ 和 $a_{i+1}$ 之间的关系。例如，数列 $2, 4, 3, 3, 5, 3$ 的单调序列为 $<, >, =, <, >$。

对于整数序列 $b_1, b_2, \ldots, b_{n+1}$ 以及其单调序列 $s_1, s_2, \ldots, s_n$，如果符号序列 $s'_1, s'_2, \ldots, s'_k$ 满足对所有 $1 \le i \le n$ 有 $s_i = s'_{((i - 1) \bmod n) + 1}$，我们就说序列 $s_1, s_2, \ldots, s_n$ 实现了序列 $s'_1, s'_2, \ldots, s'_k$。也就是说，序列 $s_1, s_2, \ldots, s_n$ 可以通过重复多次 $s'_1, s'_2, \ldots, s'_k$ 序列并删除一个后缀得到。例如，整数数列 $2, 4, 3, 3, 5, 3$ 至少实现了以下符号序列：

• $<, >, =$
• $<, >, =, <, >$
• $<, >, =, <, >, <, <, =$
• $<, >, =, <, >, =, >, >$

给定一个整数序列 $a_1, a_2, \ldots, a_n$ 以及一个单调序列 $s_1, s_2, \ldots, s_k$，求出原整数序列最长的子序列 $a_{i_1}, a_{i_2}, \ldots, a_{i_m}$ $(1 \le i_1 \lt i_2 \lt \ldots \lt i_m \le n)$ 使得前者的单调序列实现后者的符号序列。

输入格式

第一行包含用空格分隔的两个整数 $n,k$，分别表示整数序列 $(a_i)$ 的长度和单调序列 $(s_j)$ 的长度。

第二行包含用空格分隔的 $n$ 个整数，表示序列 $a_i$。

第三行包含用空格分隔的 $k$ 个符号，表示符号序列 $s_j$。

输出格式

第一行输出一个整数 $m$，表示序列 $a_1, a_2, \ldots, a_n$ 的最长的「实现」了单调序列 $s_1, s_2, \ldots, s_n$ 的子序列。

第二行输出任意一个这样的子序列 $a_{i_1}, a_{i_2}, \ldots, a_{i_n}$，元素之间用空格分隔。

样例

输入

7 3
2 4 3 1 3 5 3
< > =

输出

6
2 4 3 3 5 3

数据范围与提示

对于 $100\%$ 的数据，
$1 \le n \le 500000$，
$1 \le k \le 500000$，
$1 \le a_i \le 1000000$，
$s_j \in \{<, >, =\}$。

Translated by vincent163