{"problem":{"name":"E. Candies and Stones","description":{"content":"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, Mi","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":7000,"memory_limit":46080},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF101E"},"statements":[{"statement_type":"Markdown","content":"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.\n\n## Input\n\nThe first line contains three integers _n_, _m_, _p_ (1 ≤ _n_, _m_ ≤ 20000, 1 ≤ _p_ ≤ 109). The second line contains _n_ integers _x_0, _x_1, ..., _x__n_ - 1 (0 ≤ _x__i_ ≤ 20000). The third line contains _m_ integers _y_0, _y_1, ..., _y__m_ - 1 (0 ≤ _y__i_ ≤ 20000). The value of _f_(_a_, _b_) is calculated as a remainder of the division of the sum _x__a_ + _y__b_ by number _p_.\n\n## Output\n\nPrint 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.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"小杰拉尔德和他的教练迈克玩一个有趣的游戏。游戏开始时，有一堆包含 #cf_span[n] 颗糖果和一堆包含 #cf_span[m] 颗石头。杰拉尔德和迈克轮流行动，迈克先手。在迈克的回合中，他会检查杰拉尔德吃掉了多少糖果和石头。设杰拉尔德吃了 #cf_span[a] 颗糖果和 #cf_span[b] 颗石头，则迈克会奖励杰拉尔德 #cf_span[f(a, b)] 个奖分。杰拉尔德在自己的回合中，要么从糖果堆中吃掉一颗糖果，要么从石头堆中吃掉一颗石头。当迈克发现杰拉尔德已经吃掉了除了最后一颗糖果和最后一颗石头之外的所有物品时，他会最后一次奖励分数，游戏结束。杰拉尔德不允许吃掉所有的糖果，也不允许吃掉所有的石头。请告诉杰拉尔德如何玩才能获得尽可能多的分数：你需要找出杰拉尔德的一种可能的最优策略。\n\n第一行包含三个整数 #cf_span[n, m, p]（#cf_span[1 ≤ n, m ≤ 20000]，#cf_span[1 ≤ p ≤ 10^9]）。第二行包含 #cf_span[n] 个整数 #cf_span[x0], #cf_span[x1], ..., #cf_span[xn - 1]（#cf_span[0 ≤ xi ≤ 20000]）。第三行包含 #cf_span[m] 个整数 #cf_span[y0], #cf_span[y1], ..., #cf_span[ym - 1]（#cf_span[0 ≤ yi ≤ 20000]）。#cf_span[f(a, b)] 的值被计算为 #cf_span[xa + yb] 除以 #cf_span[p] 的余数。\n\n请在第一行输出一个数字：杰拉尔德能获得的最大分数。在第二行输出一个长度为 #cf_span[n + m - 2] 的字符串，每个字符为 \"_C_\" 或 \"_S_\"，第 #cf_span[i] 个字符为 \"_C_\" 表示杰拉尔德第 #cf_span[i] 次行动应吃掉一颗糖果，为 \"_S_\" 表示应吃掉一颗石头。\n\n在第一个测试中，如果杰拉尔德第一步吃石头，他会得到一分；如果吃糖果，他会得零分。无论如何，杰拉尔德在第一次行动前得 #cf_span[0] 分，第二次行动后得 #cf_span[1] 分。因此，杰拉尔德能获得的最大分数为 #cf_span[2]，为此他应先吃石头，再吃糖果。\n\n## Input\n\n第一行包含三个整数 #cf_span[n, m, p]（#cf_span[1 ≤ n, m ≤ 20000]，#cf_span[1 ≤ p ≤ 10^9]）。第二行包含 #cf_span[n] 个整数 #cf_span[x0], #cf_span[x1], ..., #cf_span[xn - 1]（#cf_span[0 ≤ xi ≤ 20000]）。第三行包含 #cf_span[m] 个整数 #cf_span[y0], #cf_span[y1], ..., #cf_span[ym - 1]（#cf_span[0 ≤ yi ≤ 20000]）。#cf_span[f(a, b)] 的值被计算为 #cf_span[xa + yb] 除以 #cf_span[p] 的余数。\n\n## Output\n\n请在第一行输出一个数字：杰拉尔德能获得的最大分数。在第二行输出一个长度为 #cf_span[n + m - 2] 的字符串，每个字符为 \"_C_\" 或 \"_S_\"，第 #cf_span[i] 个字符为 \"_C_\" 表示杰拉尔德第 #cf_span[i] 次行动应吃掉一颗糖果，为 \"_S_\" 表示应吃掉一颗石头。\n\n[samples]\n\n## Note\n\n在第一个测试中，如果杰拉尔德第一步吃石头，他会得到一分；如果吃糖果，他会得零分。无论如何，杰拉尔德在第一次行动前得 #cf_span[0] 分，第二次行动后得 #cf_span[1] 分。因此，杰拉尔德能获得的最大分数为 #cf_span[2]，为此他应先吃石头，再吃糖果。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m, p \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 20000 $, $ 1 \\leq p \\leq 10^9 $.  \nLet $ X = (x_0, x_1, \\dots, x_{n-1}) \\in \\mathbb{Z}^n $, $ Y = (y_0, y_1, \\dots, y_{m-1}) \\in \\mathbb{Z}^m $.  \nDefine the reward function:  \n$$ f(a, b) = (x_a + y_b) \\bmod p $$  \nfor $ 0 \\leq a < n $, $ 0 \\leq b < m $.  \n\n**Constraints**  \n1. Gerald starts with $ 0 $ candies and $ 0 $ stones eaten.  \n2. Gerald must make exactly $ n + m - 2 $ moves:  \n   - Eat $ n-1 $ candies (leaving 1 candy).  \n   - Eat $ m-1 $ stones (leaving 1 stone).  \n3. At any move, Gerald may eat either one candy (if any remain) or one stone (if any remain).  \n4. After each move $ i $, if Gerald has eaten $ a $ candies and $ b $ stones, he receives $ f(a, b) $ points.  \n5. The final state is $ (a = n-1, b = m-1) $, and the last reward is computed at that state.  \n\n**Objective**  \nMaximize the total reward:  \n$$\n\\sum_{i=1}^{n+m-2} f(a_i, b_i)\n$$  \nwhere $ (a_i, b_i) $ is the state (candies and stones eaten) after the $ i $-th move, starting from $ (0,0) $ and ending at $ (n-1, m-1) $, with each move increasing either $ a $ or $ b $ by 1.  \n\nFind a sequence of $ n + m - 2 $ moves (each 'C' or 'S') achieving the maximum total reward.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF101E","tags":["divide and conquer","dp"],"sample_group":[["2 2 10\n0 0\n0 1","2\nSC"],["3 3 10\n0 2 0\n0 0 2","10\nCSSC"],["3 3 2\n0 1 1\n1 1 0","4\nSCSC"]],"created_at":"2026-03-03 11:00:39"}}