ChannelTalk 是由 Channel Corp 开发的一款多合一 AI 即时通讯软件，旨在通过与客户的实时沟通帮助企业实现可持续发展。通过利用 CRM 数据和 AI，它提高了效率并改善了客户体验，提供符合“客户拥有答案”这一哲学的服务。ChannelTalk 在日本已经取得了市场领先的份额，并且其收入正在迅速增长，计划将业务从亚洲扩展到美国市场。成功的关键在于“产品”——ChannelTalk 超过一半的员工是开发人员，他们作为一个团队专注于创造一个优秀的产品。

为了收集客户意见，Channel Corp. 决定在其交流平台 ChannelTalk 上试点几个讨论频道。

共有 $N$ 个频道，编号为 $1$ 到 $N$。所有频道都针对同一个话题讨论相反的观点。在频道 $i$ 中，有 $A_i$ 个赞同该观点的人和 $B_i$ 个反对该观点的人。此外，频道 $i$ 的最大容量为 $C_i$，$C_i$ 是一个偶数。（作为特例，频道 $N$ 没有人数限制。）

有时，会有新的参与者进入某个频道。该参与者也会赞同或反对该观点。每当有新参与者进入时，根据 ChannelTalk 的政策，会进行以下流程：

• 当新参与者进入频道时，如果频道内的人数没有超过该频道的容量，他们将留在该频道中。
• 如果人数超过了频道的容量，则总人数会变成一个奇数。在这种情况下，人数较多的一方（赞同者或反对者）中的一名参与者将被自动移动到下一个编号的频道。（被移动的参与者的观点保持不变。）
• 如果由于上述步骤导致下一个频道的人数超过了该频道的容量，则重复相同的过程。该过程将一直重复，直到每个频道中的人数都在其容量范围内。注意，频道 $N$ 没有容量限制，因此该过程最终一定会结束。

为了协助试点该功能，你需要编写一个程序，在新参与者进入时管理每个频道中的人数。具体来说，你的程序需要快速执行以下询问：

• 1 x v：$v$ 个赞同该观点的全新参与者进入频道 $x$。
• 2 x v：$v$ 个反对该观点的全新参与者进入频道 $x$。
• 3 x：输出频道 $x$ 中赞同该观点的人数和反对该观点的人数。

注意，在类型 1 和类型 2 的询问中，$v$ 个新参与者是一个接一个地进入频道的，并且只有在前一个参与者引起的所有频道重新分配流程全部完成后，下一个参与者才会进入。

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $Q$。($2 \le N \le 200\,000$；$1 \le Q \le 200\,000$)

接下来的 $N - 1$ 行中，第 $i$ 行包含三个空格分隔的整数 $A_i$、$B_i$ 和 $C_i$。($0 \le A_i, B_i \le 10^9$；$2 \le C_i \le 10^9$；$A_i + B_i \le C_i$；$C_i$ 为偶数)

输入的第 $N + 1$ 行包含两个空格分隔的整数 $A_N$ 和 $B_N$。($0 \le A_N, B_N \le 10^9$)

接下来的 $Q$ 行中，第 $i$ 行以与题目描述中相同的格式描述第 $i$ 个询问。对于所有询问，满足以下条件：$1 \le x \le N$，$1 \le v \le 10^9$。

保证至少存在一个类型 3 的询问。

输出格式

对于所有类型 3 的询问，输出对应频道中赞同该观点的人数和反对该观点的人数。

样例

输入样例 1

4 5
2 1 4
0 3 6
2 0 2
2 4
1 2 2
3 2
1 2 4
3 2
3 4

输出样例 1

2 3
3 3
5 4

输入样例 2

2 3
0 0 4
0 0
2 1 6
3 1
3 2

输出样例 2

0 4
0 2