珅泽大陆战争预测

珅泽大陆有三个强大的国家，分别是A国、B国、C国，三国之间互相为交战状态，其中更是有n个兵家必争之地。这n个地点从西向东排成一线，在第i个地点中三个国家分别派遣的兵力为ai、bi和ci。如果在第i个地点，有某个国家的兵力同时大于其他两个国家，它就可以占领该地点。

小珅同学作为杰出的战略家，总能准确地预测出下场战争的交战区域[l,r]，表示下次战场会由西向东从第l个地点覆盖到第r个地点。而第l个地点到第r个地点范围内，占领的地点数量最多的国家，会成为本场战争的战胜国。如果有两个或以上国家占领的地点数量相同，则本场战争的结果为平局。

现在，小珅同学一共会预测m场战争，请你帮他求出每场战争的结果。

输入

输入文件共 n+m+1 行，第一行输入包含两个正整数n和m，表示地点的数量n，以及小珅同学预测的战争数量m。

接下来的n行每行包含三个正整数ai、bi和ci，分别表示第i个地点中三个国家派遣的兵力。

接下来的m行每行包含两个正整数l和r，表示第i场战争的交战区域从第l个地点到第r个地点。

输出

输出文件共 m 行，每行包含一个字符，对于第i场战争，如果A国获胜则输出'A'，B国获胜输出'B'，C国获胜输出'C'，如果有两个或以上国家平局则输出'D'。

样例输入

样例输出

D
B
A
C

提示

【输入输出样例1说明】

对于第一场战争（从1到6），A国占领5、6号地点，B国占领1、2号地点，C国占领3、4号地点，三个国家各自占领两个地点，所以最终结果为平局。

对于第二场战争（从1到3），A国没有占领地点，B国占领1、2号地点，C国占领3号地点，所以最终结果为B获胜。

对于第三场战争（从5到6），A国占领5、6号地点，B国没有占领地点，C国没有占领地点，所以最终结果为A获胜。

对于第四场战争（从2到5），A国占领5号地点，B国占领2号地点，C国占领3、4号地点，所以最终结果为C获胜。

【数据规模与约定】

对于 30% 的数据，ci=0。

对于 50% 的数据，1≤n,m≤100，1≤ai,bi,ci≤109。

对于 70% 的数据，1≤n,m≤1000。

对于100% 的数据，1≤n,m≤105，1≤l,r≤n，1≤ai,bi,ci≤1018，ai !=bi，bi !=ci，ci != ai。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Country {
    long long a;
    long long b;
    long long c;
};

char getWinner(const vector<Country>& countries, int l, int r) {
    int countA = 0, countB = 0, countC = 0;
    for (int i = l - 1; i < r; i++) {
        if (countries[i].a > countries[i].b && countries[i].a > countries[i].c) {
            countA++;
        } else if (countries[i].b > countries[i].a && countries[i].b > countries[i].c) {
            countB++;
        } else if (countries[i].c > countries[i].a && countries[i].c > countries[i].b) {
            countC++;
        }
    }
    if (countA > countB && countA > countC) {
        return 'A';
    } else if (countB > countA && countB > countC) {
        return 'B';
    } else if (countC > countA && countC > countB) {
        return 'C';
    } else {
        return 'D';
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Country> countries(n);
    for (int i = 0; i < n; i++) {
        cin >> countries[i].a >> countries[i].b >> countries[i].c;
    }
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        cout << getWinner(countries, l, r) << endl;
    }
    return 0;
}