You are given $N$ gears numbered $1$ through $N$. For each valid $i$, gear $i$ has $A_i$ teeth. In the beginning, no gear is connected to any other. Your task is to process $M$ queries and simulate the gears' mechanism. There are three types of queries:
- Type 1: Change the number of teeth of gear $X$ to $C$.
- Type 2: Connect two gears $X$ and $Y$.
- Type 3: Find the speed of rotation of gear $Y$ if gear $X$ rotates with speed $V$.
It is known that if gear $i$ is directly connected to gear $j$ and gear $i$ rotates with speed $V$, then gear $j$ will rotate with speed $-V A_i / A_j$, where the sign of rotation speed denotes the direction of rotation (so minus here denotes rotation in the opposite direction). You may also notice that gears can be blocked in some cases. This happens when some gear would have to rotate in different directions. If a gear is connected to any blocked gear, it is also blocked. For example, if three gears are connected to each other, this configuration can not rotate at all, and if we connect a fourth gear to these three, it will also be blocked and not rotate.

-----Input-----
- The first line of the input contains two space-separated integers $N$ and $M$.
- The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$.
- The following $M$ lines describe queries. Each of these lines begins with an integer $T$ denoting the type of the current query.
- If $T = 1$, it is followed by a space and two space-separated integers $X$ and $C$.
- If $T = 2$, it is followed by a space and two space-separated integers $X$ and $Y$.
- If $T = 3$, it is followed by a space and three space-separated integers $X$, $Y$ and $V$.

-----Output-----
For each query of type 3, print a single line containing two integers separated by a slash '/' — the numerator and denominator of the rotation speed of the given gear expressed as an irreducible fraction (even if this speed is an integer), or $0$ if the gear does not rotate at all.

-----Constraints-----
- $1 \le N \le 10^5$
- $1 \le M \le 2\cdot 10^5$
- $6 \le A_i \le 10^6$ for each valid $i$
- $1 \le X, Y \le N$
- $1 \le C, V \le 10^6$

-----Subtasks-----
Subtask #1 (30 points):
- $N \le 2,000$
- $M \le 5,000$
Subtask #2 (70 points): original constraints

-----Example Input-----
4 10
6 8 10 13
3 1 2 2
2 1 2
3 1 2 3
2 2 3
1 1 7
3 1 3 10
2 3 1
3 1 3 2
2 1 4
3 1 4 6

-----Example Output-----
0
-9/4
7/1
0
0

-----Explanation-----
For the first query of type 3, there are no connections between gears, so the answer is $0$.
For the second query of type 3, we can calculate the rotation speed using the formula $-3\cdot\frac{6}{8} = \frac{-9}{4}$.
For the third query of type 3, we can use the formula twice, so the speed of the second gear is $-10\cdot\frac{7}{8} = -\frac{35}{4}$, and the speed of the third gear is $-(-\frac{35}{4})\frac{8}{10} = \frac{7}{1}$.
For the last query of type 3, all gears are blocked.

Difficulty: interview

Starter code:

Solutions:
class Dsu:
    def __init__(self, v, s):
        self.par = s
        self.v = v
        self.dr = [1] * v
        self.zero = [False] * v
        self.speed = []
        for i in range(v):
            self.speed.append([])
            self.speed[i].append(i)

    def find(self, i):
    #     if parent[i] == -1:
    #         return i
    #     else: return self.find_parent(parent, parent[i])
        if i != self.par[i][0]:
            org = self.par[i][0]
            self.par[i][0] = self.find(self.par[i][0])
            if self.zero[i] or self.zero[self.par[i][0]] or self.zero[org]:
                self.zero[i] = self.zero[self.par[i][0]] = self.zero[org] = True
            if org != self.par[i][0]:
                self.speed[self.par[i][0]].append(i)
        return self.par[i][0]

    def union(self, x, y):
        # def union(self, parent, x, y):
        #     x_set = self.find_parent(parent, x)
        #     y_set = self.find_parent(parent, y)
        #     parent[x_set] = y_set
        self.rx = self.find(x)
        self.ry = self.find(y)
        self.sign = -self.dr[x] * self.dr[y]
        if self.rx != self.ry:
            if (self.par[self.rx][1]<self.par[self.ry][1]):
                mx=self.ry
                mn=self.rx
            if (self.par[self.rx][1]>self.par[self.ry][1]):
                mx=self.rx
                mn=self.ry
            if self.par[self.rx][1] != self.par[self.ry][1]:
                self.par[mn][0] = mx
                if self.zero[mn] or self.zero[mx] or self.zero[x] or self.zero[y]:
                    self.zero[mn] = self.zero[mx] = self.zero[x] = self.zero[y] = True
                else:
                    for i in range(len(self.speed[mn])):
                        self.dr[self.speed[mn][i]] *= self.sign
                        org = self.par[self.speed[mn][i]][0]
                        if org != mx:
                            self.par[self.speed[mn][i]][0] = mx
                            self.speed[mx].append(self.speed[mn][i])
                self.speed[mx].append(mn)

            else:
                self.par[self.ry][0] = self.rx
                self.par[self.rx][1] += 1
                if self.zero[self.rx] or self.zero[self.ry] or self.zero[x] or self.zero[y]:
                    self.zero[self.rx] = self.zero[self.ry] = self.zero[x] = self.zero[y] = True
                else:
                    for i in range(len(self.speed[self.ry])):
                        self.dr[self.speed[self.ry][i]] *= self.sign
                        org = self.par[self.speed[self.ry][i]][0]
                        if org != self.rx:
                            self.par[self.speed[self.ry][i]][0] = self.rx
                            self.speed[self.rx].append(self.speed[self.ry][i])
                self.speed[self.rx].append(self.ry)
        else:
            return


def optwo(x, y, D):
    if (D.find(x) == D.find(y) and D.dr[x] == D.dr[y]):
            D.zero[x] = D.zero[y] = True
    D.union(x, y)


def gcd(a, b):
    if a == 0:
        return b
    else:
        return gcd(b % a, a)


def opthree(x, y, v, D):
    if (D.find(x) != D.find(y)) or (D.zero[D.par[y][0]]):
        print(0)
    else:
        g = gcd(v * speed[x], speed[y])
        flag=(D.dr[x] * D.dr[y])//abs(D.dr[x] * D.dr[y])
        print(str(flag * v * speed[x] // g) + "/" + str(speed[y] // g))


n, M = map(int, input().split())
speed = list(map(int, input().split()))
s = []
for i in range(n):
    s.append([i, 0])
D = Dsu(n, s)
for i in range(M):
    T = list(map(int, input().split()))
    if (T[0] == 1):
        speed[T[1] - 1] = T[2]
    elif (T[0] == 2):
        optwo(T[1] - 1, T[2] - 1, D)
    elif (T[0] == 3):
        opthree(T[1] - 1, T[2] - 1, T[3], D)