#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	string s;
	cin >> s;
	int a = 0, b = 0;
	for (char c : s) {
		if (c == 'A') {a++;}
		else {b++;}
	}	
	cout << (a > b ? 'A' : 'B') << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

 #include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
 
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    vector<string> g;
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        g.push_back(s);
    }
    bool triangle = false;
    for(int i = 0; i < n; i++)
    {
        int cnt = 0;
        for(int j = 0; j < n; j++)
        {
            if(g[i][j] == '1')
            {
                cnt++;
            }
        }
        if(cnt == 1)
        {
            triangle = true;
        }
        else if(cnt > 1)
        {
            break;
        }
    }
    reverse(g.begin(), g.end());
    for(int i = 0; i < n; i++)
    {
        int cnt = 0;
        for(int j = 0; j < n; j++)
        {
            if(g[i][j] == '1')
            {
                cnt++;
            }
        }
        if(cnt == 1)
        {
            triangle = true;
        }
        else if(cnt > 1)
        {
            break;
        }
    }
    if(triangle)
    {
        cout << "TRIANGLE" << endl;
    }
    else
    {
        cout << "SQUARE" << endl;
    }
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}
 
 
 

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
int res[MAX];
 
int S(int x) {
	int res = 0;
	while (x) {
		res += (x % 10);
		x /= 10;
	}
	return res;
}
 
void solve() {
	int x;
	cin >> x;
	cout << res[x] << '\n';
}
 
int main() {
	res[0] = 0;
	for (int i = 1; i < MAX; i++) {
		res[i] = res[i - 1] + S(i);
	}
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include "bits/stdc++.h"
using namespace std;
 
void solve() {
    int n; cin >> n;
    map<int, int> cnt;
    int ans = 0;
    for(int i = 0, x; i < n; ++i) {
        cin >> x;
        if(!cnt[x]) ++ans, ++cnt[((1 << 31) - 1) ^ x];
        else --cnt[x];
    }
    cout << ans << "\n";
}   
 
main() {
    int t = 1; cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	int n, k;
	cin >> n >> k;
	vector<int> v;
	while (n) {
		v.push_back((n + 1) / 2);
		n /= 2;
	}
	int tot = 0, pow2 = 1;
	for (int x : v) {
		if (tot < k && k <= tot + x) {
			cout << pow2 * (2 * (k - tot) - 1) << '\n';
			return;
		}
		tot += x;
		pow2 *= 2;
	}
}
 
int main() {
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
vector<pair<int, int>> odd, even;
 
bool valid(int gc[7][7], bool odd) {
	for (int r = 1; r < 6; r++) {
		for (int c = 1; c < 6; c++) {
			if (gc[r][c] && ((r + c) % 2 == odd)) {
				if (gc[r - 1][c - 1] && gc[r - 1][c + 1] && gc[r + 1][c - 1] && gc[r + 1][c + 1]) {
					return false;
				}
			}
		}
	}
	return true;
}
 
bool check(int g[7][7], int flips_left, int idx, vector<pair<int, int>>& vec, int valid_val) {
    if (flips_left == 0) {
        return valid(g, valid_val);
    }
    if (idx == vec.size()) {
        return false;
    }
    bool ok = false;
    ok |= check(g, flips_left, idx + 1, vec, valid_val);
    g[vec[idx].first][vec[idx].second] ^= 1;
    ok |= check(g, flips_left - 1, idx + 1, vec, valid_val);
    g[vec[idx].first][vec[idx].second] ^= 1;
    return ok;
}
 
void solve() {
    int g[7][7];
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            char c;
            cin >> c;
            g[i][j] = (c == 'B');
        }
    }   
    int res = 0;
    for (int i = 0; i <= 4; i++) {
        if (check(g, i, 0, odd, 1)) {res += i; break;}
    }
    for (int i = 0; i <= 4; i++) {
        if (check(g, i, 0, even, 0)) {res += i; break;}
    }
    cout << res << '\n';
}
int main() {
	
	for (int i = 0; i < 7; i++) {
		for (int j = 0; j < 7; j++) {
			if ((i + j) % 2) {
				odd.emplace_back(i, j);
			}
			else {
				even.emplace_back(i, j);
			}
		}
	}
	
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
}

 #include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
 
