{"problem":{"name":"dp","description":{"content":"For a string $T$ of length $L$ consisting of `d` and `p`, let $f(T)$ be $T$ rotated $180$ degrees. More formally, let $f(T)$ be the string that satisfies the following conditions. *   $f(T)$ is a str","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc148_b"},"statements":[{"statement_type":"Markdown","content":"For a string $T$ of length $L$ consisting of `d` and `p`, let $f(T)$ be $T$ rotated $180$ degrees. More formally, let $f(T)$ be the string that satisfies the following conditions.\n\n*   $f(T)$ is a string of length $L$ consisting of `d` and `p`.\n*   For every integer $i$ such that $1 \\leq i \\leq L$, the $i$\\-th character of $f(T)$ differs from the $(L + 1 - i)$\\-th character of $T$.\n\nFor instance, if $T =$ `ddddd`, $f(T) =$ `ppppp`; if $T =$ `dpdppp`, $f(T)=$ `dddpdp`.\nYou are given a string $S$ of length $N$ consisting of `d` and `p`.  \nYou may perform the following operation **zero or one** time.\n\n*   Choose a pair of integers $(L, R)$ such that $1 \\leq L \\leq R \\leq N$, and let $T$ be the substring formed by the $L$\\-th through $R$\\-th characters of $S$. Then, replace the $L$\\-th through $R$\\-th characters of $S$ with $f(T)$.\n\nFor instance, if $S=$ `dpdpp` and $(L,R)=(2,4)$, we have $T=$ `pdp` and $f(T)=$ `dpd`, so $S$ becomes `ddpdp`.\nPrint the lexicographically smallest string that $S$ can become.\nWhat is lexicographical order?A string $S = S_1S_2\\ldots S_{|S|}$ is said to be **lexicographically smaller** than a string $T = T_1T_2\\ldots T_{|T|}$ if one of the following 1. and 2. holds. Here, $|S|$ and $|T|$ denote the lengths of $S$ and $T$, respectively.\n\n1.  $|S| \\lt |T|$ and $S_1S_2\\ldots S_{|S|} = T_1T_2\\ldots T_{|S|}$.\n2.  There is an integer $1 \\leq i \\leq \\min\\lbrace |S|, |T| \\rbrace$ that satisfies the following two conditions:\n    *   $S_1S_2\\ldots S_{i-1} = T_1T_2\\ldots T_{i-1}$.\n    *   $S_i$ is smaller than $T_i$ in alphabetical order.\n\n## Constraints\n\n*   $1 \\leq N \\leq 5000$\n*   $S$ is a string of length $N$ consisting of `d` and `p`.\n*   $N$ is an integer.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc148_b","tags":[],"sample_group":[["6\ndpdppd","dddpdd\n\nLet $(L, R) = (2, 5)$. Then, we have $T =$ `pdpp` and $f(T) =$ `ddpd`, so $S$ becomes `dddpdd`.  \nThis is the lexicographically smallest string that can be obtained, so print it."],["3\nddd","ddd\n\nIt may be optimal to skip the operation."],["11\nddpdpdppddp","ddddpdpdddp"]],"created_at":"2026-03-03 11:01:14"}}