CF1535E.Gold Transfer

You are given a rooted tree. Each vertex contains $a_i$ tons of gold, which costs $c_i$ per one ton. Initially, the tree consists only a root numbered $0$ with $a_0$ tons of gold and price $c_0$ per ton.

There are $q$ queries. Each query has one of two types:

1. Add vertex $i$ (where $i$ is an index of query) as a son to some vertex $p_i$; vertex $i$ will have $a_i$ tons of gold with $c_i$ per ton. It's guaranteed that $c_i \gt c_{p_i}$.
2. For a given vertex $v_i$ consider the simple path from $v_i$ to the root. We need to purchase $w_i$ tons of gold from vertices on this path, spending the minimum amount of money. If there isn't enough gold on the path, we buy all we can.

If we buy $x$ tons of gold in some vertex $v$ the remaining amount of gold in it decreases by $x$ (of course, we can't buy more gold that vertex has at the moment). For each query of the second type, calculate the resulting amount of gold we bought and the amount of money we should spend.

Note that you should solve the problem in online mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query, so don't forget to flush output after printing answers. You can use functions like fflush(stdout) in C++ and BufferedWriter.flush in Java or similar after each writing in your program. In standard (if you don't tweak I/O), endl flushes cout in C++ and System.out.println in Java (or println in Kotlin) makes automatic flush as well.

你将得到一棵有根树。每个顶点 $i$ 包含 $a_i$ 吨黄金，每吨价格为 $c_i$。初始时，树仅包含编号为 $0$ 的根节点，其拥有 $a_0$ 吨黄金，每吨价格为 $c_0$。

共有 $q$ 个查询，每个查询属于以下两种类型之一：

1. 将顶点 $i$（其中 $i$ 为该查询的索引）作为子节点添加到某个顶点 $p_i$ 下；顶点 $i$ 拥有 $a_i$ 吨黄金，每吨价格为 $c_i$。保证 $c_i > c_{p_i}$。
2. 对于给定顶点 $v_i$，考虑从 $v_i$ 到根节点的简单路径。我们需要从该路径上的顶点中购买总共 $w_i$ 吨黄金，使得花费的总金额最小。若路径上黄金总量不足 $w_i$ 吨，则尽可能多地购买（即买光所有可用黄金）。

若在某顶点 $v$ 购买 $x$ 吨黄金，则该顶点剩余黄金量减少 $x$ 吨（当然，不能购买超过该顶点当前所拥有的黄金量）。对每个第 2 类查询，请计算实际购得的黄金总量以及所需支付的总金额。

注意：本题需以在线模式求解。这意味着你无法一次性读入全部输入；你只能在输出上一个查询的答案之后，才能读入下一个查询。因此，请务必在每次输出答案后刷新输出缓冲区。在 C++ 中可使用 fflush(stdout)，在 Java 中可使用 BufferedWriter.flush() 或类似方法；在标准设置下（未自定义 I/O），C++ 中的 endl 会自动刷新 cout，Java 中的 System.out.println（或 Kotlin 中的 println）也会自动刷新。

The first line contains three integers $q$, $a_0$ and $c_0$ ($1 \le q \le 3 \cdot 10^5$; $1 \le a_0, c_0 \lt 10^6$) — the number of queries, the amount of gold in the root and its price.

Next $q$ lines contain descriptions of queries; The $i$-th query has one of two types:

• "$1$ $p_i$ $a_i$ $c_i$" ($0 \le p_i \lt i$; $1 \le a_i, c_i \lt 10^6$): add vertex $i$ as a son to vertex $p_i$. The vertex $i$ will have $a_i$ tons of gold with price $c_i$ per one ton. It's guaranteed that $p_i$ exists and $c_i \gt c_{p_i}$.
• "$2$ $v_i$ $w_i$" ($0 \le v_i \lt i$; $1 \le w_i \lt 10^6$): buy $w_i$ tons of gold from vertices on path from $v_i$ to $0$ spending the minimum amount of money. If there isn't enough gold, we buy as much as we can. It's guaranteed that vertex $v_i$ exist.

It's guaranteed that there is at least one query of the second type.

第一行包含三个整数 $q$、$a_0$ 和 $c_0$（$1 \le q \le 3 \cdot 10^5$；$1 \le a_0, c_0 \lt 10^6$）——分别表示查询次数、根节点（编号为 $0$）所含黄金吨数及其每吨价格。

接下来 $q$ 行，每行描述一个查询；第 $i$ 个查询为以下两种类型之一：

• “$1$ $p_i$ $a_i$ $c_i$”（$0 \le p_i \lt i$；$1 \le a_i, c_i \lt 10^6$）：将顶点 $i$ 作为顶点 $p_i$ 的子节点加入。顶点 $i$ 拥有 $a_i$ 吨黄金，每吨价格为 $c_i$。保证 $p_i$ 已存在，且 $c_i \gt c_{p_i}$。
• “$2$ $v_i$ $w_i$”（$0 \le v_i \lt i$；$1 \le w_i \lt 10^6$）：从顶点 $v_i$ 到根节点 $0$ 的路径上的所有顶点中，购买 $w_i$ 吨黄金，要求花费金额最少。若黄金总量不足，则尽可能多地购买。保证顶点 $v_i$ 已存在。

保证至少存在一个第二类查询。

For each query of the second type, print the resulting amount of gold we bought and the minimum amount of money we should spend.

对于每个第二类查询，输出我们购买的黄金总量以及应花费的最少金额。

Explanation of the sample:

At the first query, the tree consist of root, so we purchase $2$ tons of gold and pay $2 \cdot 2 = 4$. $3$ tons remain in the root.

At the second query, we add vertex $2$ as a son of vertex $0$. Vertex $2$ now has $3$ tons of gold with price $4$ per one ton.

At the third query, a path from $2$ to $0$ consists of only vertices $0$ and $2$ and since $c_0 \lt c_2$ we buy $3$ remaining tons of gold in vertex $0$ and $1$ ton in vertex $2$. So we bought $3 + 1 = 4$ tons and paid $3 \cdot 2 + 1 \cdot 4 = 10$. Now, in vertex $0$ no gold left and $2$ tons of gold remain in vertex $2$.

At the fourth query, we add vertex $4$ as a son of vertex $0$. Vertex $4$ now has $1$ ton of gold with price $3$.

At the fifth query, a path from $4$ to $0$ consists of only vertices $0$ and $4$. But since no gold left in vertex $0$ and only $1$ ton is in vertex $4$, we buy $1$ ton of gold in vertex $4$ and spend $1 \cdot 3 = 3$. Now, in vertex $4$ no gold left.

样例解释：

在第一个查询中，树仅包含根节点，因此我们购买 $2$ 吨黄金，并支付 $2 \cdot 2 = 4$。此时根节点剩余 $3$ 吨黄金。

在第二个查询中，我们将顶点 $2$ 作为顶点 $0$ 的子节点加入。顶点 $2$ 当前拥有 $3$ 吨黄金，单价为 $4$。

在第三个查询中，从顶点 $2$ 到顶点 $0$ 的路径仅包含顶点 $0$ 和 $2$；由于 $c_0 \lt c_2$，我们在顶点 $0$ 购买其剩余的 $3$ 吨黄金，在顶点 $2$ 购买 $1$ 吨黄金。因此共购买 $3 + 1 = 4$ 吨黄金，花费为 $3 \cdot 2 + 1 \cdot 4 = 10$。此时顶点 $0$ 中黄金已售罄，顶点 $2$ 中剩余 $2$ 吨黄金。

在第四个查询中，我们将顶点 $4$ 作为顶点 $0$ 的子节点加入。顶点 $4$ 当前拥有 $1$ 吨黄金，单价为 $3$。

在第五个查询中，从顶点 $4$ 到顶点 $0$ 的路径仅包含顶点 $0$ 和 $4$。但由于顶点 $0$ 中已无黄金剩余，而顶点 $4$ 中仅有 $1$ 吨黄金，因此我们仅在顶点 $4$ 购买 $1$ 吨黄金，花费 $1 \cdot 3 = 3$。此时顶点 $4$ 中黄金已售罄。