int n;
const int N = 1e5 + 69;
int dp[N][3];
string s; 
vector <int> adj[N];
 
void dfs(int u){
    // dp[u][0] = nothing open 
    // dp[u][1] = P open 
    // dp[u][2] = S open 
    
    dp[u][0] = INF;
    if (s[u] != 'S') dp[u][1] = 0;
    else dp[u][1] = INF;
    if (s[u] != 'P') dp[u][2] = 0;
    else dp[u][2] = INF;
    int tot = 0;
    
    for (int v : adj[u]){
        dfs(v);
        dp[u][1] = dp[u][1] + min({dp[v][1], dp[v][2] + 1, dp[v][0]});
        dp[u][2] = dp[u][2] + min({dp[v][2], dp[v][1] + 1, dp[v][0]});
        tot += dp[v][0];
    }
    
    if (s[u] != 'C') tot = INF;
    
    dp[u][0] = min({tot, dp[u][1] + 1, dp[u][2] + 1});
    
    //cout << u << " " << dp[u][0] << " " << dp[u][1] << " " << dp[u][2] << "\n";
}
 
void Solve() 
{
    cin >> n;
    for (int i = 1; i <= n; i++) adj[i].clear();
    for (int i = 2; i <= n; i++){
        int x; cin >> x;
        adj[x].push_back(i);
    }
    
    cin >> s; s = "0" + s;
    
    dfs(1);
    
    cout << min({dp[1][0], dp[1][1], dp[1][2]}) << "\n";
}
 
int32_t main() 
{
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
string alph = "abc";
 
void solve() {
	string s;
	cin >> s;
	int cnt = 0;
	for (int i = 0; i < 3; i++) {
		cnt += (s[i] != alph[i]);
	}
	cout << (cnt <= 2 ? "YES\n" : "NO\n");
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    int ans = 1;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    a[0]++;
    for(int i = 0; i < n; i++)
    {
        ans*=a[i];
    }
    cout << ans << endl;
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}
 
 

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
int score[10][10] = {
	{1,1,1,1,1,1,1,1,1,1},
	{1,2,2,2,2,2,2,2,2,1},
	{1,2,3,3,3,3,3,3,2,1},
	{1,2,3,4,4,4,4,3,2,1},
	{1,2,3,4,5,5,4,3,2,1},
	{1,2,3,4,5,5,4,3,2,1},
	{1,2,3,4,4,4,4,3,2,1},
	{1,2,3,3,3,3,3,3,2,1},
	{1,2,2,2,2,2,2,2,2,1},
	{1,1,1,1,1,1,1,1,1,1}
};
 
void solve() {
	int ans = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			char c;
			cin >> c;
			if (c == 'X') {ans += score[i][j];}
		}
	}
	cout << ans << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	int res = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'B') {
			res++; i += k - 1;
		}
	}
	cout << res << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	int n;
	long long x;
	cin >> n >> x;
	long long a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	long long lo = 0, hi = 2'000'000'007;
	while (lo < hi) {
		long long mid = lo + (hi - lo + 1) / 2;
		long long tot = 0;
		for (int i = 0; i < n; i++) {
			tot += max(mid - a[i], 0LL);
		}
		if (tot <= x) {lo = mid;} 
		else {hi = mid - 1;}
	}
	cout << lo << endl;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
using namespace std;
 
const int N = 200'000;
 
int n, k;
int a[N+5], h[N+5], pref[N+5], length[N+5];
 
