题目描述

我们希望你能回忆起一个简单的算法。和我一样，这可能是你学习的第一个算法，叫做 "冒泡排序"。

void bubble_sort(int a[], int n) { // 0-based, sort from lowest to highest
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        } // after i-th inner iteration, a[n - i] is correct
    }
}

正如你可能知道的，给定一个长度为 $n$ 的排列，在最坏的情况下，冒泡排序的运行时间为 $\Omega (n ^ 2)$ 。计算算法中调用swap的次数是一个非常传统的想法。正如你现在所做的，你想在可能发生以下事件的动态排列中计算这个次数：

1. Reverse:反向排列，即排列替换为

$$p' = {p _n, p _{n-1}, p _{n-2}\dots,p _3, p _2, p _ 1} $$

2. Shift:将排列向左移动$1$ ,即排列替换为

$$p' = {p_2, p_3,p_4, \dots, p _{n-1}, p_n, p_1}$$

您所需要做的就是在每次操作后，输出如果我们使用上述泡排序代码对排列进行排序，所调用的 "交换 "次数。

输入格式

第一行包含两个整数 $n, m (1 \leq n \leq 1 \times 10 ^ 3, 1 \leq m \leq 6 \times 10 ^ 5)$ ，分别表示序列长度和操作次数。
第二行包含用空格分隔的$n$个整数，其中 $i$ 表示初始 $p _i$ 。
第三行包含一个由 $m$ 个字母组成的字符串，这些字母由 R和 S组成。
字母 $i$ -th表示 $i$ -th操作，其中R或S分别表示Reverse或Shift操作。
可以保证 $p$ 构成 $1, 2, \dots, n$ 的正确排列。

输出格式

第一行，打印排序初始 $p$ 时调用的 swap次数。
在第二行中，打印一个由 $m$ 个数字组成的字符串
$i$ -表示调用swap来对当前序列进行排序的次数对$10$取余数的结果

样例

5 10
5 4 3 2 1
SSSSRSSSSR

10
6446466400