← 返回题目列表

Codeforces · 101/E

E. 糖果和石头

中文机器翻译题面 查看原题

小杰拉德和他的教练迈克玩了一个有趣的游戏。游戏开始时有一堆由 n 个糖果组成的堆和一堆由 m 个石头组成的堆。杰拉德和迈克轮流移动,迈克先走。在移动过程中,迈克检查杰拉德吃了多少糖果和石头。让杰拉德吃a糖果和b石头。然后 Mike 授予 Gerald f(a, b) 奖励积分。杰拉德在移动过程中要么从糖果堆中吃一颗糖果,要么从石堆中吃一颗石头。当迈克看到杰拉德把所有东西都吃光了,只剩下一颗糖果和一颗石头时,他最后一次奖励积分,游戏结束。杰拉德不被允许吃掉所有的糖果,也不被允许吃掉所有的石头。告诉杰拉德如何玩才能获得尽可能多的分数:需要为杰拉德找到一种可能的最佳策略。

输入

第一行包含三个整数 n、m、p (1 ≤ n, m ≤ 20000, 1 ≤ p ≤ 109)。第二行包含 n 个整数 x0, x1, ..., xn - 1 (0 ≤ xi ≤ 20000)。第三行包含 m 个整数 y0, y1, ..., ym - 1 (0 ≤ yi ≤ 20000)。 f(a, b) 的值计算为总和 xa + yb 除以数字 p 的余数。

输出

在第一行打印唯一的数字:杰拉德可以获得的最大分数。在第二行打印一个由 n + m - 2 个字符组成的字符串,每个字符要么是“C”,要么是“S”,如果杰拉尔德的第 i 个动作应该吃糖果,则第 i 个字符应该是“C”;如果他应该吃石头,则第 i 个字符应该是“S”。

示例

输入 #1

2 2 10
0 0
0 1

输出 #1

2
SC

输入 #2

3 3 10
0 2 0
0 0 2

输出 #2

10
CSSC

输入 #3

3 3 2
0 1 1
1 1 0

输出 #3

4
SCSC

注意

在第一个测试中,如果杰拉德的第一步是吃石头,他将获得一分,如果他吃糖果,他将获得零品脱。无论如何,杰拉德在第一次行动之前将得到 0 分,而在第二次行动之后将得到 1 分。这样,杰拉德可以获得的最大分数等于 2,为此他应该先吃一块石头,然后吃一块糖果。