bool get(int dist)
{
    bool found = false;
    for(int i = 0; i < n-dist+1; i++)
    {
        if(length[i] < dist){continue;}
        int sum = pref[i+dist]-pref[i];
        if(sum <= k)
        {
            found = true;
            break;
        }
    }
    return found;
}
 
void solve()
{
    pref[0] = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        pref[i+1] = pref[i]+a[i];
    }
    for(int i = 0; i < n; i++)
    {
        cin >> h[i];
    }
    length[n-1] = 1;
    for(int i = n-2; i >= 0; i--)
    {
        if(h[i]%h[i+1] == 0)
        {
            length[i] = length[i+1]+1;
        }
        else
        {
            length[i] = 1;
        }
    }
    int l = 1, r = N;
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(get(mid))
        {
            l = mid+1;
        }
        else
        {
            r = mid-1;
        }
    }
    cout << r << endl;
}
 
int main() {
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	string s;
	cin >> s;
	int n = s.length(), cnt = 0;
	bool all = (s[0] == 'B' || s[n - 1] == 'B');
	for (int i = 0; i < n - 1; i++) {
		if (s[i] == s[i + 1] && s[i] == 'B') {all = true;}
	}
	vector<int> lens;
	int curr = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'A') {curr++;}
		else {
			if (curr != 0) {lens.push_back(curr);}
			curr = 0;
		}
	}
	if (curr != 0) {lens.push_back(curr);}
	sort(lens.begin(), lens.end());
	
	if (lens.empty()) {cout << 0 << '\n'; return;}
	
	int tot = 0;
	if (all) {tot += lens[0];}
	for (int i = 1; i < lens.size(); i++) {
		tot += lens[i];
	}
	cout << tot << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200005;
 
vector<int> adj[N];
vector<bool> vis(N);
 
int entry_node = -1;
vector<int> path;
 
bool dfs1(int u, int p)
{
    vis[u] = true;
    for(auto v : adj[u])
    {
        if(v != p && vis[v])
        {
            entry_node = v;
            return true;
        }
        else if(v != p && !vis[v])
        {
            if(dfs1(v, u))
            {
                return true;
            }
        }
    }
    return false;
}
 
int dfs2(int u)
{
    vis[u] = true;
    int distbruh = N;
    for(auto v : adj[u])
    {
        if(v == entry_node)
        {
            return 1;
        }
        if(!vis[v])
        {
            int dist = dfs2(v)+1;
            distbruh = min(dist, distbruh);
        }
    }
    return distbruh;
}
 
void solve()
{
    int n, a, b;
    cin >> n >> a >> b;
    for(int i = 0; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(b, -1);
    vis.assign(n+1, false);
    int distMarcel = N, distValeriu = 0;
    if(entry_node == a)
    {
        distMarcel = 0;
    }
    else
    {
        distMarcel = dfs2(a);
    }
    vis.assign(n+1, false);
    if(entry_node == b)
    {
        distValeriu = 0;
    }
    else
    {
        distValeriu = dfs2(b);
    }
    if(distValeriu < distMarcel)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    for(int i = 1; i <= n; i++)
    {
        adj[i].clear();
        vis[i] = false;
    }
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}
 

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int a, b, c;
    cin >> a >> b >> c;
    cout << (a+b+c-min({a,b,c}) >= 10 ? "YES\n" : "NO\n");
    
}
 
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
}
 

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int n;
	cin >> n;
	int winner = -1, best_score = 0;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		if (b > best_score && a <= 10) {winner = i; best_score = b;}
	}
	cout << winner << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	for (int r = 0; r < 8; r++) {
		for (int c = 0; c < 8; c++) {
			char x;
			cin >> x;
			if (x != '.') {cout << x;}
		}
	}	
	cout << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
void solve() {
    int n, k; cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];    
    sort(all(a));
    int cnt = 1, ans = 1;
    for(int i = 1; i < n; ++i) {
        if(a[i] - a[i - 1] > k) {
            cnt = 1;
        } else {
            ++cnt;
        }
        ans = max(ans, cnt);
    }
    cout << n - ans << '\n';
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
#define int long long
 
void solve() {
    int n, c; cin >> n >> c;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    int l = 1, r = 1e9;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        int sumall = 0;
        for(int i = 0; i < n; ++i) {
            sumall += (a[i] + 2 * mid) * (a[i] + 2 * mid);
            if(sumall > c) break;
        }
        if(sumall == c) {
            cout << mid << "\n";
            return;
        }
        if(sumall > c) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
void solve() {
    int n; cin >> n;
    vector<ll> cnt(n + 1, 0), mx(n + 1, 0);
    for(int i = 0; i < n; ++i) {
        int x; cin >> x;
        if(x <= n) ++cnt[x];
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = i; j <= n; j += i) mx[j] += cnt[i];
    }
    cout << *max_element(all(mx)) << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define int long long
 
void solve()
{
    int n;
    cin >> n;
    map<int, int> up, side, diag1, diag2;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        up[x]++;
        side[y]++;
        diag1[x-y]++;
        diag2[x+y]++;
    }
    for(auto x : up)
    {
        ans+=x.second*(x.second-1);
    }
    for(auto x : side)
    {
        ans+=x.second*(x.second-1);
    }
    for(auto x : diag1)
    {
        ans+=x.second*(x.second-1);
    }for(auto x : diag2)
    {
        ans+=x.second*(x.second-1);
    }
    cout << ans << endl;
}
 
int32_t main(){
    startt
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}
 
 
 

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
#define int long long
const int N = 2e5 + 5;
vector<pair<int, int>> adj[N];
int val[N], vis[N];
void dfs(int u) {
    vis[u] = 1;
    for(auto x: adj[u]) {
        int v = x.first, w = x.second;
        if(!vis[v]) {
            val[v] = val[u] + w;
            dfs(v);
        }
    }
}
void solve() {
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        adj[i].clear();
        vis[i] = 0, val[i] = 0;
    }
    vector<array<int, 3>> c;
    for(int i = 1; i <= m; ++i) {
        int a, b, d; cin >> a >> b >> d;
        adj[a].pb({b, d});
        adj[b].pb({a, -d}); 
        c.pb({a, b, d});  
    }
    for(int i = 1; i <= n; ++i) {
        if(!vis[i]) dfs(i);
    }
    for(int i = 1; i <= m; ++i) {
        int a = c[i - 1][0], b = c[i - 1][1], d = c[i - 1][2];
        if(val[a] + d != val[b]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a + b == c) {cout << "+\n";}
	else {cout << "-\n";}	
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    int x, odd = 0, even = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> x;
        if(x%2 == 0)
        {
            even+=x;
        }
        else
        {
            odd+=x;
        }
    }
    if(even > odd)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}
 
 

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	int mp[26];
	for (int i = 0; i < 26; i++) {
		mp[i] = -1;
	}
	for (int i = 0; i < n; i++) {
		int curr = (s[i] - 'a');
		if (mp[curr] == -1) {
			mp[curr] = (i % 2);
		}
		else {
			if (mp[curr] != (i % 2)) {cout << "NO\n"; return;}
		}
	}
	cout << "YES\n";
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

#include <iostream>
 
using namespace std;
long long n,a[200005],q,sum=0,pref[200005],t;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--)
    {
        sum = 0;
        cin >> n >> q;
        for(int i=1;i<=n;i++){
            cin >> a[i];
            sum+=a[i];
            pref[i]=pref[i-1];
            pref[i]+=a[i];
        }
        for(int i = 0; i < q; i++){
            long long l,r,k;
            cin >> l >> r >> k;
            long long ans = pref[n]-(pref[r]-pref[l-1])+k*(r-l+1);
            if(ans%2==1){
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
    }
}
 

#include <bits/stdc++.h>
using ll=long long;
using ld=long double;
int const INF=1000000005;
ll const LINF=1000000000000000005;
ll const mod=1000000007;
ld const PI=3.14159265359;
ll const MAX_N=3e5+5;
ld const EPS=0.00000001;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define sz(a) (int)a.size()
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll t,n,a[2000005],pref[2000005];
int32_t main(){
//CODE_START;
#ifdef LOCAL
//ifstream cin("input.txt");
#endif
cin>>t;
while(t--){
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
        pref[i]=pref[i-1]+a[i];
    }
    ll l=1,r=n,ans=0;
    while(l<=r){
            ll mid=(l+r)/2;
        cout<<"? "<<(mid-l+1)<<' ';
        for(ll i=l;i<=mid;i++)
        {
            cout<<i<<' ';
        }
        cout<<endl<<flush;
        ll x=0;
        cin>>x;
        if(x==pref[mid]-pref[l-1]){
            l=mid+1;
        }else {
            r=mid-1;
            ans=mid;
        }
    }
    cout<<"! "<<ans<<endl<<flush;
}
}

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int n, m, x1, y1, x2, y2;
    string d_string;
    cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    x1--;x2--;y1--;y2--;
    cin >> d_string;
    int d = (d_string[0] == 'U' ? 1+(d_string[1] == 'R' ? 2 : 0) : 0+(d_string[1] == 'R' ? 2 : 0));
    bool vis[n][m][4];
    memset(vis, false, sizeof(vis));
    int i = x1, j = y1;
    int bounces = 0;
    while(!vis[i][j][d])
    {
        if(i == x2 && j == y2){cout << bounces << endl; return;}
        int na = 0;
        if(d%2 == 1 && i == 0){d-=1;na++;}
        if(d%2 == 0 && i == n-1){d+=1;na++;}
        if(d >= 2 && j == m-1){d-=2;na++;}
        if(d < 2 && j == 0){d+=2;na++;}
        bounces+=min(1, na);
        if(vis[i][j][d])
        {
            break;
        }
        vis[i][j][d] = true;
        if(d%2 == 1){i--;}else{i++;}
        if(d >= 2){j++;}else{j--;}
    }
    cout << -1 << endl;
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(all(a));
    if(a[0] != 1) {
        cout << "NO\n";
        return;
    }
    vector<int> dp(5005, 0);
    dp[1] = 1;
    for(int i = 1; i < n; ++i) {
        if(!dp[a[i]]) {
            cout << "NO\n";
            return;
        }
        for(int j = 5000; j >= a[i]; --j) {
            dp[j] |= dp[j - a[i]];
        }
    }
    cout << "YES\n";
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(all(a));
    if(a[0] != 1) {
        cout << "NO\n";
        return;
    }
    long long sum = a[0];
    for(int i = 1; i < n; ++i) {
        if(sum < a[i]) {
            cout << "NO\n";
            return;
        }
        sum += a[i];
    }
    cout << "YES\n";
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

To make the arithmetic mean be equal to exactly $$$1$$$ the sum needs to be equal to the number of elements in the array.

Let's consider $$$3$$$ cases for this problem:

1) The sum of the array equals $$$n$$$: Here the answer is $$$0$$$ since the arithmetic mean of the array is initially $$$1$$$.

2) The sum of the array is smaller than $$$n$$$: The answer is always $$$1$$$ since we can add a single integer $$$k$$$ such that $$$sum + k = n + 1$$$ is satisfied and more specifically $$$k = n - sum + 1$$$.

3) The sum of the array is greater than $$$n$$$: If we add any number apart from $$$0$$$ will add to the sum more or equal than to the number of elements. The number of $$$0$$$'s to add can be found by a loop of adding $$$0$$$'s until the number of elements is equal to the sum or by the simple formula of $$$sum-n$$$.

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

 int main()
 {
	 int t;
	 cin >> t;
	 while(t--){
		 int n;
		 cin >> n;
		 int sum = 0;
		 for (int i = 0;i < n; i++){
			 int a;
			 cin >> a;
			 sum += a;
		 }
   if(sum < n)cout << "1\n";
   else cout << sum - n << "\n";
	 }
 }

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

