此题为hard version，是困难版本，简单版本在easy version。两个版本只有第二种干预有区别。

“为我等的世界带来变革。于诸神之地施行制裁。”

在某个平行世界，人们，用其双手创造出诸多的故事。由于某个契机，故事里的角色出现在了创造者的世界，即“神”的世界里。于是，关于创造者（Creator）和被创造者（ReCreator）的故事开始了。

军姬阿尔泰尔作为最强大的被创造者，在于与另一个被创造者魔法少女煌树茉美香发生冲突后展开了战斗，军姬发动了能力-森罗万象第二十乐章：因子模仿，创造了茉美香的模仿者，因此，茉美香和自己的模仿者展开了殊死搏斗。

茉美香和对手都有Magical Splash Flare的必杀技，但其威力取决于发动者的体力  和魔力 （都是非负整数值），具体来说，其威力  ，最后威力大者会成功击败对手，并且她们的必杀技会对世界产生冲突影响，这个冲突影响表示为茉美香的威力值减去模仿者的威力值得到的差对  取模。

在发动必杀技前，茉美香和对手会依次若干次的Shining Shower对波攻击，成功击破者的体力会叠加对手的体力，魔力也会叠加对手的魔力。具体来说，对波攻击的情况表示为01字符串的一个连续区间  ，按照从左到右的顺序进行，其中 表示当前对波攻击茉美香成功击破对手，  表示茉美香被对手击破。因此，为了击败对手，茉美香需要选择合适的区间进行对波攻击。

现在告诉你茉美香和对手初始的体力和魔力，以及对波情况的依据字符串，然后进行若干次“神的干预”，有以下两种干预：

1. 根据一个对波区间  ，将对应区间子字符串里的  变成  ， 变成  。
2. 询问一个对波区间  ，请你输出世界受到的冲突影响。

第一行输入两个正整数   和  ， 代表01字符串的长度， 代表干预次数。

第二行输入四个正整数 ， ， ， ，依次代表茉美香的初始体力，模仿者的初始体力，茉美香的初始魔力，模仿者的初始魔力。

接下来 行，每行输入三个正整数  ， ，，分别代表干预种类，和干预区间。若  代表第一种干预，若  代表第二种干预。

输入保证：

输出若干行第二种干预的结果。每次结果输出世界受到的冲突影响。

3 3
1 2 1 2
101
2 1 3
1 1 3
2 1 3

39
999999974

L题样例39解释：
初始 (1,1) (2,2)
s[1]: (3,3) (2,2)
s[2]: (3,3) (5,5)
s[3]: (8,8) (5,5)
答案 = 8*8 - 5*5 = 64 - 25 = 39