Finales are born to be exciting. Performers play hard to draw audiences’ attention and then take a perfect curtain call. As the last problem and the finale of the problem set, however, we want you to recall a simple algorithm. Like me, it may be the first algorithm you’ve learned, called Bubble Sort.
Given a permutation of length , as you might know, Bubble Sort runs in in the worst case. It’s quite a traditional idea to count the number of calls of 「swap」 in the algorithm. As you are stronger now, you want to count that number in a dynamic permutation with the following events that might happen:
Reverse the permutation, meaning that the permutation is replaced with
Shift the permutation to the left by , meaning that the permutation is replaced with
All you need to do is to output the number of 「swap」 that would be called if we sort the permutation with the above Bubble Sort code after each operation.
The first line contains two integers (, ), denoting the length of permutation and the number of operations.
The second line contains integers separated by spaces, and the -th denotes the initial .
The third line contains a single string containing $$$$ letters consisting of 『R』 and 『S』. The -th letter denotes the -th operation, where 『R』 or 『S』 denotes the Reverse or Shift operation, respectively.
It’s guaranteed that forms a correct permutation of .
In the first line, print the number of 「swap」 would be called when Bubble Sort the initial .
In the second line, print a single string of digits. The -th denotes the number of 「swap」 would be called to Bubble Sort the permutation, modulo .
5 10 5 4 3 2 1 SSSSRSSSSR
给出一个长度为 的排列 和 次操作，操作 可以将 移到数组的最右侧，操作 可以倒置数组，求初始数组和每次操作后逆序对的数量。
进行 Shift 操作时，逆序对的数量要减去原来第一个数的逆序对的数量，除此之外还要减去移动后的正序对的数量。
进行 Reverse 操作时，逆序对的数量会变为原数组的正序对的数量。