小杰拉德和他的教练迈克玩了一个有趣的游戏。游戏开始时有一堆由 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,为此他应该先吃一块石头,然后吃一块糖果。