{"problem":{"name":"E. Lock Puzzle","description":{"content":"Welcome to another task about breaking the code lock! Explorers Whitfield and Martin came across an unusual safe, inside of which, according to rumors, there are untold riches, among which one can fin","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF937E"},"statements":[{"statement_type":"Markdown","content":"Welcome to another task about breaking the code lock! Explorers Whitfield and Martin came across an unusual safe, inside of which, according to rumors, there are untold riches, among which one can find the solution of the problem of discrete logarithm!\n\nOf course, there is a code lock is installed on the safe. The lock has a screen that displays a string of _n_ lowercase Latin letters. Initially, the screen displays string _s_. Whitfield and Martin found out that the safe will open when string _t_ will be displayed on the screen.\n\nThe string on the screen can be changed using the operation «_shift_ _x_». In order to apply this operation, explorers choose an integer _x_ from 0 to _n_ inclusive. After that, the current string _p_ = αβ changes to β_R_α, where the length of β is _x_, and the length of α is _n_ - _x_. In other words, the suffix of the length _x_ of string _p_ is reversed and moved to the beginning of the string. For example, after the operation «_shift_ 4» the string «_abcacb_» will be changed with string «_bcacab_ », since α = _ab_, β = _cacb_, β_R_ = _bcac_.\n\nExplorers are afraid that if they apply too many operations «_shift_», the lock will be locked forever. They ask you to find a way to get the string _t_ on the screen, using no more than 6100 operations.\n\n## Input\n\nThe first line contains an integer _n_, the length of the strings _s_ and _t_ (1 ≤ _n_ ≤ 2 000).\n\nAfter that, there are two strings _s_ and _t_, consisting of _n_ lowercase Latin letters each.\n\n## Output\n\nIf it is impossible to get string _t_ from string _s_ using no more than 6100 operations «_shift_», print a single number  - 1.\n\nOtherwise, in the first line output the number of operations _k_ (0 ≤ _k_ ≤ 6100). In the next line output _k_ numbers _x__i_ corresponding to the operations «_shift_ _x__i_» (0 ≤ _x__i_ ≤ _n_) in the order in which they should be applied.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"欢迎来到另一个破解密码锁的任务！探险家 Whitfield 和 Martin 发现了一个不寻常的保险箱，据传言，里面藏有无尽的财宝，其中甚至包括离散对数问题的解！\n\n当然，保险箱上安装了一个密码锁。锁的屏幕会显示一个由 #cf_span[n] 个小写拉丁字母组成的字符串。初始时，屏幕显示字符串 #cf_span[s]。Whitfield 和 Martin 发现，当屏幕显示字符串 #cf_span[t] 时，保险箱就会打开。\n\n可以通过操作 «_shift_ #cf_span[x]» 来改变屏幕上的字符串。为了执行此操作，探险家们选择一个整数 #cf_span[x]，范围从 0 到 #cf_span[n]（包含两端）。随后，当前字符串 #cf_span[p = αβ] 会变为 #cf_span[βRα]，其中 #cf_span[β] 的长度为 #cf_span[x]，#cf_span[α] 的长度为 #cf_span[n - x]。换句话说，字符串 #cf_span[p] 的长度为 #cf_span[x] 的后缀被反转后移动到字符串的开头。例如，执行 «_shift_ #cf_span[4]» 后，字符串 «_abcacb_» 会变为 «_bcacab_»，因为 #cf_span[α = ]_ab_，#cf_span[β = ]_cacb_，#cf_span[βR = ]_bcac_。\n\n探险家们担心，如果执行过多的 «_shift_» 操作，锁可能会永久锁定。他们请你找出一种方法，使用不超过 #cf_span[6100] 次操作，使屏幕显示字符串 #cf_span[t]。\n\n第一行包含一个整数 #cf_span[n]，表示字符串 #cf_span[s] 和 #cf_span[t] 的长度（#cf_span[1 ≤ n ≤ 2 000]）。\n\n接下来是两个字符串 #cf_span[s] 和 #cf_span[t]，每个均由 #cf_span[n] 个小写拉丁字母组成。\n\n如果无法在不超过 6100 次 «_shift_» 操作的情况下从字符串 #cf_span[s] 得到字符串 #cf_span[t]，请输出单个数字 #cf_span[ - 1]。\n\n否则，在第一行输出操作次数 #cf_span[k]（#cf_span[0 ≤ k ≤ 6100]）。在下一行输出 #cf_span[k] 个数字 #cf_span[xi]，对应按顺序应应用的 «_shift_ #cf_span[xi]» 操作（#cf_span[0 ≤ xi ≤ n]）。\n\n在第一个示例中，应用操作后，屏幕上的字符串将按如下方式变化：\n\n## Input\n\n第一行包含一个整数 #cf_span[n]，表示字符串 #cf_span[s] 和 #cf_span[t] 的长度（#cf_span[1 ≤ n ≤ 2 000]）。接下来是两个字符串 #cf_span[s] 和 #cf_span[t]，每个均由 #cf_span[n] 个小写拉丁字母组成。\n\n## Output\n\n如果无法在不超过 6100 次 «_shift_» 操作的情况下从字符串 #cf_span[s] 得到字符串 #cf_span[t]，请输出单个数字 #cf_span[ - 1]。否则，在第一行输出操作次数 #cf_span[k]（#cf_span[0 ≤ k ≤ 6100]）。在下一行输出 #cf_span[k] 个数字 #cf_span[xi]，对应按顺序应应用的 «_shift_ #cf_span[xi]» 操作（#cf_span[0 ≤ xi ≤ n]）。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**\n\nLet $\\Sigma$ be the set of lowercase Latin letters.\nLet $\\mathcal{S}_n$ be the set of strings over $\\Sigma$ of length $n$.\nFor a string $w \\in \\mathcal{S}_k$, let $w^R$ denote the reversal of $w$.\nLet concatenation of strings be denoted by juxtaposition.\n\nDefine the transformation function $f: \\mathcal{S}_n \\times \\{0, \\dots, n\\} \\to \\mathcal{S}_n$. For a string $p \\in \\mathcal{S}_n$ and an integer $x$, let $p = \\alpha\\beta$ where:\n*   $\\alpha$ is the prefix of $p$ of length $n-x$.\n*   $\\beta$ is the suffix of $p$ of length $x$.\n\nThe operation is defined as:\n$$f(p, x) = \\beta^R \\alpha$$\n\n**Given**\n\n*   An integer $n$ such that $1 \\le n \\le 2000$.\n*   An initial string $s \\in \\mathcal{S}_n$.\n*   A target string $t \\in \\mathcal{S}_n$.\n\n**Objective**\n\nDetermine if there exists a sequence of integers $X = (x_1, x_2, \\dots, x_k)$ satisfying the following conditions:\n\n1.  $0 \\le k \\le 6100$.\n2.  $0 \\le x_i \\le n$ for all $1 \\le i \\le k$.\n3.  Let the sequence of strings $(s_0, s_1, \\dots, s_k)$ be defined recursively:\n    *   $s_0 = s$\n    *   $s_i = f(s_{i-1}, x_i)$ for $1 \\le i \\le k$\n4.  $s_k = t$.\n\n**Output**\n\n*   If such a sequence $X$ exists, output $k$ followed by the terms $x_1, x_2, \\dots, x_k$.\n*   Otherwise, output $-1$.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF937E","tags":["constructive algorithms","strings"],"sample_group":[["6\nabacbb\nbabcba","4\n6 3 2 3"],["3\naba\nbba","\\-1\n\nIn the first example, after applying the operations, the string on the screen will change as follows:\n\n1.  _abacbb_ _bbcaba_\n2.  _bbcaba_ _ababbc_\n3.  _ababbc_ _cbabab_\n4.  _cbabab_ _babcba_"]],"created_at":"2026-03-03 11:00:39"}}