Background

upd 2023.1.22: Added one set of hack testdata by

Bessie, far away in Moo-lica, also wants to visit friends and relatives during the Spring Festival. To kill time, she often plays an interesting number game with Farmer John.

Problem Description

Farmer John has a set $S$, initially $\\{2,3,4,\\ldots,N\\}$.

For two positive integers $p, q$ in the set $S$, we call them "a pair of good numbers" if and only if $p^k = q \\ (k\\ge 2 \\land k\\in\\N)$.

We treat each number in $S$ as a node in an undirected graph. For each pair of "good numbers", we add an undirected edge between these two numbers.

Farmer John will perform $Q$ operations of the following two types:

1. Given $x$, ask for the size of the connected component containing node $x$.
2. Given $x$, remove $x$ from $S$. At the same time, node $x$ in the undirected graph is also removed.

Since Bessie is too slow, she wants you to help.

Input Format

The first line contains two positive integers $N, Q$.

The next $Q$ lines each contain two positive integers $op_i, x_i$. Here, $op_i$ denotes the type of the operation.

It is guaranteed that $x_i$ is in the set $S$.

Output Format

For each operation of type $1$, output one positive integer per line, which is the answer to the query.

30 6
1 6
1 4
2 9
1 3
2 2
1 16

1
4
2
2

Hint

Sample Explanation

This is the original undirected graph (all nodes in the top row are isolated nodes):

This is the undirected graph after the first type $2$ operation (node $9$ is deleted):

This is the undirected graph after the second type $2$ operation (node $2$ is deleted):

Constraints

All testdata satisfy:

• $2\\le N \\le 10^{18}$
• $1\\le Q \\le 10^6$
• $x_i\\in S$
• $op_i \\in \\{1,2\\}$

Test points $1\\sim 2$ additionally satisfy $2\\le N \\le 10^5$, $1\\le Q \\le 10^4$.

Test points $3\\sim 4$ additionally satisfy that all $x_i = m^{p_i}$, where $m$ is a constant satisfying $m\\ge 2 \\land m\\in \\N$.

Test points $5\\sim 10$ have no additional constraints.

Translated by ChatGPT 5