Background

"Why are you crying?"

"Because what I expected is far from reality."

"Can crying change anything?"

"Nothing. Just like the past, which has already become a fact."

"Then why not wipe away your tears and move forward?"

"... I am waiting for my soul to catch up with time."

After night

长夜之后

In boundless light

无垠光中

He calls my name

他呼唤着我

I do the same

我望向彼方，回应

Problem Description

"Things you don't want to remember—just stop thinking about them. To distract you, I happen to have a problem related to human emotions. Want to take a look?"

"... This really makes me want to complain. What, is that person controlling everything again?"

"What? How unpleasant... Didn't you used to be very enthusiastic about this kind of thing?"

"... Not sure."

"Ahem... Then listen carefully. There are currently $n$ people, and each person has an emotion value, represented by a real number $v_i$. Now, due to some special changes, these people's emotions have become entangled..."

"Hmm?"

"The first type of entanglement has four parameters $a,b,c,d$, meaning: it is now known that there exist infinitely many $f:\R\rightarrow\R$ such that $\frac{f(v_a)}{f(v_b)}=\frac{v_c}{v_d}$."

"Wait, wait, wait! How are you even saying this math formula out loud?! And what does $f:\R\rightarrow\R$ mean?!"

"See? Didn't you say it too?"

"... Damn, so it really is you, that person..."

"Simply put, $f:\R\rightarrow\R$ means a function whose domain and codomain are both real numbers. If you still can't understand this, I have to start doubting whether you're really a high school student..."

"Fine... Go on."

"The second type of entanglement has two parameters $a,b$, meaning: it is now known that there exist finitely many $f:\R\rightarrow\R$ such that $f(v_a)\ne f(v_b)$."

"What do you mean by 'finitely many'?"

"It means there is an exact number... As long as there exists a natural number $k$ that can represent the number of such functions, then we call it 'there exist finitely many functions,' okay?"

"Hmm..."

"Next, as the entanglement keeps increasing, you also need to answer some questions. The first is: given $a,b$, you need to determine whether $v_a$ is always equal to $v_b$. The second is: given $a$, you need to compute how many $b$ ($1\le b\le n$, and $b$ can be equal to $a$) make $v_a=v_b$ always hold."

"... I understand the problem, but what does this have to do with human emotions?"

"Haha... I just wanted to cheer you up. Don't be so serious."

"... Boring."

Brief Statement

There are $n$ positive real variables $v_1,\dots,v_n$. You need to make judgments based on the currently known conditions. Each time, you are given one of the following two types of conditions:

• Given constants $a,b,c,d$: it means it is now known that there exist infinitely many $f:\R\rightarrow\R$ such that $\frac{f(v_a)}{f(v_b)}=\frac{v_c}{v_d}$.

• Given constants $a,b$: it means it is now known that there exist finitely many $f:\R\rightarrow\R$ such that $f(v_a)\ne f(v_b)$.

Or one of the following two types of queries:

• Given constants $a,b$: ask whether $v_a=v_b$ always holds.

• Given constant $a$: ask how many $b$ ($1\le b\le n$, and $b$ can be equal to $a$) make $v_a=v_b$ always hold.

Input Format

The first line contains two positive integers $n,m$, representing the number of variables and the number of operations.

The next $m$ lines each describe one operation. There are four possible types:

• 1 a b c d: it means it is now known that there exist infinitely many $f:\R\rightarrow\R$ such that $\frac{f(v_a)}{f(v_b)}=\frac{v_c}{v_d}$.

• 2 a b: it means it is now known that there exist finitely many $f:\R\rightarrow\R$ such that $f(v_a)\ne f(v_b)$.

• 3 a b: query whether $v_a=v_b$ always holds.

• 4 a: query how many $b$ ($1\le b\le n$, and $b$ can be equal to $a$) make $v_a=v_b$ always hold.

Output Format

For each operation of type 3, output one line with the string entangled if $v_a=v_b$ always holds; otherwise output one line with the string separate.

For each operation of type 4, output one line with one integer, representing the number of $b$ that satisfy the condition.

2 2
2 1 2
3 1 2

entangled

5 7
1 1 2 3 4
3 1 2
2 1 2
3 1 2
3 3 4
4 1
4 2

separate
entangled
entangled
2
2

7 6
1 1 2 3 4
1 3 5 6 7
2 4 5
3 6 7
2 1 2
3 6 7

separate
entangled

Hint

For all testdata, $1\le n,m\le 6\times 10^5$. It is guaranteed that in operation type 1, $a\ne b$ and $c\ne d$; in operation type 2, $a\ne b$; in operation type 3, $a\ne b$.

Subtask 1 (5 pts): it is guaranteed that operations of type 1 and type 2 do not appear.

Subtask 2 (10 pts): it is guaranteed that operations of type 1 do not appear.

Subtask 3 (35 pts): it is guaranteed that $n\le 5000$.

Subtask 4 (50 pts): no special restrictions.

Translated by ChatGPT 5