CF 1894A 学习笔记思维题意理解分析

原题

A. Secret Sport

time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Let's consider a game in which two players, A and B, participate. This game is characterized by two positive integers, 𝑋� and 𝑌�.

The game consists of sets, and each set consists of plays. In each play, exactly one of the players, either A or B, wins. A set ends exactly when one of the players reaches 𝑋� wins in the plays of that set. This player is declared the winner of the set. The players play sets until one of them reaches 𝑌� wins in the sets. After that, the game ends, and this player is declared the winner of the entire game.

You have just watched a game but didn't notice who was declared the winner. You remember that during the game, 𝑛� plays were played, and you know which player won each play. However, you do not know the values of 𝑋� and 𝑌�. Based on the available information, determine who won the entire game — A or B. If there is not enough information to determine the winner, you should also report it.

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡� (1≤𝑡≤104)(1≤�≤104) - the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer 𝑛� (1≤𝑛≤20)(1≤�≤20) - the number of plays played during the game.

The second line of each test case contains a string 𝑠� of length 𝑛�, consisting of characters 𝙰A and 𝙱B. If 𝑠𝑖=𝙰��=A, it means that player A won the 𝑖�-th play. If 𝑠𝑖=𝙱��=B, it means that player B won the 𝑖�-th play.

It is guaranteed that the given sequence of plays corresponds to at least one valid game scenario, for some values of 𝑋� and 𝑌�.

Output

For each test case, output:

𝙰A — if player A is guaranteed to be the winner of the game.
𝙱B — if player B is guaranteed to be the winner of the game.
?? — if it is impossible to determine the winner of the game.

Example

input

Copy

ABBAA

BBB

BBAAABA

AAAAAAAABBBAABBBBBAB

AAAABABBABBAB

BBBAAAA

output

Copy

A
B
A
B
A
B
A

Note

In the first test case, the game could have been played with parameters 𝑋=3�=3, 𝑌=1�=1. The game consisted of 11 set, in which player A won, as they won the first 33 plays. In this scenario, player A is the winner. The game could also have been played with parameters 𝑋=1�=1, 𝑌=3�=3. It can be shown that there are no such 𝑋� and 𝑌� values for which player B would be the winner.

In the second test case, player B won all the plays. It can be easily shown that in this case, player B is guaranteed to be the winner of the game.

In the fourth test case, the game could have been played with parameters 𝑋=3�=3, 𝑌=3�=3:

In the first set, 33 plays were played: AAA. Player A is declared the winner of the set.
In the second set, 33 plays were played: AAA. Player A is declared the winner of the set.
In the third set, 55 plays were played: AABBB. Player B is declared the winner of the set.
In the fourth set, 55 plays were played: AABBB. Player B is declared the winner of the set.
In the fifth set, 44 plays were played: BBAB. Player B is declared the winner of the set.

In total, player B was the first player to win 33 sets. They are declared the winner of the game.

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int t;
	scanf("%d",&t);
	
	while(t--)
	{
		int n;
		scanf("%d",&n);
		string s;
		cin>>s;
		printf("%c\n",s[n-1]);
	}
	
	return 0;
}