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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'class Dsu:\n    def __init__(self, v, s):\n        self.par = s\n        self.v = v\n        self.dr = [1] * v\n        self.zero = [False] * v\n        self.speed = []\n        for i in range(v):\n            self.speed.append([])\n            self.speed[i].append(i)\n\n    def find(self, i):\n    #     if parent[i] == -1:\n    #         return i\n    #     else: return self.find_parent(parent, parent[i])\n        if i != self.par[i][0]:\n            org = self.par[i][0]\n            self.par[i][0] = self.find(self.par[i][0])\n            if self.zero[i] or self.zero[self.par[i][0]] or self.zero[org]:\n                self.zero[i] = self.zero[self.par[i][0]] = self.zero[org] = True\n            if org != self.par[i][0]:\n                self.speed[self.par[i][0]].append(i)\n        return self.par[i][0]\n\n    def union(self, x, y):\n        # def union(self, parent, x, y):\n        #     x_set = self.find_parent(parent, x)\n        #     y_set = self.find_parent(parent, y)\n        #     parent[x_set] = y_set\n        self.rx = self.find(x)\n        self.ry = self.find(y)\n        self.sign = -self.dr[x] * self.dr[y]\n        if self.rx != self.ry:\n            if (self.par[self.rx][1]<self.par[self.ry][1]):\n                mx=self.ry\n                mn=self.rx\n            if (self.par[self.rx][1]>self.par[self.ry][1]):\n                mx=self.rx\n                mn=self.ry\n            if self.par[self.rx][1] != self.par[self.ry][1]:\n                self.par[mn][0] = mx\n                if self.zero[mn] or self.zero[mx] or self.zero[x] or self.zero[y]:\n                    self.zero[mn] = self.zero[mx] = self.zero[x] = self.zero[y] = True\n                else:\n                    for i in range(len(self.speed[mn])):\n                        self.dr[self.speed[mn][i]] *= self.sign\n                        org = self.par[self.speed[mn][i]][0]\n                        if org != mx:\n                            self.par[self.speed[mn][i]][0] = mx\n                            self.speed[mx].append(self.speed[mn][i])\n                self.speed[mx].append(mn)\n\n            else:\n                self.par[self.ry][0] = self.rx\n                self.par[self.rx][1] += 1\n                if self.zero[self.rx] or self.zero[self.ry] or self.zero[x] or self.zero[y]:\n                    self.zero[self.rx] = self.zero[self.ry] = self.zero[x] = self.zero[y] = True\n                else:\n                    for i in range(len(self.speed[self.ry])):\n                        self.dr[self.speed[self.ry][i]] *= self.sign\n                        org = self.par[self.speed[self.ry][i]][0]\n                        if org != self.rx:\n                            self.par[self.speed[self.ry][i]][0] = self.rx\n                            self.speed[self.rx].append(self.speed[self.ry][i])\n                self.speed[self.rx].append(self.ry)\n        else:\n            return\n\n\ndef optwo(x, y, D):\n    if (D.find(x) == D.find(y) and D.dr[x] == D.dr[y]):\n            D.zero[x] = D.zero[y] = True\n    D.union(x, y)\n\n\ndef gcd(a, b):\n    if a == 0:\n        return b\n    else:\n        return gcd(b % a, a)\n\n\ndef opthree(x, y, v, D):\n    if (D.find(x) != D.find(y)) or (D.zero[D.par[y][0]]):\n        print(0)\n    else:\n        g = gcd(v * speed[x], speed[y])\n        flag=(D.dr[x] * D.dr[y])//abs(D.dr[x] * D.dr[y])\n        print(str(flag * v * speed[x] // g) + "/" + str(speed[y] // g))\n\n\nn, M = map(int, input().split())\nspeed = list(map(int, input().split()))\ns = []\nfor i in range(n):\n    s.append([i, 0])\nD = Dsu(n, s)\nfor i in range(M):\n    T = list(map(int, input().split()))\n    if (T[0] == 1):\n        speed[T[1] - 1] = T[2]\n    elif (T[0] == 2):\n        optwo(T[1] - 1, T[2] - 1, D)\n    elif (T[0] == 3):\n        opthree(T[1] - 1, T[2] - 1, T[3], D)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17049