Problem: Little Gerald and his coach Mike play an interesting game. At the beginning of the game there is a pile consisting of n candies and a pile consisting of m stones. Gerald and Mike move in turns, Mike goes first. During his move Mike checks how many candies and stones Gerald has eaten. Let Gerald eat a candies and b stones. Then Mike awards Gerald f(a, b) prize points. Gerald during his move either eats a candy from the pile of candies or a stone from the pile of stones. As Mike sees that Gerald has eaten everything apart one candy and one stone, he awards points for the last time and the game ends. Gerald is not allowed to eat all the candies, and he is not allowed to eat all the stones too. Tell Gerald how to play to get the largest possible number of points: it is required to find one of the possible optimal playing strategies for Gerald.

Input

The first line contains three integers n, m, p (1 ≤ n, m ≤ 20000, 1 ≤ p ≤ 109). The second line contains n integers x0, x1, ..., xn - 1 (0 ≤ xi ≤ 20000). The third line contains m integers y0, y1, ..., ym - 1 (0 ≤ yi ≤ 20000). The value of f(a, b) is calculated as a remainder of the division of the sum xa + yb by number p.

Output

Print on the first line the only number: the maximal number of points Gerald can earn. Print on the second line a sting consisting of n + m - 2 characters, each of which is either a "C" or "S", the i-th character should be "C" if Gerald's i-th move should be eating a candy and "S" if he should eat a stone.

Examples

Input

2 2 10
0 0
0 1


Output

2
SC


Input

3 3 10
0 2 0
0 0 2


Output

10
CSSC


Input

3 3 2
0 1 1
1 1 0


Output

4
SCSC

Note

