Problem Description

Translated from POI 2010 Stage 3. Day 0 “Monotonicity”.

For an integer sequence $a_1, a_2, \cdots, a_n$, we define its “monotonic sequence” as a symbol sequence $s_1, s_2, \cdots, s_{n-1}$ consisting of $<$, $>$, and $=$, where the symbol $s_i$ represents the relation between $a_i$ and $a_{i+1}$. For example, the monotonic sequence of $2, 4, 3, 3, 5, 3$ is $<, >, =, <, >$.

For an integer sequence $b_1, b_2, \cdots, b_{n+1}$ and its monotonic sequence $s_1, s_2, \cdots, s_n$, if a symbol sequence $s_1', s_2', \cdots, s_k'$ satisfies that for all $1 \le i \le n$ we have $s_i = s_{((i - 1) \bmod n) + 1}'$, then we say the sequence $s_1, s_2, \cdots, s_n$ “implements” the sequence $s_1', s_2', \cdots, s_k'$. In other words, the sequence $s_1, s_2, \cdots, s_n$ can be obtained by repeating the sequence $s_1', s_2', \cdots, s_k'$ multiple times and then deleting a suffix. For example, the integer sequence $2, 4, 3, 3, 5, 3$ implements at least the following symbol sequences:

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

Given an integer sequence $a_1, a_2, \cdots, a_n$ and a monotonic sequence $s_1, s_2, \cdots, s_k$, find the longest subsequence $a_{i_1}, a_{i_2}, \cdots, a_{i_m}$ $(1 \le i_1 \lt i_2 \lt \cdots \lt i_m \le n)$ such that the monotonic sequence of the subsequence implements the given symbol sequence.

Input Format

The first line contains two integers $n, k$ separated by spaces, representing the length of the integer sequence $a_i$ and the length of the monotonic sequence $s_j$.

The second line contains $n$ integers separated by spaces, representing the sequence $a_i$.

The third line contains $k$ symbols separated by spaces, representing the symbol sequence $s_j$.

Output Format

The first line outputs an integer $m$, representing the length of the longest subsequence of $a_1, a_2, \cdots, a_n$ whose monotonic sequence “implements” the monotonic sequence $s_1, s_2, \cdots, s_n$.

The second line outputs any such subsequence $a_{i_1}, a_{i_2}, \cdots, a_{i_n}$, with elements separated by spaces.

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

6
2 4 3 3 5 3

Hint

For $100\%$ of the testdata, $1 \le n \le 20000$, $1 \le k \le 100$, $1 \le a_i \le 1000000$, $s_j \in \{<, >, =\}$.

Translated by ChatGPT 5