Right Side Character

AtCoder

IDagc062_a

Time2000ms

Memory256MB

Difficulty—

For a string $T=T_1T_2\dots T_n$ of length $n\ (2\leq n)$ consisting of `A` and `B`, we define a string $f(T)$ of length $n-1$ as follows. * Let $a_1 < a_2 < \dots < a_{m}$ be the indices $i\ (1\leq i \leq n-1)$ such that $T_i={}$`A`, and $b_1 < b_2 < \dots < b_k$ be the indices $i\ (1\leq i \leq n-1)$ such that $T_i={}$`B`. Then, let $f(T)=T_{a_1+1}T_{a_2+1}\dots T_{a_m+1}T_{b_1+1}T_{b_2+1}\dots T_{b_k+1}$. For example, for the string $T={}$`ABBABA`, the indices $i\ (1\leq i \leq 5)$ with $T_i={}$`A` are $i=1,4$, and the indices $i\ (1\leq i \leq 5)$ with $T_i={}$`B` are $i=2,3,5$, so $f(T)$ is $T_{1+1}T_{4+1}T_{2+1}T_{3+1}T_{5+1}={}$`BBBAA`. You are given a string $S$ of length $N$ consisting of `A` and `B`. Find $S$ after replacing $S$ with $f(S)$ $(N-1)$ times. You have $T$ test cases to solve. ## Constraints * $1 \leq T \leq 10^5$ * $2 \leq N \leq 3 \times 10^5$ * $S$ is a string of length $N$ consisting of `A` and `B`. * All numbers in the input are integers. * The sum of $N$ over the test cases in a single input file is at most $3 \times 10^5$. ## Input The input is given from Standard Input in the following format: $T$ $\mathrm{case}_1$ $\vdots$ $\mathrm{case}_T$ Each case is given in the following format: $N$ $S$ [samples]

Samples

Input #1

3
2
AB
3
AAA
4
ABAB

Output #1

B
A
A

In the first test case, $S$ changes as `AB`${}\rightarrow {}$`B`.
In the second test case, $S$ changes as `AAA`${} \rightarrow {}$`AA`${} \rightarrow {}$`A`.
In the third test case, $S$ changes as `ABAB`${}\rightarrow {}$`BBA`${} \rightarrow {}$`BA`${} \rightarrow {}$`A`.

API Response (JSON)

{
  "problem": {
    "name": "Right Side Character",
    "description": {
      "content": "For a string $T=T_1T_2\\dots T_n$ of length $n\\ (2\\leq n)$ consisting of `A` and `B`, we define a string $f(T)$ of length $n-1$ as follows. *   Let $a_1 < a_2 < \\dots < a_{m}$ be the indices $i\\ (1\\le",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc062_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For a string $T=T_1T_2\\dots T_n$ of length $n\\ (2\\leq n)$ consisting of `A` and `B`, we define a string $f(T)$ of length $n-1$ as follows.\n\n*   Let $a_1 < a_2 < \\dots < a_{m}$ be the indices $i\\ (1\\le...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments