BOX

AtCoder

IDabc279_f

Time2000ms

Memory256MB

Difficulty—

There are $N$ boxes numbered $1,2,\ldots,N$, and $10^{100}$ balls numbered $1,2,\dots,10^{100}$. Initially, box $i$ contains just ball $i$. Process a total of $Q$ operations that will be performed. There are three types of operations: $1$, $2$, and $3$. Type $1$: Put all contents of box $Y$ into box $X$. It is guaranteed that $X \neq Y$. 1 $X$ $Y$ Type $2$: Put ball $k+1$ into box $X$, where $k$ is the current total number of balls contained in the boxes. 2 $X$ Type $3$: Report the number of the box that contains ball $X$. 3 $X$ ## Constraints * All values in the input are integers. * $2 \le N \le 3 \times 10^5$ * $1 \le Q \le 3 \times 10^5$ * For each type-$1$ operation, $1 \le X,Y \le N$ and $X \neq Y$. * For each type-$2$ operation, $1 \le X \le N$. * For each type-$3$ operation, ball $X$ is contained in some box at that point. * There is at least one type-$3$ operation. ## Input The input is given from Standard Input in the following format. Here, $op_i$ represents the $i$\-th operation. $N$ $Q$ $op_1$ $op_2$ $\vdots$ $op_Q$ [samples]

Samples

Input #1

Output #1

5
4
3
1
3

This input contains ten operations.

*   The first operation is of type $3$. Ball $5$ is in box $5$.
*   The second operation is of type $1$. Put all contents of box $4$ into box $1$.
    *   Box $1$ now contains balls $1$ and $4$, and box $4$ is now empty.
*   The third operation is of type $2$. Put ball $6$ into box $1$.
*   The fourth operation is of type $2$. Put ball $7$ into box $4$.
*   The fifth operation is of type $3$. Ball $7$ is in box $4$.
*   The sixth operation is of type $1$. Put all contents of box $1$ into box $3$.
    *   Box $3$ now contains balls $1$, $3$, $4$, and $6$, and box $1$ is now empty.
*   The seventh operation is of type $3$. Ball $4$ is in box $3$.
*   The eighth operation is of type $1$. Put all contents of box $4$ into box $1$.
    *   Box $1$ now contains ball $7$, and box $4$ is now empty.
*   The ninth operation is of type $3$. Ball $7$ is in box $1$.
*   The tenth operation is of type $3$. Ball $6$ is in box $3$.

API Response (JSON)

{
  "problem": {
    "name": "BOX",
    "description": {
      "content": "There are $N$ boxes numbered $1,2,\\ldots,N$, and $10^{100}$ balls numbered $1,2,\\dots,10^{100}$. Initially, box $i$ contains just ball $i$. Process a total of $Q$ operations that will be performed. Th",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc279_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ boxes numbered $1,2,\\ldots,N$, and $10^{100}$ balls numbered $1,2,\\dots,10^{100}$. Initially, box $i$ contains just ball $i$.\nProcess a total of $Q$ operations that will be performed.\nTh...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments