Longest Subsequence Realizing a Given Monotonicity Scheme

You are given an integer sequence (A = (a_1, a_2, \dots, a_n)) and a monotonicity scheme (P = (p_1, p_2, \dots, p_m)), where each (p_i) is one of the symbols (\langle), (=), or (\rangle). The monotonicity scheme of a sequence (B = (b_1, b_2, \dots, b_k)) is defined as the sequence of relations between consecutive elements, i.e. for each (1 \le i < k) the relation is: [ r_i = \begin{cases} \langle, & \text{if } b_i < b_{i+1},\ =, & \text{if } b_i = b_{i+1},\ \rangle, & \text{if } b_i > b_{i+1}. \end{cases} ] We say that the sequence (B) realizes the monotonicity scheme (P) if its monotonicity scheme ( (r_1, r_2, \dots, r_{k-1}) ) is a prefix of the infinite repetition of (P); that is, for every (1 \le i < k) it holds that [ r_i = p_{((i-1) \bmod m) + 1}. ] Your task is to find the longest subsequence (not necessarily contiguous) of (A) that realizes the given monotonicity scheme (P). If there are several such subsequences, you may output any one of them.

Input Format: The input consists of multiple lines. The first line contains two integers (n) and (m) denoting the length of the sequence (A) and the length of the monotonicity scheme (P), respectively. The second line contains (n) integers (a_1, a_2, \dots, a_n). The third line contains a string of (m) characters (each character is one of '<', '=', '>') representing the scheme (P).

Output Format: Output one line containing the elements of the longest subsequence that realizes the scheme, separated by a single space.

inputFormat

The input begins with a line containing two integers (n) and (m) (the length of the sequence and the length of the monotonicity scheme, respectively). The next line contains (n) space-separated integers. The third line contains a string of length (m) composed solely of the characters '<', '=', '>' representing the pattern (P).

outputFormat

Output a single line with the elements of the longest subsequence (space-separated) that realizes the infinite repetition of the given monotonicity scheme.

sample

5 2
1 2 3 2 4

1 3 2 4