Monotonic Subsequence

Given an integer sequence (a_1, a_2, \cdots, a_n) and a monotonic pattern (p_1, p_2, \cdots, p_k) where each (p_i) is one of the symbols ( < ), ( > ) or ( = ), we say that a subsequence (b_1, b_2, \cdots, b_m) of (a) (with (1 \le i_1 < i_2 < \cdots < i_m \le n)) has a monotonic sequence defined by the relation between consecutive elements. More precisely, for each (1 \le j \le m-1), the relation between (b_j) and (b_{j+1}) is defined as follows: [ \text{relation}(b_j,b_{j+1}) = \begin{cases} < & \text{if } b_j < b_{j+1},\[6pt] > & \text{if } b_j > b_{j+1},\[6pt] = & \text{if } b_j = b_{j+1}. \end{cases} ] We say that the monotonic sequence of the subsequence (b) "realizes" the pattern (p_1, p_2, \cdots, p_k) if for all (1 \le j \le m-1) we have [ \text{relation}(b_j,b_{j+1}) = p_{((j-1) \bmod k) + 1}. ] Your task is to find the longest subsequence of (a) whose monotonic sequence realizes the given pattern. If there are multiple answers, any one of them is acceptable.

Input Format:
The first line contains two integers (n) and (k).
The second line contains (n) integers (a_1, a_2, \cdots, a_n).
The third line contains a string of length (k) consisting only of the characters '<', '>' and '=' (representing the pattern (p_1, p_2, \cdots, p_k)).

Output Format:
The first line should contain a single integer (m), the length of the longest subsequence found.
The second line should contain (m) integers representing the subsequence (in the order they appear in (a)), separated by spaces.

Example: For the input:

6 3
2 4 3 3 5 3
=

One acceptable output is:

6
2 4 3 3 5 3

Explanation: The monotonic sequence of the subsequence is <, >, =, <, >, which realizes the pattern <, >, = since it is exactly the repetition of the pattern.

Note: A subsequence with a single element ((m=1)) is always considered valid as its monotonic sequence is empty, and hence trivially realizes any pattern.

inputFormat

The input consists of three lines. The first line contains two integers (n) (the number of elements in the sequence) and (k) (the length of the pattern). The second line contains (n) space-separated integers (a_1, a_2, \cdots, a_n). The third line contains a string of length (k) made up of the characters '<', '>', and '=' representing the pattern.

outputFormat

Output two lines. The first line contains a single integer (m), the length of the longest subsequence whose monotonic sequence realizes the given pattern. The second line contains (m) space-separated integers which are the elements of that subsequence in their original order.

sample

6 3
2 4 3 3 5 3
=

6
2 4 3 3 5 3