单点时限: 6.0 sec
内存限制: 1024 MB
在一个一维的世界里，有 $m$ 座城池。相邻的城池（也就是 $i$ 和 $i+1$ 座城市）如果属于同一个国家，他们就连成一个城邦。于是这 $m$ 座城池连成了 $n$ 个城邦。在发生战争时，城邦的大小是决定成败的最关键因素。
唐纳德先生与你各坐拥这个世界的一部分城池，你们经历了数千年的战争在形成了现在的局面。很不幸的是，从现在开始，你们的命运就不在自己手中了。有一个观察者，早就厌烦了这个世界里大大小小的持续了几千年的战争，他决定启用高维力量，一劳永逸地解决战乱。
于是他制定了以下规则：对于观察者来说，每一秒，唐纳德先生手下的城邦会同时在他们的右边界上发起进攻；你手下的城邦会在左边界上发起进攻。这就会产生战争。战争的成败取决于城邦的所占的城池多少，城邦大者赢；如果一样大，唐纳德先生会赢。（是的，这很不公平。）赢的一方可以在边界线上进一步，也就是说吃掉对方的一个城池。如果这是对方的城邦的最后一个城池，那么这个城邦就会消失，可能会有城邦与城邦会连成新的城邦。从而，在若干秒后，整个世界的格局就再也不会改变了。也就再也不会有战争。
听起来很完美？现在我想提前知道结果：要多少秒后格局才会定下来？到那时，唐纳德和你所拥有的城池数量各是多少？
第一行一个整数 $t$ ($1 \le t \le 10^5$)，表示有 $t$ 组测试数据。
对于每组数据，第一行是一个正整数 $n$ ($1 \le n \le 10^6$)，和一个字符 C 或 D，分别表示目前有多少个城邦，以及最左边的城邦是属于你 (C) 还是唐纳德先生 (D)。
第二行有 $n$ 个正整数用空格隔开 $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^{12}$, $a_1+a_2+\cdots+a_n = m$)，表示从左往右的城邦大小。如果最左边的城邦是 C，那么 $a_1$ 对应 C，$a_2$ 对应 D，$a_3$ 对应 C，以此类推；如果最左边的城邦是 D，那么 $a_1$ 对应 D，以此类推。
保证所有测试数据的 $n$ 之和不超过 $10^6$。
对于每组测试数据，输出一行三个整数，分别为：所需的时间，唐纳德先生的城池数量，你的城池数量。
5 2 D 2 3 2 D 3 3 2 C 4 3 4 D 2 1 2 3 1 D 9
2 0 5 3 6 0 0 3 4 5 8 0 0 9 0
样例分别为：DDCCC，DDDCCC，CCCCDDD，DDCDDCCC，DDDDDDDDD。
以第四个样例为例，其收敛经历了下述过程：DDCDDCCC — DDDDCCCC — DDDDDCCC — DDDDDDCC — DDDDDDDC — DDDDDDDD。