题目描述

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

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

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

输入格式

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

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

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

输出格式

输出共m行，每行包含一个字符，对于第i场战争，如果A国获胜则输出'A'，B国获胜输出'B'，C国获胜输出'C'，其他情况则输出'D'。

输入样例 #1

4 5
7 7 7
9 3 2
1 8 2
4 4 1
1 4
1 1
2 2
3 3
4 4

输出样例 #1

D
D
A
B
D

输入样例 #2

6 4
1 6 0
2 5 0
3 4 7
4 3 7
5 2 0
6 1 0
1 6
1 3
5 6
2 5

输出样例 #2

D
B
A
C

输入样例 #3

3 4
5 5 1
2 8 3
9 1 1
1 1
1 2
2 3
1 3

输出样例 #3

D
B
D
D

提示

【说明提示】

对于第一场战争（从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%的数据，cᵢ=0。

对于50%的数据，1≤n,m≤100，1≤aᵢ,bᵢ,cᵢ≤10⁹。

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

对于100%的数据，1≤n,m≤10⁵，1≤l,r≤n，1≤aᵢ,bᵢ,cᵢ≤10¹⁸，aᵢ≠bᵢ，bᵢ≠cᵢ，cᵢ≠aᵢ。