You are given a rooted tree with root $$$1$$$ and $$$N$$$ nodes. Each node $$$i$$$ has an initial weight $$$M_i$$$. At all times, the system strictly maintains the following property: for any non-root node $$$x$$$, its weight never exceeds that of its parent, that is, $$$M_{\text{parent}(x)} \ge M_x$$$.
You need to process $$$Q$$$ operations online. The operations are of the following two types:
- 1 u w: Query. Starting from node $$$u$$$, move upward along the tree edges toward the root, and find the first node whose weight is at least $$$w$$$ (including $$$u$$$ itself). Output the index of that node. If no such node exists all the way up to the root, output -1.
- 2 x v: Update. Attempt to add $$$v$$$ to the weight of node $$$x$$$ ($$$v$$$ may be negative), that is, let $$$M_x \leftarrow M_x + v$$$. To avoid violating the tree property, a legality check must be performed before the update:
- If $$$x \neq 1$$$ and $$$M_x + v \gt M_{\text{parent}(x)}$$$, then the update fails.
- If $$$x$$$ is not a leaf node and $$$M_x + v \lt \max_{y \in \text{children}(x)} M_y$$$, then the update fails.
If both checks pass, then the update is actually performed and SUCCESS is output; otherwise, the update is rejected, the state of the tree remains unchanged, and FAILED is output.
Output
For each test case, output $$$Q$$$ lines, each corresponding to the result of one operation:
- For a 1 u w operation, output the index of the node satisfying the condition; if no such node exists, output -1.
- For a 2 x v operation, output SUCCESS if the update succeeds, and FAILED if the update fails.
Example
Output
2
-1
FAILED
FAILED
SUCCESS
4
Note
In the sample, the tree structure is as follows: node $$$1$$$ has children $$$2$$$ and $$$3$$$; node $$$2$$$ has children $$$4$$$ and $$$5$$$.
The initial weights are $$$M = [100, 80, 50, 30, 20]$$$.
- Operation 1 1 4 40: starting from node $$$4$$$, we move upward to find a node whose weight is at least $$$40$$$. The current weight of node $$$4$$$ is $$$30 \lt 40$$$, while its parent node $$$2$$$ has weight $$$80 \ge 40$$$, which satisfies the condition, so the output is 2.
- Operation 2 1 5 150: starting from node $$$5$$$, we move upward to find a node whose weight is at least $$$150$$$. None of the nodes on the path, including the root node $$$1$$$ (whose weight is $$$100$$$), satisfies the condition, so the output is -1.
- Operation 3 2 2 30: we attempt to increase the weight of node $$$2$$$ by $$$30$$$, so the new weight would be $$$110$$$. Since $$$110 \gt M_1$$$ ($$$100$$$), this violates the property that a parent's weight must be at least that of its child, so the update fails and the output is FAILED.
- Operation 4 2 2 -60: we attempt to decrease the weight of node $$$2$$$ by $$$60$$$, so the new weight would be $$$20$$$. Since $$$20 \lt \max(M_4, M_5)$$$ ($$$30$$$), this also violates the monotonicity property of the tree weights, so the update fails and the output is FAILED.
- Operation 5 2 4 10: we attempt to increase the weight of node $$$4$$$ by $$$10$$$, so the new weight becomes $$$40$$$. This satisfies $$$40 \le M_2$$$ ($$$80$$$), and node $$$4$$$ is a leaf node, so the update succeeds. We update $$$M_4 = 40$$$ and output SUCCESS.
- Operation 6 1 4 40: again starting from node $$$4$$$, we move upward to find a node whose weight is at least $$$40$$$. Since the previous update succeeded, we now have $$$M_4 = 40 \ge 40$$$, so node $$$4$$$ itself already satisfies the condition, and the output is 4.