Halloween is almost here! Here in the United States, it is a tradition for young children to dress up as demons and super heros wonder around in the dark very late at night, visit random strangers in their houses, and ask for candy.
Alice and Bob just solved a problem that required them to eat about $10^9$ candies and are very full now, so instead, they will ask their neighbors to either show them a trick, or give them a brand new treap ("trick or treap")! $q$ times, one of the following will happen:
- 1. This neighbor will given them a new treap node $i$, with value $y$. Here, $i$ is the query number.
- 2. This neighbor will perform a trick: if the nodes $y$ and $z$ are not in the same group, he will merge them into the same group, with $y$'s group to the left of $z$'s group. Otherwise, he will teach them how to juggle.
- 3. This neighbor will perform a different trick: If the group containing node $y$ contains more than $z$ nodes, he will split the first $z$ nodes from the rest of them. Otherwise, he will teach them Kotlin.
- 4. Alice's and Bob's overprotective mother will call and ask them about the sum of values in the group that $y$ is in.
Can you write a bot to pretend to answer the queries for Alice so that she can continue to bother her neighbors in the middle of the night without interruption?
The first line will contain a single integer $q$. $1 <= q <= 5 * 10^5$ $q$ lines follow. They will look like one of the following:
- $1$ $y$. In this case $0 <= y <= 10^5$.
- $2$ $y$ $z$. Nodes $y$ and $z$ will already exist.
- $3$ $y$ $z$. Node $y$ will already exist. $0 < z$.
- $4$ $y$. Node $y$ will already exist.
For each query of type 4, print the sum of the values in the queried group.
## Input
The first line will contain a single integer $q$. $1 <= q <= 5 * 10^5$ $q$ lines follow. They will look like one of the following:- $1$ $y$. In this case $0 <= y <= 10^5$.- $2$ $y$ $z$. Nodes $y$ and $z$ will already exist.- $3$ $y$ $z$. Node $y$ will already exist. $0 < z$.- $4$ $y$. Node $y$ will already exist.
## Output
For each query of type 4, print the sum of the values in the queried group.
[samples]
**Definitions**
Let $ q \in \mathbb{Z}^+ $ be the number of queries.
Let $ V \subseteq \mathbb{Z}_{\geq 0} $ be the set of node identifiers that have been added.
Let $ \text{val}: V \to \mathbb{R} $ be a function mapping each node $ i \in V $ to its value $ y $.
Let $ \mathcal{G} = \{ G_1, G_2, \dots \} $ be a partition of $ V $ into disjoint ordered groups (lists), where each group $ G $ is a sequence of nodes $ (n_1, n_2, \dots, n_k) $, ordered left to right.
**Constraints**
1. $ 1 \leq q \leq 5 \cdot 10^5 $
2. For all queries:
- Type 1: $ 0 \leq y \leq 10^5 $, and node $ y $ is newly added.
- Type 2: Nodes $ y, z \in V $, and $ y \neq z $.
- Type 3: Node $ y \in V $, and $ z > 0 $.
- Type 4: Node $ y \in V $.
**Operations**
For each query:
- **Type 1 ($1\ y$)**: Add new node $ y $ with $ \text{val}(y) = y $ as a singleton group: $ \mathcal{G} \gets \mathcal{G} \cup \{ (y) \} $.
- **Type 2 ($2\ y\ z$)**: Let $ G_y, G_z \in \mathcal{G} $ be the groups containing $ y $ and $ z $, respectively. If $ G_y \neq G_z $, replace $ G_y $ and $ G_z $ with $ G_y \oplus G_z $ (concatenation, $ G_y $ left of $ G_z $). Otherwise, do nothing.
- **Type 3 ($3\ y\ z$)**: Let $ G_y \in \mathcal{G} $ be the group containing $ y $, with $ |G_y| = k $. If $ k > z $, replace $ G_y $ with two groups: $ (n_1, \dots, n_z) $ and $ (n_{z+1}, \dots, n_k) $. Otherwise, do nothing.
- **Type 4 ($4\ y$)**: Let $ G_y \in \mathcal{G} $ be the group containing $ y $. Output $ \sum_{n \in G_y} \text{val}(n) $.
**Objective**
For each query of type 4, output the sum of values in the group containing node $ y $.