亡语

Problem Description

你在玩一款在线卡牌游戏《炉石传说》。 你有 $n$ 个随从，随从死亡当且仅当其生命值小于等于 $0$。一个随从死亡后，将会触发亡语。随从分为三类，每类随从具有不同的 存活效果 与 亡语效果：

• 存活效果：随从存活时产生的效果，死亡但未结算亡语的随从不具有 存活效果
• 亡语效果：一个随从 首次 生命值降到小于等于 $0$ 时触发的效果 | 类型 | 初始信息 | 存活效果 | 亡语效果 | | :-------------------------: | :----------------------------: | :--------------------------------: | :------------------------------: | | 1 | $h$ - 初始生命值 | 无 | 对所有随从造成 1 点伤害 | | 2 | $h$ - 初始生命值
  $x$ - 初始等级
  $k$ - 亡语召唤数量 | 无 | 召唤 $k$ 个 [ 编号继承此随从 ,
  初始生命值为此随从初始生命值 2 倍 ,
  初始等级为 $x-1$ ,
  亡语召唤数量为 $k$ ] 的第二类随从
  （也具有第二类随从的亡语效果）。
  特别地，等级 0 的随从死亡时不会召唤新的随从。 | | 3 | $h$ - 初始生命值 | 所有随从受到的伤害增加一倍。
  假设当前有 $m$ 个第三类随从存活，
  那么所有随从（包括本身）受到的伤害
  会变为 $m+1$ 倍。 | 无 | 假设触发亡语的顺序依次为 亡语 $1$，亡语 $2$，那么因为亡语 $1$ 或 $2$ 死亡的随从，其亡语触发顺序遵循如下规则：
• 因亡语 $1$ 死亡的随从，其亡语结算在 因亡语 $2$ 死亡的随从 之前；（可以理解为 BFS）
• 因同一个亡语死亡的随从，优先结算编号较小的随从的亡语 给定 $n$ 个随从的初始信息，请你求出当第一个随从死亡（强制死亡）并依次结算所有亡语后，所有随从的状态，具体见输出格式。

Input

输入包含多组测试数据： 输入的第一行包含一个整数 $T$ ($1\le T\le 10)$，表示测试数据的组数。 对于每组测试数据： 第一行包含一个整数 $n$ ($1\le n\le 10^5$)，表示随从个数。 接下来 $n$ 行，描述 $n$ 个随从，第 $i$ 个随从为三种类型中的一种：

• $1 \ h_i$ ($1\le h_i\le 10^9$)，表示第 $i$ 个随从属于第一类，初始生命值为 $h_i$
• $2\ h_i \ x_i \ k_i$ ($1\le h_i \le 10^9, 0\le x_i\le 10^5, 1\le k_i\le 10$)，表示第 $i$ 个随从属于第二类，初始生命值为 $h_i$，等级为 $x_i$，亡语召唤数量为 $k_i$
• $3 \ h_i$ ($1\le h_i\le 10^9$)，表示第 $i$ 个随从属于第三类，初始生命值为 $h_i$

Output

对于每组测试数据： 输出 $n$ 行，第 $i$ 行表示第 $i$ 个随从的状态： 若为第一类随从，输出一个整数 $h_i$ 表示它的剩余生命值（ $h_i=0$ 表示其死亡）。 若为第二类随从，输出三个整数 $m_i,x_i,h_i$ ：

• 若第 $i$ 个随从未死亡，则 $h_i$ 等于其剩余生命值，$m_i = 1$，$x_i$ 等于其初始等级；
• 若第 $i$ 个随从已死亡，则 $m_i,x_i,h_i$ 表示其衍生随从的状态：$m_i$ 个等级为 $x_i$，剩余生命值为 $h_i$ 的随从；
• 特殊地，若第二类随从及其衍生的随从均死亡，$m_i = 0$，$x_i = 0$，$h_i = 0$ 。 若为第三类随从，输出一个整数 $h_i$ 表示它的剩余生命值（ $h_i=0$ 表示其死亡）。

Sample Input

3
3
1 1
2 1 2 2
3 7
5
1 1
2 1 2 3
1 1
2 1 2 3
3 7
5
1 1
2 1 2 3
1 1
2 1 2 3
3 1

Sample Output

0
2 1 2
5
0
9 0 4
0
3 1 2
3
0
3 1 1
0
3 1 2
0

Hint

对于第二组样例，完整过程如下：

• 随从 $1$ 死亡，由于随从 $5$ 未死亡，所以对所有随从造成 $2$ 点伤害，随从 $2,3,4$ 死亡；
• 随从 $2$ 亡语结算，召唤三个等级为 $1$，血量为 $2$ 的随从；
• 随从 $3$ 亡语结算，由于随从 $5$ 未死亡，所以对所有随从造成 $2$ 点伤害，新随从 $2$ 死亡；
• 随从 $4$ 亡语结算，召唤三个等级为 $1$，血量为 $2$ 的随从；
• 新随从 $2$ 亡语结算，召唤九个等级为 $0$，血量为 $4$ 的随从。
  对于第三组样例，完整过程如下：
  
• 随从 $1$ 死亡，由于随从 $5$ 未死亡，所以对所有随从造成 $2$ 点伤害，随从 $2,3,4$ 死亡；
• 随从 $2$ 亡语结算，召唤三个等级为 $1$，血量为 $2$ 的随从；
• 随从 $3$ 亡语结算，由于随从 $5$ 死亡，所以对所有随从造成 $1$ 点伤害；
• 随从 $4$ 亡语结算，召唤三个等级为 $1$，血量为 $2$ 的随从。

Source

2024“钉耙编程”中国大学生算法设计超级联赛（9）