Description

     文具推销商布卢姆先生在与自己的一场零和游戏中成功赢了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的答案，当然前提是你帮戴达卢斯先生想出了最好的策略。

Format

Input

第一行包括两个数n,m，表示开始有n堆石子，且有m个操作。

     第二行包括n个数，表示开始时第1堆到第n堆各有多少石子。

     以下m行，每行包括一个操作。操作格式已给出。

     所有数据中间均可能包含不期望的空格，请自行判断。

Output

  对于每一个Q操作输出一行，如果戴达卢斯先生能够胜利则输出“D”，否组输出“B”。

.

     对于100%的数据保证，0 <= 任意时刻石子数 <= 10^18,堆数 <= 6 * 10^5,m <= 3 * 10^5。

Samples

input1