题目描述

** **                                     ** ** ** **                                 ** ** ** ** ** **         ** 文具推销商布卢姆先生在与自己的一场零和游戏中成功赢了 100 英磅，从此迷上了各种游戏，以至于到处找人玩游戏；而他今天的对手——史蒂芬 . 戴达卢斯，则期望你能帮助他赢得游戏，事成之后他会用克莱因瓶请你喝酒。** ** ** ** **         ** 游戏的规则很简单。考虑桌面上有许多堆石子，布卢姆与戴达卢斯轮流操作（布卢姆先生很绅士的让戴达卢斯先生先操作）。每人每次可以从一堆石子中取出 2^q(q >= 0) 个石子。谁面对着空空如也的桌面，谁就失败了。** ** ** ** **         ** 然而，布卢姆先生与戴达卢斯先生玩久了同一个局面的游戏后总是会觉得厌倦的，于是便决定偶尔在某局游戏后改变一下游戏的初始局面。再于是便有了如下几种操作：** ** **         Q i j ** 询问只玩第 i 堆石子到第 j 堆石子，在戴达卢斯先生先手的情况下谁会获得胜利。 (0 < i,j <= n_now ) ** ** **         A i j s ** 将第 i 堆到第 j 堆的每堆石子的个数都加上 s 。 (s >= 0,0 < i,j <= n_now) ** ** **         B i j s ** 将第 i 堆到第 j 堆的每堆石子的个数都减去 s 。（ s >= 0, 0<i,j<=n_now 保证不会出现负数）** ** **         C i s ** 将第 i 堆的石子个数变为 s 。 (s >= 0,0<i<=n_now) ** ** **         D i j p ** 将第 i 堆到第 j 堆的每堆石子的个数都乘上 2^(2p) 。 (5 > p > 0,0<i,j<=n_now) ** ** **         E k ** 将前面第 k 个 D 操作的效果抹除，即对于 [Dki,Dkj] 的每堆石子个数都除以 2^(2Dp) 。** ** **         F p ** 在最后一堆石子的右边再增加一堆石子，其石子个数为 p (p > 0) ** ** **         G ** 删掉最后一堆石子。** ** **         ....** ** ** ** ** **         ** 本来布卢姆先生还可以再加上各种操作，但是他还要腾出时间去参加帕迪的葬礼，因此暂时就只用这几种操作了；而且，作为一个犹太人，布卢姆是相当聪明的——你甚至可以认为他绝对聪明，不会犯任何错误。而此时戴达卢斯先生则想让你告诉他每一个 Q 的答案，当然前提是你帮戴达卢斯先生想出了最好的策略。** ** ** ** **      ** **

输入格式

** **   ** 第一行包括两个数 n,m ，表示开始有 n 堆石子，且有 m 个操作。** ** **         ** 第二行包括 n 个数，表示开始时第 1 堆到第 n 堆各有多少石子。** ** **         ** 以下 m 行，每行包括一个操作。操作格式已给出。** ** **         ** 所有数据中间均可能包含不期望的空格，请自行判断。** ** **

输出格式

** **         ** 对于每一个 Q 操作输出一行，如果戴达卢斯先生能够胜利则输出“ D ”，否组输出“ B ”。** ** . ** ** **         ** 对于 100% 的数据保证， 0 <= ** 任意时刻石子数 ** <= 10^18, 堆数 ** <= 6 * 10^5,m <= 3 * 10^5** 。**

提示

没有写明提示

题目来源

没有写明来源