In the first test if Gerald's first move is eating a stone, he will receive a point for it and if he eats a candy, he will get zero pints. In any way Gerald will get 0 points before his first move, and 1 after his second one. This, the maximum number of points Gerald can get equals to 2, and for that he should first eat a stone, then a candy.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
int allocator_pos = 0;
char allocator_memory[(int)1e5];
inline void *operator new(size_t n) {
  char *res = allocator_memory + allocator_pos;
  allocator_pos += n;
  assert(allocator_pos <= (int)1e5);
  return (void *)res;
}
inline void operator delete(void *) noexcept {}
template <class T = int>
inline T readInt();
inline double readDouble();
inline int readUInt();
inline int readChar();
inline void readWord(char *s);
inline bool readLine(char *s);
inline bool isEof();
inline int getChar();
inline int peekChar();
inline bool seekEof();
inline void skipBlanks();
template <class T>
inline void writeInt(T x, char end = 0, int len = -1);
inline void writeChar(int x);
inline void writeWord(const char *s);
inline void writeDouble(double x, int len = 0);
inline void flush();
static struct buffer_flusher_t {
  ~buffer_flusher_t() { flush(); }
} buffer_flusher;
static const int buf_size = 4096;
static unsigned char buf[buf_size];
static int buf_len = 0, buf_pos = 0;
inline bool isEof() {
  if (buf_pos == buf_len) {
    buf_pos = 0, buf_len = fread(buf, 1, buf_size, stdin);
    if (buf_pos == buf_len) return 1;
  }
  return 0;
}
inline int getChar() { return isEof() ? -1 : buf[buf_pos++]; }
inline int peekChar() { return isEof() ? -1 : buf[buf_pos]; }
inline bool seekEof() {
  int c;
  while ((c = peekChar()) != -1 && c <= 32) buf_pos++;
  return c == -1;
}
inline void skipBlanks() {
  while (!isEof() && buf[buf_pos] <= 32U) buf_pos++;
}
inline int readChar() {
  int c = getChar();
  while (c != -1 && c <= 32) c = getChar();
  return c;
}
inline int readUInt() {
  int c = readChar(), x = 0;
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return x;
}
template <class T>
inline T readInt() {
  int s = 1, c = readChar();
  T x = 0;
  if (c == '-')
    s = -1, c = getChar();
  else if (c == '+')
    c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return s == 1 ? x : -x;
}
inline double readDouble() {
  int s = 1, c = readChar();
  double x = 0;
  if (c == '-') s = -1, c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  if (c == '.') {
    c = getChar();
    double coef = 1;
    while ('0' <= c && c <= '9') x += (c - '0') * (coef *= 1e-1), c = getChar();
  }
  return s == 1 ? x : -x;
}
inline void readWord(char *s) {
  int c = readChar();
  while (c > 32) *s++ = c, c = getChar();
  *s = 0;
}
inline bool readLine(char *s) {
  int c = getChar();
  while (c != '\n' && c != -1) *s++ = c, c = getChar();
  *s = 0;
  return c != -1;
}
static int write_buf_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x) {
  if (write_buf_pos == buf_size)
    fwrite(write_buf, 1, buf_size, stdout), write_buf_pos = 0;
  write_buf[write_buf_pos++] = x;
}
inline void flush() {
  if (write_buf_pos) {
    fwrite(write_buf, 1, write_buf_pos, stdout), write_buf_pos = 0;
    fflush(stdout);
  }
}
template <class T>
inline void writeInt(T x, char end, int output_len) {
  if (x < 0) writeChar('-'), x = -x;
  char s[24];
  int n = 0;
  while (x || !n) s[n++] = '0' + x % 10, x /= 10;
  while (n < output_len) s[n++] = '0';
  while (n--) writeChar(s[n]);
  if (end) writeChar(end);
}
inline void writeWord(const char *s) {
  while (*s) writeChar(*s++);
}
inline void writeDouble(double x, int output_len) {
  if (x < 0) writeChar('-'), x = -x;
  int t = (int)x;
  writeInt(t), x -= t;
  writeChar('.');
  for (int i = output_len - 1; i > 0; i--) {
    x *= 10;
    t = std::min(9, (int)x);
    writeChar('0' + t), x -= t;
  }
  x *= 10;
  t = std::min(9, (int)(x + 0.5));
  writeChar('0' + t);
}
#pragma GCC optimaze("O3,unroll-loops")
#pragma GCC target("sse4,sse3,sse2,sse")
using namespace std;
int a[20005], b[20005], n, m, p;
int dp1[3][20005], dp2[3][20005];
int f(int x, int y) { return (a[x] + b[y]) % p; }
void get_ans(int x1, int y1, int x2, int y2) {
  if (x1 == x2) {
    for (int i = y1; i < y2; i++) writeChar('S');
    return;
  }
  if (y1 == y2) {
    for (int i = x1; i < x2; i++) writeChar('C');
    return;
  }
  int mid = (x1 + y1 + x2 + y2) / 2;
  dp1[0][x2] = f(n - x2, m - y2);
  int x = 0, y = 0, i1, i2;
  for (i1 = x2 + y2, i2 = x1 + y1; i1 > mid && i2 < mid; i1--, i2++) {
    for (int j = max(x1, i1 - y2); j <= min(x2, i1 - y1); j++) {
      int z = i1 - j;
      if (j != x1)
        dp1[x ^ 1][j - 1] =
            max(dp1[x ^ 1][j - 1], dp1[x][j] + f(n - j + 1, m - z));
      if (z != y1)
        dp1[x ^ 1][j] = max(dp1[x ^ 1][j], dp1[x][j] + f(n - j, m - z + 1));
      dp1[x][j] = 0;
    }
    x ^= 1;
    for (int j = max(x1, i2 - y2); j <= min(x2, i2 - y1); j++) {
      int z = i2 - j;
      if (j != x2)
        dp2[y ^ 1][j + 1] = max(dp2[y ^ 1][j + 1], dp2[y][j] + f(n - j, m - z));
      if (z != y2)
        dp2[y ^ 1][j] = max(dp2[y ^ 1][j], dp2[y][j] + f(n - j, m - z));
      dp2[y][j] = 0;
    }
    y ^= 1;
  }
  if (i1 > mid) {
    for (int j = max(x1, i1 - y2); j <= min(x2, i1 - y1); j++) {
      int z = i1 - j;
      if (j != x1)
        dp1[x ^ 1][j - 1] =
            max(dp1[x ^ 1][j - 1], dp1[x][j] + f(n - j + 1, m - z));
      if (z != y1)
        dp1[x ^ 1][j] = max(dp1[x ^ 1][j], dp1[x][j] + f(n - j, m - z + 1));
      dp1[x][j] = 0;
    }
    x ^= 1;
  }
  if (i2 < mid) {
    for (int j = max(x1, i2 - y2); j <= min(x2, i2 - y1); j++) {
      int z = i2 - j;
      if (j != x2)
        dp2[y ^ 1][j + 1] = max(dp2[y ^ 1][j + 1], dp2[y][j] + f(n - j, m - z));
      if (z != y2)
        dp2[y ^ 1][j] = max(dp2[y ^ 1][j], dp2[y][j] + f(n - j, m - z));
      dp2[y][j] = 0;
    }
    y ^= 1;
  }
  int posx = -1, tek = -1;
  for (int i = max(x1, mid - y2); i <= min(x2, mid - y1); i++) {
    if (tek < dp1[x][i] + dp2[y][i]) posx = i, tek = dp1[x][i] + dp2[y][i];
    dp1[x][i] = 0, dp2[y][i] = 0;
  }
  if (x1 == 1 && y1 == 1 && x2 == n && y2 == m) {
    writeInt(tek);
    writeChar('\n');
  }
  get_ans(posx, mid - posx, x2, y2);
  get_ans(x1, y1, posx, mid - posx);
  return;
}
int main() {
  n = readInt();
  m = readInt();
  p = readInt();
  for (int i = 0; i < n; i++) a[i] = readInt();
  for (int i = 0; i < m; i++) b[i] = readInt();
  if (n == 1) {
    int ans = 0;
    for (int i = 0; i < m; i++) ans += f(0, i);
    writeInt(ans);
    writeChar('\n');
    for (int i = 1; i < m; i++) writeChar('S');
    exit(0);
  }
  if (m == 1) {
    int ans = 0;
    for (int i = 0; i < n; i++) ans += f(i, 0);
    writeInt(ans);
    writeChar('\n');
    for (int i = 1; i < n; i++) writeChar('C');
    exit(0);
  }
  get_ans(1, 1, n, m);
  return 0;
}