{"problem":{"name":"Two Abbreviations","description":{"content":"You are given a string $S$ of length $N$ and another string $T$ of length $M$. These strings consist of lowercase English letters. A string $X$ is called a **good string** when the following condition","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc028_a"},"statements":[{"statement_type":"Markdown","content":"You are given a string $S$ of length $N$ and another string $T$ of length $M$. These strings consist of lowercase English letters.\nA string $X$ is called a **good string** when the following conditions are all met:\n\n*   Let $L$ be the length of $X$. $L$ is divisible by both $N$ and $M$.\n*   Concatenating the $1$\\-st, $(\\frac{L}{N}+1)$\\-th, $(2 \\times \\frac{L}{N}+1)$\\-th, $...$, $((N-1)\\times\\frac{L}{N}+1)$\\-th characters of $X$, without changing the order, results in $S$.\n*   Concatenating the $1$\\-st, $(\\frac{L}{M}+1)$\\-th, $(2 \\times \\frac{L}{M}+1)$\\-th, $...$, $((M-1)\\times\\frac{L}{M}+1)$\\-th characters of $X$, without changing the order, results in $T$.\n\nDetermine if there exists a good string. If it exists, find the length of the shortest such string.\n\n## Constraints\n\n*   $1 \\leq N,M \\leq 10^5$\n*   $S$ and $T$ consist of lowercase English letters.\n*   $|S|=N$\n*   $|T|=M$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$S$\n$T$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc028_a","tags":[],"sample_group":[["3 2\nacp\nae","6\n\nFor example, the string `accept` is a good string. There is no good string shorter than this, so the answer is $6$."],["6 3\nabcdef\nabc","\\-1"],["15 9\ndnsusrayukuaiia\ndujrunuma","45"]],"created_at":"2026-03-03 11:01:13"}}