A. Multisets
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver likes data structure problems, but he thinks that data structure problems on arrays with interval queries are boring. So he came up with a different kind of data structure problem, with multisets!

There is a sequence $$$a_1, \dots, a_L$$$, where each $$$a_i$$$ is a multiset of positive integers. Initially, the sequence is empty, i.e. $$$L=0$$$. Implement the following operations:

  • 1 M K: Add a multiset consisting of only the number $$$M$$$ appearing $$$K$$$ times to the end of the sequence.
  • 2 X Y: Add the sum of $$$a_X$$$ and $$$a_Y$$$ to the end of the sequence. The number of occurrences of each value adds; for example, we define the sum of multisets $$$\{1, 1, 2\}$$$ and $$$\{1, 2\}$$$ to be $$$\{1, 1, 1, 2, 2\}$$$.
  • 3 X M K: Add $$$f(a_X,M,K)$$$ to the end of the sequence, where $$$f(S,M,K)$$$ is formed by removing $$$K$$$ copies of $$$M$$$ from $$$S$$$ if $$$S$$$ has at least $$$K$$$ copies of $$$M$$$, or adding $$$K$$$ copies of $$$M$$$ to $$$S$$$ if $$$S$$$ has strictly fewer than $$$K$$$ copies of $$$M$$$.
  • 4 X: It is guaranteed that $$$a_X$$$ consists of a single element. Output this single element of $$$a_X$$$.
Input

The first line of input contains a single integer $$$Q$$$ ($$$1 \le Q \le 5 \cdot 10^5$$$), the number of operations.

The next $$$Q$$$ lines contain one operation each.

It is guaranteed that:

  • The indices $$$X$$$ and $$$Y$$$ used in operations $$$2$$$, $$$3$$$, and $$$4$$$ always remain within the sequence at the time of the operation.
  • The values $$$M$$$ and $$$K$$$ used in operation $$$1$$$ and $$$3$$$ satisfy $$$1 \le M,K \le 10^9$$$.
  • For all type $$$4$$$ operations, $$$a_X$$$ contains exactly one element.
Output

For each type $$$4$$$ operation, output a line with the answer.

Scoring
  • ($$$10$$$ points) $$$1 \le M \le 10$$$ for all type $$$1$$$ and $$$3$$$ operations.
  • ($$$40$$$ points) It is guaranteed that in each type $$$3$$$ operation, the newly appended multiset is formed by removing $$$K$$$ copies of $$$M$$$ from $$$a_X$$$.
  • ($$$50$$$ points) No additional constraints.
Example
Input
8
1 5 1
1 6 2
4 1
2 1 2
3 3 6 4
3 4 6 5
3 5 5 1
4 6
Output
5
6
Note

The multisets are as follows:

  • $$$a_1 = \{5\}$$$.
  • $$$a_2 = \{6, 6\}$$$.
  • $$$a_3 = \{5, 6, 6\}$$$.
  • $$$a_4 = \{5, 6, 6, 6, 6, 6, 6\}$$$.
  • $$$a_5 = \{5, 6\}$$$.
  • $$$a_6 = \{6\}$$$.