F. 邵接待之战
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
"我纵茕茕孑立，难避漫漫长夜.

然长夜终尽，天将启明……

惟以平旦之孤星，何胜东方之既白.

还请觉悟. 今朝此日，都市一星，势必陨灭."

—— 邵

你和邵即将进行接待战.

你与邵均各自有：

  • 一条血量条与一条混乱条，初值均为满（等于给定的上限）.血量条会因血量伤害而减少，混乱条会因为混乱伤害而减少.
  • 一个行动队列，初始为空.

在接下来的 R 个回合内，每回合双方会获得若干行动并加入对应队列，然后按规则进行一系列两两对抗.

每个回合会依次进行三个环节：获取行动——对抗——回合结束

回合流程：

  • 获取行动环节，双方首先将该回合的获得的行动顺序 添加至自己的行动队列末尾.
  • 对抗环节，之后双方同时从行动队列队首取出行动，行动两两进行对抗. 直到一方的行动队列为空 且另一方行动队列中不存在"进攻"行动时，进入回合结束环节.
  • 回合结束环节，进行崩溃状态复原的结算，具体规则在混乱与死亡部分给出.

每个行动包含一个类型 和一个点数，行动一共有三种类型：

  • "Attack ——"进攻"，
  • "Defence ——"招架"，
  • "Hide ——"闪避"，

对抗规则：

  • 自身进攻行动 与 对方进攻行动 对抗：
    • 自身进攻点数 > 对方进攻点数：对方受到自身进攻点数 的 血量伤害 和 混乱伤害. 双方该次行动移除.
    • 自身进攻点数 = 对方进攻点数：无变化. 双方该次行动移除.
    • 自身进攻点数 < 对方进攻点数：自身受到对方进攻点数 的 血量伤害 和 混乱伤害. 双方该次行动移除.
  • 自身进攻行动 与 对方招架行动 对抗：
    • 自身进攻点数 > 对方招架点数：对方受到自身进攻点数-对方招架点数 的 血量伤害 和 混乱伤害. 双方该次行动移除.
    • 自身进攻点数 = 对方招架点数：无变化. 双方该次行动移除.
    • 自身进攻点数 < 对方招架点数：自身收到对方招架点数-自身进攻点数 的混乱伤害. 双方该次行动移除.
  • 自身进攻行动 与 对方闪避行动 对抗：
    • 自身进攻点数 > 对方闪避点数：对方受到自身进攻点数 的 血量伤害 和 混乱伤害. 双方该次行动移除.
    • 自身进攻点数 <= 对方闪避点数：对方恢复对方闪避点数 的混乱值（无法超出混乱条上限）. 自身该次行动移除，对方闪避行动重新放回队列队首.
  • 自身进攻行动时若对方行动队列为空，则对方受到自身进攻点数 的 血量伤害 和 混乱伤害. 自身该次行动移除.
  • 自身招架行动 与 对方招架行动 对抗：
    • 自身招架点数 > 对方招架点数：对方受到自身招架点数 的 混乱伤害. 双方该次行动移除.
    • 自身招架点数 = 对方招架点数：无变化. 双方该次行动移除.
    • 自身招架点数 < 对方招架点数：自身受到对方招架点数 的 混乱伤害. 双方该次行动移除.
  • 自身招架行动 与 对方闪避行动 对抗：
    • 自身招架点数 > 对方闪避点数：对方受到自身招架点数 的 混乱伤害. 双方该次行动移除.
    • 自身招架点数 <= 对方闪避点数：对方恢复对方闪避点数的混乱值（无法超出混乱条上限）. 自身该次行动移除，对方闪避行动重新放回队列队首.
  • 自身招架行动时若对方行动队列为空，则无变化. 自身该次行动移除.
  • 自身闪避行动 与 对方闪避行动 对抗：
    • 自身闪避点数 > 对方闪避点数：自身恢复自身闪避点数 的混乱值（无法超出混乱条上限）. 对方该次行动移除，自身闪避行动重新放回队列队首.
    • 自身闪避点数 = 对方闪避点数：无变化. 双方该次行动移除.
    • 自身闪避点数 < 对方闪避点数：对方恢复对方闪避点数 的混乱值（无法超出混乱条上限）. 自身该次行动移除，对方闪避行动重新放回队列队首.
  • 自身闪避行动时若对方行动队列为空，则无变化. 自身该次行动移除.

混乱与死亡：

  • 当某角色混乱条降为 0的瞬间：
    • 其立即陷入崩溃状态，并立刻清空自己的行动队列；
    • 其跳过下一回合获取行动阶段.
    • 其在下回合回合结束时立即恢复混乱条至上限，恢复正常状态.
    • 注：崩溃状态不会叠加，即当角色进入崩溃状态时不会再触发崩溃状态，直到恢复正常为止.
  • 当任一角色血量条降为 0的瞬间：该角色死亡. 游戏立即结束.
  • 伤害与恢复均饱和：
    • 承受的血量/混乱伤害不会使条值低于 0，超出部分舍弃；
    • 恢复混乱值不会超过该角色混乱条上限.

在游戏结束后，输出你和邵的剩余血量，无论双方队列是否为空.

Input

第一行为四个整数 HP1, SP1, HP2, SP2(1 ≤ HP1, SP1, HP2, SP2 ≤ 1 × 1012),分别表示自身的血量条，混乱条，对方的血量条，混乱条；

第二行为一个整数 R(1 ≤ R ≤ 1 × 105)；

之后的每 R 组数据：

第一行为两个整数 k1, k2(0 ≤ k1, k2 ≤ 1 × 105), 分别表示自身该回合获得的行动数量和对方该回合获得的行动数量.

接下来 k1 行为自身该回合获得的行动，

第一个值为字符串 s1, i(), 表示行动类型；第二个值为整数 c1, i(0 ≤ c1, i ≤ 1 × 1012) 表示该行动的行动点数.

接下来 k2 行为对方该回合获得的行动，

第一个值为字符串 s2, i(), 表示行动类型；第二个值为整数 c2, i(0 ≤ c2, i ≤ 1 × 1012) 表示该行动的行动点数.

题目保证 .

Output

两个整数，分别表示游戏结束后自身的血量和邵的血量.

Examples
Input
20 10 20 10
3
3 3
Attack 6
Attack 3
Defence 4
Hide 5
Attack 8
Defence 2
2 2
Attack 4
Attack 7
Attack 5
Hide 7
2 2
Attack 2
Defence 8
Hide 6
Attack 6
Output
6 3
Input
12 6 10 5
2
3 3
Hide 4
Attack 3
Attack 7
Hide 5
Defence 2
Attack 6
2 1
Attack 4
Attack 5
Attack 100
Output
12 0
Note

样例一解释：

  • 初始：我方血量上限为20，混乱上限为10；邵血量上限为20，混乱上限为10
  • 回合一:
    • 获取行动：获取行动后我方行动队列为；邵行动队列为.
    • 对抗：
      • 我方对抗邵，邵受到6的血量伤害和混乱伤害，两个行动移除;
      • 我方对抗邵，我方受到8的血量伤害和混乱伤害，两个行动移除；
      • 我方对抗邵，邵受到4的混乱伤害，两个行动移除.此时邵的混乱条为0，进入崩溃，行动队列被立即清空，且下回合跳过获取行动阶段;
      • 此时双方行动队列为空，符合回合结束条件，进入回合结束阶段.
    • 回合结束.
  • 回合二：
    • 获取行动：获取行动后我方行动队列为；邵行动队列为空.
    • 对抗：
      • 我方对抗邵的空行动，邵受到4的血量伤害和混乱伤害，我方行动移除;
      • 我方对抗邵的空行动，邵受到7的血量伤害和混乱伤害，我方行动移除；
      • 此时双方行动队列为空，符合回合结束条件，进入回合结束阶段.
    • 回合结束；邵恢复正常状态，混乱条回复到上限10.
  • 回合三：
    • 获取行动：获取行动后我方行动队列为；邵行动队列为.
    • 对抗：
      • 我方对抗邵，邵回复6的混乱值，由于邵的混乱条为满值，所以无变化.我方行动移除，邵行动放回队首;
      • 我方对抗邵，邵受到8的混乱伤害，双方行动移除；
      • 我方空行动对抗邵，我方收到6的血量伤害和混乱伤害，我方行动移除.
      • 此时双方行动队列为空，符合回合结束条件，进入回合结束阶段.
    • 回合结束.
最终结果：我方剩余血量为6，邵剩余血量为3.

样例二解释：

  • 初始：我方血量上限为12，混乱上限为6；邵血量上限为10，混乱上限为5
  • 回合一:
    • 获取行动：获取行动后我方行动队列为；邵行动队列为.
    • 对抗：
      • 我方对抗邵，邵恢复5的混乱伤害，由于邵的混乱条为满值，所以无变化。我方行动移除，邵行动放回队首；
      • 我方对抗邵，邵恢复5的混乱伤害，由于邵的混乱条为满值，所以无变化。我方行动移除，邵行动放回队首；
      • 我方对抗邵，邵受到7的血量伤害和混乱伤害，由于邵此时的混乱值为5，舍去溢出的2点伤害.此时邵的混乱条为0，进入崩溃，行动队列被立即清空，且下回合跳过获取行动阶段;
      • 此时双方行动队列为空，符合回合结束条件，进入回合结束阶段.
    • 回合结束；
  • 回合二：
    • 获取行动：获取行动后我方行动队列为；邵行动队列为空.
    • 对抗：
      • 我方对抗邵的空行动，邵受到4的血量伤害和混乱伤害，由于邵此时的血量为3，舍弃溢出的1点伤害.邵的血量为0，立即结束游戏.
最终结果：我方剩余血量为12，邵剩余血量为0.