{"raw_statement":[{"iden":"statement","content":"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.\n\nAlice 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:\n\n- 1. This neighbor will given them a new treap node $i$, with value $y$. Here, $i$ is the query number.\n\n- 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.\n\n- 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.\n\n- 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.\n\nCan 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?\n\nThe first line will contain a single integer $q$. $1 <= q <= 5 * 10^5$ $q$ lines follow. They will look like one of the following:\n\n- $1$ $y$. In this case $0 <= y <= 10^5$.\n\n- $2$ $y$ $z$. Nodes $y$ and $z$ will already exist.\n\n- $3$ $y$ $z$. Node $y$ will already exist. $0 < z$.\n\n- $4$ $y$. Node $y$ will already exist.\n\nFor each query of type 4, print the sum of the values in the queried group.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"For each query of type 4, print the sum of the values in the queried group."},{"iden":"examples","content":"Input10\n1 38788\n3 1 1\n3 1 2\n1 56200\n3 1 2\n3 1 2\n4 4\n3 4 4\n4 1\n3 4 6\nOutput56200\n38788\nInput8\n1 60420\n3 1 1\n3 1 1\n1 49164\n2 1 1\n2 4 1\n2 1 4\n1 24036\nOutput"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries.  \nLet $ V \\subseteq \\mathbb{Z}_{\\geq 0} $ be the set of node identifiers that have been added.  \nLet $ \\text{val}: V \\to \\mathbb{R} $ be a function mapping each node $ i \\in V $ to its value $ y $.  \nLet $ \\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.  \n\n**Constraints**  \n1. $ 1 \\leq q \\leq 5 \\cdot 10^5 $  \n2. For all queries:  \n   - Type 1: $ 0 \\leq y \\leq 10^5 $, and node $ y $ is newly added.  \n   - Type 2: Nodes $ y, z \\in V $, and $ y \\neq z $.  \n   - Type 3: Node $ y \\in V $, and $ z > 0 $.  \n   - Type 4: Node $ y \\in V $.  \n\n**Operations**  \nFor each query:  \n- **Type 1 ($1\\ y$)**: Add new node $ y $ with $ \\text{val}(y) = y $ as a singleton group: $ \\mathcal{G} \\gets \\mathcal{G} \\cup \\{ (y) \\} $.  \n- **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.  \n- **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.  \n- **Type 4 ($4\\ y$)**: Let $ G_y \\in \\mathcal{G} $ be the group containing $ y $. Output $ \\sum_{n \\in G_y} \\text{val}(n) $.  \n\n**Objective**  \nFor each query of type 4, output the sum of values in the group containing node $ y $.","simple_statement":"You are given q queries. Initially, no nodes exist.\n\n- Type 1: Add a new node with value y.\n- Type 2: Merge the groups containing nodes y and z (y’s group goes to the left of z’s).\n- Type 3: Split the group containing y: take the first z nodes out as a new group (if group has ≤ z nodes, do nothing).\n- Type 4: Print the sum of values in the group containing node y.\n\nAnswer all type 4 queries.","has_page_source":false}