int main()
{
    int t;
    cin >> t;
    while(t--){
        int n, m, i, j;
        cin >> n >> m >> i >> j;

        cout << 1 << " " << 1 << " " << n << " " << m << "\n";
    }
}

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

int main()
{
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> h(n);

        for (int i = 0;i < n; i++){
            cin >> h[i];
        }
        sort(h.begin(), h.end());

        if(n == 2){
            cout << h[0] << " " << h[1] << "\n";
            continue;
        }

        int pos = -1, mn = INT_MAX;

        for (int i = 1;i < n; i++){
            if(mn > abs(h[i] - h[i - 1])){
                pos = i;
                mn = abs(h[i] - h[i - 1]);
            }
        }
        
        for (int i = pos;i < n; i++){
            cout << h[i] << " ";
        }
        for(int i = 0;i < pos; i++){
            cout << h[i] << " ";
        }

        cout << "\n";

    }
}

#include "bits/stdc++.h"
using namespace std;
 
int main()
{
    int t;
    cin >> t;
 
    while(t--){
        
        int n;
        cin >> n;
        if(n % 2 == 1){
            cout << "Bob\n";
            continue;
        }
        int cnt = 0;
        while(n % 2 == 0){
            cnt++;
            n /= 2;
        }
 
        if(n > 1){
            cout << "Alice\n";
        }else if(cnt % 2 == 0){
            cout << "Alice\n";
        }else cout << "Bob\n";
    }
}

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

string get(string s, int k){
    while((int)s.size() < k){
        s = s + s;
    }
    while((int)s.size() > k)
        s.pop_back();
    return s;
}
int main()
{
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;

    string pref = "";
    pref += s[0];

    string mn = get(pref, k);

    for(int i = 1;i < n;i++){
        if(s[i] > s[0])break;
        pref += s[i];
        mn = min(mn, get(pref, k));
    }
    cout << mn << "\n";
}

We know that the final string is some prefix repeated a bunch of times. Incrementally for $$$i$$$ from $$$1$$$ to $$$n$$$ we will keep the longest among the first $$$i$$$ prefixes that gives the best answer we've seen so far.

So assume the $$$m-th$$$ prefix is currently the best and we're considering position $$$p$$$. If the $$$p-th$$$ character is greater than the corresponding character in $$$s_{1..m} \cdot (a lot)$$$ then the $$$p-th$$$ prefix and any further prefixes can't possibly give a smaller answer, so we just print the current one and finish. Otherwise all the characters before the $$$p-th$$$ are all less than or equal to the corresponding characters in $$$s_1..m \cdot (a lot)$$$, so if the $$$p-th$$$ is smaller than the corresponding we set the $$$p-th$$$ prefix as the best.

Now the interesting case is if the current character is the same as the corresponding one. Say then that $$$p = m + t$$$, by the logic of the previous paragraph we must have $$$s_{(m + 1)..(m + t)} = s_{1..t}$$$. If $$$t = m$$$ then the new prefix is just the old one twice, so set $$$p$$$ as the best prefix now. This ensures that otherwise $$$t < m$$$.

Denote $$$A = s_{1..t}$$$ and $$$B = s_{(t + 1)..m}$$$, so the string formed by the current best prefix is $$$ABABABABA...$$$ and the new one is $$$ABAABAABA...$$$ Now if $$$AB = BA$$$ then these strings are in fact the same, so set $$$m + t$$$ as the new best prefix. Otherwise we can find the first position where $$$AB$$$ and $$$BA$$$ differ, and use that to determine whether the new prefix is better. This can be done in $$$O(1)$$$ with Z function, thus giving a linear solution for the full problem.

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

