8195번 - Monotonicity 2 스페셜 저지다국어

For an integer sequence a₁,a₂,…,a_n we define its monotonicity scheme as the sequence s₁,s₂,…,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₁,b₂,…,b_n+1 with monotonicity scheme s₁,s₂,…,s_n, realizes another monotonicity scheme s’₁,s’₂,…,s’_k if for every i=1,2,…,n it holds that s_i=s'_{((i-1) mod k) + 1}. In other words, the sequence s₁,s₂,…,s_n can be obtained by repeating the sequence  s’₁,s’₂,…,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₁,a₂,…,a_n and a monotonicity scheme s₁,s₂,…,s_k are given. Your task is to find the longest subsequence a_i1,a_i2,…,a_im (1 ≤ i₁ < i₂ < … < i_m ≤ n) of the former that realizes the latter.

The first line of the standard input holds two integers n and k (1 ≤ n ≤ 500,000, 1 ≤ k ≤ 500,000), 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 ai 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 sj of the form <, > or = separated by single spaces.

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₁,a₂,…,a_n that realizes the scheme s₁,s₂,…,s_k.

In the second line it should print out any such subsequence a_i1,a_i2,…,a_im, separating its elements by single spaces.