E. Конфеты и Камни
ограничение по времени на тест
7.5 seconds
ограничение по памяти на тест
45 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Мальчик Геральд и его тренер Миша играют в интересную игру. В начале игры имеются куча из n конфет и куча из m камней. Геральд и Миша ходят по очереди, первым ходит Миша. Миша на своем ходу проверят, сколько на данный момент Геральд съел конфет и камней. Пусть Геральд съел a конфет и b камней. Тогда Миша начисляет Геральду 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-ый символ должен быть «C», если на своем i-ом ходу Геральд должен съесть конфету, и «S», если камень.

Примеры
Входные данные
2 2 10
0 0
0 1
Выходные данные
2
SC
Входные данные
3 3 10
0 2 0
0 0 2
Выходные данные
10
CSSC
Входные данные
3 3 2
0 1 1
1 1 0
Выходные данные
4
SCSC
Примечание

В первом тесте, если на первом ходу Геральд съест камень, то после него он получит одно очко, а если конфету — то ноль. Перед первым своим ходом Геральд получит в любом случае 0 очков, а после второго — в любом случае 1. Таким образом, максимальное количество очков, которое может получить Геральд равно 2, и для этого надо съесть сначала камень, потом конфету.