Problem10589--ABC356 —— F - Distance Component Size Query

10589: ABC356 —— F - Distance Component Size Query

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

You are given an integer $K$. For a set $S$ that is initially empty, process $Q$ queries of the following two types in order:

-   `1 x`: An integer $x$ is given. If $x$ is in $S$, remove $x$ from $S$. Otherwise, add $x$ to $S$.
-   `2 x`: An integer $x$ that is in $S$ is given. Consider a graph where the vertices are the numbers in $S$, and there is an edge between two numbers if and only if the absolute difference between them is at most $K$. Print the count of vertices in the connected component that contains $x$.

Input

The input is given from Standard Input in the following format:

```
$Q$ $K$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$
```

Each query is given in the following format:

```
$1$ $x$
```
```
$2$ $x$
```

Output

Process the queries.

Constraints

-   $1 \leq Q \leq 2\times 10^5$
-   $0 \leq K \leq 10^{18}$
-   For each query, $1 \leq x \leq 10^{18}$.
-   For each query of the second type, the given $x$ is in $S$ at that point.
-   All input values are integers.

Sample 1 Input

7 5
1 3
1 10
2 3
1 7
2 3
1 10
2 3

Sample 1 Output

1
3
2

The query processing proceeds as follows:

  • In the first query, $3$ is added to $S$, resulting in $S=\{3\}$.
  • In the second query, $10$ is added to $S$, resulting in $S=\{3,10\}$.
  • In the third query, consider a graph with vertices $3$ and $10$ and no edges. The connected component containing $3$ has a size of $1$, so print $1$.
  • In the fourth query, $7$ is added to $S$, resulting in $S=\{3,7,10\}$.
  • In the fifth query, consider a graph with vertices $3$, $7$, and $10$, with edges between $3$ and $7$, and $7$ and $10$. The connected component containing $3$ has a size of $3$, so print $3$.
  • In the sixth query, $10$ is removed from $S$, resulting in $S=\{3,7\}$.
  • In the seventh query, consider a graph with vertices $3$ and $7$, with an edge between them. The connected component containing $3$ has a size of $2$, so print $2$.

Sample 2 Input

11 1000000000000000000
1 1
1 100
1 10000
1 1000000
1 100000000
1 10000000000
1 1000000000000
1 100000000000000
1 10000000000000000
1 1000000000000000000
2 1

Sample 2 Output

10

Sample 3 Input

8 0
1 1
1 2
2 1
1 1
1 2
1 1
1 2
2 1

Sample 3 Output

1
1

Source/Category