C - AB vs. BA Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1500 点

問題文

A と B からなる長さ N の文字列 S が与えられます。 Abel と Bart は、S を用いてゲームをします。 Abel を先手として交互に、次の操作を行います。

  • Abel は、S の部分文字列 AB を 1 つ選び、削除する。
  • Bart は、S の部分文字列 BA を 1 つ選び、削除する。

自分の手番で操作を行えない人が負けとなり、もう一方の人が勝ちとなります。 両者が最適に行動したとき、勝者を求めてください。

1 つの入力につき、T ケースを解いてください。

制約

  • 1 \le T \le 2 \times 10^5
  • 1 \le N \le 2 \times 10^5
  • S は A と B からなる長さ N の文字列
  • T ケースにわたる N の総和は 2 \times 10^5 以下
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N
S

出力

T 行出力せよ。i 行目には、i 番目のテストケースについて、 Abel が勝つならば Abel を、そうでなければ Bart を出力せよ。

入力例 1

2
5
ABAAB
5
AABBA

出力例 1

Abel
Bart

1 番目のテストケースでは、Abel が左側の AB を削除すると S= AAB となり、 Bart は操作を行えないため、Abel が勝ちます。

2 番目のテストケースでは、Abel が AB を削除すると S= ABA となります。 続いて Bart が BA を削除すると S= A となり、Abel は操作を行えないため、Bart が勝ちます。

入力例 2

3
7
BAABAAA
13
AABBAAAABABBA
20
ABAABABABBAAABBABABA

出力例 2

Bart
Abel
Abel

Score : 1500 points

Problem Statement

You are given a string S of length N consisting of A and B. Abel and Bart play a game using S. Starting with Abel, they take turns performing the following operation.

  • Abel chooses one substring AB of S and deletes it.
  • Bart chooses one substring BA of S and deletes it.

The person who cannot perform the operation on their turn loses, and the other person wins. Find the winner when both players act optimally.

Solve T test cases for each input.

Constraints

  • 1 \le T \le 2 \times 10^5
  • 1 \le N \le 2 \times 10^5
  • S is a string of length N consisting of A and B.
  • The sum of N over the T test cases is at most 2 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
S

Output

Output T lines. The i-th line should contain Abel if Abel wins the i-th test case, and Bart otherwise.

Sample Input 1

2
5
ABAAB
5
AABBA

Sample Output 1

Abel
Bart

In the first test case, if Abel deletes the left AB, then S= AAB, and Bart cannot perform the operation, so Abel wins.

In the second test case, if Abel deletes AB, then S= ABA. Next, if Bart deletes BA, then S= A, and Abel cannot perform the operation, so Bart wins.

Sample Input 2

3
7
BAABAAA
13
AABBAAAABABBA
20
ABAABABABBAAABBABABA

Sample Output 2

Bart
Abel
Abel