{"problem":{"name":"ST and TS  Palindrome","description":{"content":"You are given a string $S$ of length $N$ consisting of lowercase English letters, and a positive integer $K$. Determine whether there is a string $S'$ of length $K$ that satisfies the following condit","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc155_a"},"statements":[{"statement_type":"Markdown","content":"You are given a string $S$ of length $N$ consisting of lowercase English letters, and a positive integer $K$.\nDetermine whether there is a string $S'$ of length $K$ that satisfies the following conditions.\n\n*   The concatenation of $S$ and $S'$ in this order is a palindrome.\n*   The concatenation of $S'$ and $S$ in this order is a palindrome.\n\nYou have $T$ test cases to solve.\n\n## Constraints\n\n*   $1 \\leq T \\leq 10^5$\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq K \\leq 10^{18}$\n*   $S$ is a string of length $N$ consisting of lowercase English letters.\n*   All numbers in the input are integers.\n*   In each input file, the sum of $N$ over the test cases is at most $2 \\times 10^5$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is in the following format:\n\n$N$ $K$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc155_a","tags":[],"sample_group":[["2\n6 2\nabbaab\n5 3\nabcbb","Yes\nNo\n\nFor the first test case, if we let $S' = {}$`ba`, for instance, the concatenation of $S$ and $S'$ in this order will be `abbaabba`, which is a palindrome. Here, the concatenation of $S'$ and $S$ in this order is `baabbaab`, which is also a palindrome. Thus, $S' = {}$`ba` satisfies the condition, so the answer is `Yes`.\nFor the second test case, we can prove that no string satisfies the conditions."],["3\n12 400378271514996652\nnjvhhvjnnjvh\n10 884633988115575508\nrrhiyvrrur\n36 71630165869626180\nvsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh","Yes\nNo\nYes"]],"created_at":"2026-03-03 11:01:13"}}