Attack on Titan is a Japanese manga series written and illustrated by Hajime Isayama.
The story of Attack on Titan revolves around the adventures of Eren Yeager, his foster sister, Mikasa Ackerman, and their childhood friend Armin Arlert. After the wall which protects their hometown of Shinganshina is breached by the Colossal Titan leading the other Titans to enter, Eren watches in horror as one of them eats his mother. Vowing to kill all the Titans, Eren enlists in the military, along with his friends.
In the latest episode, they finally arrived the locked basement in Eren’s home. And found the question his father left on the table:
For an integer sequence a1,a2,...,an, we define its Titan scheme as the sequence s1,s2,...,sn−1 of symbols <, > or =. The symbol si represents the relation between ai and ai+1. For example, the Titan scheme of the sequence 2,4,3,3,5,3 is <,>,=,<,>.
We say that an integer sequence b1, b2, . . . , bn+1 with Titan scheme s1, s2, . . . , sn, realizes another Titan scheme s′1,s′2,...,s′k if for every i = 1,2,...,n it holds that si = s′((i−1) mod k)+1. In other words, the sequence s1, s2, . . . , sn can be obtained by repeating the sequence s′1, s′2, . . . , 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 a1,a2,...,an and a Titan scheme s1,s2,...,sk are given. Your task is to find the
longest subsequence ai1,ai2,...,aim(1 ≤ i1 < i2 < ... < im ≤ n) of the former that realizes the latter. The question is so hard. Could you help Eren to find the hope?
The first line contains an integer T (T ≤ 40), which indicates the number of test cases.
For each case, the first line contains two integers, k (1 ≤ n, k ≤ 500000), separated by a single space,
denoting the lengths of the sequences (ai) and Titan scheme (sj) respectively.
The second input line gives the sequence (ai), i.e, it holds n integers ai separated by single spaces
(1 ≤ ai ≤ 1000000).
Finally, the third lines gives the Titan scheme (sj), i.e., it holds k symbols sj of the form <, > or =
separated by single spaces.
For each case, output one line containing a single integer m, the maximum length of a subsequence of a1,a2,...,an that realizes the scheme s1,s2,...,sk.