407422: GYM102787 Z Trick or Treap

Memory Limit:1024 MB Time Limit:8 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Z. Trick or Treaptime limit per test8 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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?

Input

The first line will contain a single integer $$$q$$$. $$$1 \leq q \leq 5*10^5$$$ $$$q$$$ lines follow. They will look like one of the following:

- $$$1$$$ $$$y$$$. In this case $$$0 \leq y \leq 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.

ExamplesInput
10
1 38788
3 1 1
3 1 2
1 56200
3 1 2
3 1 2
4 4
3 4 4
4 1
3 4 6
Output
56200
38788
Input
8
1 60420
3 1 1
3 1 1
1 49164
2 1 1
2 4 1
2 1 4
1 24036
Output

加入题单

上一题 下一题 算法标签: