Ciorbă 是一种酸汤，由不同的蔬菜和肉类制成。传统上，它与辣椒、酸奶油和面包一起食用。右图显示了一碗美味的 Ciorbă de perișoare（肉丸汤）。

你已经厌倦了臭名昭著的旋转寿司传送带，因此决定去一家新型餐厅：Ciorbă 传送带！Ciorbă 碗被放置在两条传送带上，每条传送带都有 $n$ 个插槽。对于红色传送带（左侧那条），插槽按顺时针方向从 $0$ 到 $n-1$ 编号；对于蓝色传送带（右侧那条），插槽按逆时针方向从 $0$ 到 $n-1$ 编号。这两条传送带之间共共享了 $k$ 个插槽（$k$ 为偶数），具体来说，是编号为 $0, d, 2 \cdot d, \dots, (k-1) \cdot d$ 的插槽。因此，一共有 $2n-k$ 个碗，编号从 $0$ 到 $2n-k-1$。

初始时：

• 编号为 $0, 1, \dots, n-1$ 的碗被放置在红色传送带的插槽 $0, 1, \dots, n-1$ 中。
• 编号为 $n, n+1, \dots, 2n-k-1$ 的碗被放置在蓝色传送带的插槽 $0, 1, \dots, n-1$ 中，跳过共享的插槽。

在传送带旁有两个按钮：“R” 和 “A”。按下 “R” 按钮会将红色传送带顺时针旋转一个插槽，而按下 “A” 按钮会将蓝色传送带逆时针旋转一个插槽。

上图展示了 $n = 32, k = 6$ 且 $d = 3$ 时的传送带情况。按下一次 “R” 按钮会将碗 $0$ 移动到碗 $1$ 的插槽，碗 $1$ 移动到碗 $2$ 的插槽，……，碗 $31$ 移动到碗 $0$ 的插槽。按下一次 “A” 按钮会将碗 $0$ 移动到碗 $32$ 的插槽，碗 $32$ 移动到碗 $33$ 的插槽，碗 $33$ 移动到碗 $3$ 的插槽，……，碗 $57$ 移动到碗 $0$ 的插槽。

如果我们用 $b_0, b_1, \dots, b_{n-1}$ 表示传送带插槽 $0, 1, \dots, n-1$ 中碗的编号，那么该传送带的编码为以下数值：

$$0 \cdot b_0 + 1 \cdot b_1 + 2 \cdot b_2 + \dots + (n-1) \cdot b_{n-1}$$

给定 $n, k, d$ 和 $q$，以及一个包含 $q$ 次按钮按下的序列，请在执行完这些按钮操作后，求出两条传送带的编码，以便你可以享受无限量 Ciorbă 的一日通行证！

输入格式

第一行包含四个整数 $n, k, d$ 和 $q$（$3 \le n \le 10^6$，$2 \le k < n$，$k$ 为偶数，$1 \le d < n-1$，$1 \le q \le 10^6$）。此外，保证 $(k-1) \cdot d + 1 < n$。

第二行包含一个长度为 $q$ 的字符串，其中的字符只能是 “R” 或 “A”，代表按钮的按下序列。

输出格式

输出两行。第一行输出红色传送带的编码。第二行输出蓝色传送带的编码。

样例

输入样例 1

7 2 3 4
RRAA

输出样例 1

74
133

输入样例 2

32 6 3 2
RA

输出样例 2

11195
21666

说明

在第一个样例中，传送带的变化过程如下：

红色传送带的最终编码为 $0 \cdot 10 + 1 \cdot 6 + 2 \cdot 0 + 3 \cdot 7 + 4 \cdot 2 + 5 \cdot 3 + 6 \cdot 4 = 74$。

蓝色传送带的最终编码为 $0 \cdot 10 + 1 \cdot 11 + 2 \cdot 5 + 3 \cdot 7 + 4 \cdot 8 + 5 \cdot 1 + 6 \cdot 9 = 133$。

第二个样例描述了题目描述中图片所示的传送带。在按下按钮后，红色传送带上的碗依次为：

$57, 0, 1, 33, 3, 4, 35, 6, 7, 37, 9, 10, 39, 12, 13, 41, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30.$

蓝色传送带上的碗依次为：

$57, 31, 32, 33, 2, 34, 35, 5, 36, 37, 8, 38, 39, 11, 40, 41, 14, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56.$