纸牌PK

题目描述

小童和小程每次遇到谁优先的问题，都会采用抽一张纸牌比大小的方式决定，总采用这种方式，难免感到无趣。

小童今天突发奇想，修改了抽纸牌的方式。修改后的方式是这样的：两人轮流在 $n$ 张纸牌中抽取 $m$ 轮，每轮抽取连续一定范围的纸牌，计算 $m$ 轮抽取中所有牌面上的数字总和，最终谁的数字总和大，谁获得优先权。

输入格式

第一行包括两个整数 $n$ 和 $m$。（$1 \le n \le 500000$，$1 \le m \le 100$）

第二行包括 $n$ 个整数，依次表示 $n$ 张纸牌上的数字。（$1 \le$ 整数 $\le 100$）

接下来 $m$ 行，每行两个正整数 $L$ 和 $R$，表示小童每轮抽牌的范围。

接下来 $m$ 行，每行两个正整数 $L$ 和 $R$，表示小程每轮抽牌的范围。（$1 \le L \le R \le n$）

输出格式

输出一个字符，小童数字总和大，输出 T；小程数字总和大，输出 C；总和相等输出 D。

样例输入 #1

7 3
2 10 5 3 6 4 9
3 5
6 7
2 7
2 6
1 2
1 6

样例输出 #1

C

提示

输入样例中 $m=3$，表示两人各自抽 3 轮范围纸牌。

小童第 1 轮：抽取第 3~5 张纸牌，该轮数字和 $5+3+6=14$。

小童第 2 轮：抽取第 6~7 张纸牌，该轮数字和 $4+9=13$。

小童第 3 轮：抽取第 2~7 张纸牌，该轮数字和 $10+5+3+6+4+9=37$。

小童数字总和 $14+13+37=64$。

小程第 1 轮：抽取第 2~6 张纸牌，该轮数字和 $10+5+3+6+4=28$。

小程第 2 轮：抽取第 1~2 张纸牌，该轮数字和 $2+10=12$。

小程第 3 轮：抽取第 1~6 张纸牌，该轮数字和 $2+10+5+3+6+4=30$。

小程数字总和 $28+12+30=70$。

最终小程数字总和大于小童，输出字符 C。

数据范围

$1 \le n \le 500000$，$1 \le m \le 100$，$1 \le L \le R \le n$，纸牌数字为 $1$ 到 $100$ 的整数。

知识点与难度

本题涉及的知识点从属于 GESP 四级（前缀和、区间求和），难度等级：Mid-。

测试点分布