string s;
int n, k;

vector<int> z_func(string &s) {
    int n = s.size(), L = -1, R = -1;
    vector<int> z(n);
    z[0] = n;
    for(int i = 1; i < n; i++) {
        if(i <= R)
            z[i] = min(z[i - L], R - i + 1);
        while(i + z[i] < n && s[i + z[i]] == s[z[i]])
            z[i]++;
        if(i + z[i] - 1 > R) {
            L = i;
            R = i + z[i] - 1;
        }
    }
    return z;
}

void finish(int m) {
    for(int i = 0; i < k; i++)
        cout << s[i % m];
    cout << '\n';
    exit(0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k >> s;
    auto z = z_func(s);

    int cur = 1;
    for(int i = 1; i < n; i++) {
        if(s[i] > s[i % cur])
            finish(cur);
        if(s[i] < s[i % cur]) {
            cur = i + 1;
            continue;
        }
        int off = i - cur + 1;
        if(off == cur) {
            cur = i + 1;
            continue;
        }
        if(z[off] < cur - off) {
            if(cur + off + z[off] >= k) {
                cur = i + 1;
                continue;
            }
            if(s[off + z[off]] > s[z[off]])
                cur = i + 1;
            continue;
        }
        if(z[cur - off] < off) {
            if(2 * cur + z[cur - off] >= k) {
                cur = i + 1;
                continue;
            }
            if(s[cur - off + z[cur - off]] < s[z[cur - off]])
                cur = i + 1;
            continue;
        }
        cur = i + 1;
    }

    finish(cur);
}

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

 const int N = 2e5 + 10;
 vector<long long> adj[N];
 long long s[N], n, m;
 bool bipartite()
 {
	 bool bip = true;

	 for(long long i = 0;i < n;i++)
		 s[i] = -1;

	 queue<long long> q;

	 for(long long i = 0;i < n;i++){
		 if(s[i] != -1)continue;

		 q.push(i);
		 s[i] = 0;

		 while(!q.empty()){
			 long long v = q.front();
			 q.pop();

			 for(long long u: adj[v]){
				 if(s[u] == -1){
					 s[u] = s[v] ^ 1;
					 q.push(u);
				 }else bip &= s[u] != s[v];
			 }
		 }
	 }
	 return bip;
 }

 int main()
 {
	 ios_base::sync_with_stdio(0);cin.tie(0);
	 long long T;
	 cin >> T;
	 while(T--)
	 {
		 cin >> n >> m;
		 for(long long i = 0;i < n;i++)
			 adj[i].clear();

		 vector<long long> v(n), t(n);
		long long p1 = 0, p2 = 0;
		 for(long long i = 0;i < n; i++){
			 cin >> v[i];
			 p1 = (p1 + abs(v[i])) % 2;
		 }
		 for (long long i = 0;i < n; i++){
			 cin >> t[i];
			 p2 = (p2 + abs(t[i])) % 2;
		 }

		 for(long long i = 0;i < m;i++){
			 long long a, b;
			 cin >> a >> b;
			 --a, --b;
			 adj[a].push_back(b);
			 adj[b].push_back(a);
		 }
		 
		 if(p1 != p2){
		   cout << "NO\n";
		   continue;
		 }

		 if(bipartite() == false){
			 cout << "YES\n";
		 }else{
			 vector<long long> c(2, 0);

			 for(int i = 0;i < n;i++){
				 c[s[i]] += v[i] - t[i];
			 }

			 if(c[0] == c[1]){
				 cout << "YES\n";
			 }else cout << "NO\n";
		 }
	 }

 }

Idea: SlavicG

We find the day that Alin got the maximum amount of money by iterating through the array. If we have no day when the sum is positive, output 0.

Create a variable max, a variable sum and a variable pos. Set $$$max = 0$$$, $$$sum = 0$$$, $$$pos= 0$$$. Iterate through the array and add $$$arr[I]$$$ to $$$sum$$$. If $$$sum > max$$$ then save $$$i$$$ in the variable $$$pos = i$$$, and set max to the current $$$sum$$$. After you are done iterating print $$$pos$$$.

Link to solution: https://ideone.com/wZWJBW

Idea: mesanu

The following greedy solutions always works: Sort the array $$$arr$$$, and then iterate until you find the minimum even number. If at the end of the loop it doesn’t exist then we have no answer and the solution is $$$-1$$$. Because we can not create an even number without any even digits. If there is an even element, save it’s index to a variable.Then print the array decreasing order (from $$$n$$$ to $$$1$$$)without the minimum even digit(the element at the saved index). After printing the array, print the minimum even digit so the number will be even.

Link to solution: https://ideone.com/fyDKc2

Idea: SlavicG

This problem can be solved using dynamic programming.

The idea is for every element we try $$$k$$$ elements before it to see which one will give us the least cost.

Set an array $$$dp[n+1]$$$ and all the elements are equal to $$$10^9$$$ and set $$$dp[1]$$$ = 0; iterate through the array from $$$2$$$ to $$$n$$$ and for each $$$dp[i] = min(dp[i], dp[j]+abs(arr[i]-arr[j]))$$$ where $$$(i-k \leq j < i)$$$ and $$$j$$$ indicates one of the last $$$k$$$ bus stops. After you are done iterating print $$$dp[n+1]$$$.

Link to solution: https://ideone.com/zllXMy

There are $$$2$$$ cases: If $$$k$$$ is even Bob makes the last move and he can always insert a coprime number with the gcd of the array, so after the insertion the $$$gcd$$$ of the array is $$$1$$$.

Idea: mesanu

If $$$k$$$ is odd then Alice makes the last move. Alice wins if we can remove an element from the starting array such that the $$$gcd$$$ of $$$arr$$$ is bigger than 1. To find this out we can use the fundamental theory of arithmetic which states that any integer can be expressed as a product of prime numbers.For each element in the array we find what primes divide it by iterating through all the primes under 100(since it is given that $$$a_i \leq 100$$$). If any prime divides more than $$$n-1$$$ elements Alice wins since if Bob introduces a number Alice can delete that number in the next move. If no prime divides more than $$$n-1$$$ elements then bob wins.

Link to solution: https://ideone.com/nmWCRz

Idea: SlavicG

Another solution for when $$$k$$$ is odd is with prefix and suffix $$$gcd$$$. Iterrate over all $$$a_i$$$ from $$$1$$$ to $$$n$$$ and set $$$prefixgcd[i] = gcd(prefixgcd[i-1],prefixgcd[i])$$$. Then do the same for $$$suffixgcd$$$, but in reverse order: from $$$n$$$ to $$$1$$$ and set every element $$$suffixgcd[i] = gcd(suffixgcd[i+1],suffixgcd[i])$$$. Be careful at $$$prefixgcd_1$$$ and $$$suffixgcd_n$$$, You should just attribute them the value of the element at the index. After that we just iterate over all the array and check if $$$gcd(prefixgcd[i-1], suffixgcd_[i+1]) > 1$$$ ( again, be careful at $$$a_1$$$ and $$$a_n$$$). If this is true for at least one element then the answer is $$$"YES"$$$. But if we can not find such i then the answer is $$$"NO"$$$.

Link to solution: https://ideone.com/R5YyHC

Idea: mesanu

We create an array $$$sum$$$ where $$$sum[i]$$$ is the sum of all the elements in array $$$a$$$ with index smaller than one. Set $$$sum[0]$$$ = 0. We have $$$sum[i] = sum[i-1]+a[i-1]$$$. Now we can use binary search to find the smallest sum bigger than $$$b[i]$$$ then print the index where the smallest sum bigger than $$$b[i]$$$ is.

Link to solution: https://ideone.com/1DCK0b