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: HARD
Tags: Spanning trees

Graph algorithms

Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
(N, M) = map(int, input().split())
(*A,) = map(int, input().split())

def gcd(m, n):
	r = m % n
	return gcd(n, r) if r else n
blk = [0] * N
F = [0] * N
(*p,) = range(N)

def root(x):
	if p[x] == x:
		return x
	z = p[x]
	p[x] = y = root(p[x])
	if F[z]:
		F[x] ^= 1
		A[x] = -A[x]
	return y

def unite(x, y):
	px = root(x)
	py = root(y)
	if px < py:
		if blk[py]:
			blk[px] = 1
		assert A[py] >= 0 and F[py] == 0
		if A[x] * A[y] >= 0:
			A[py] = -A[py]
			F[py] ^= 1
		p[py] = px
	else:
		if blk[px]:
			blk[py] = 1
		assert A[px] >= 0 and F[px] == 0
		if A[x] * A[y] >= 0:
			A[px] = -A[px]
			F[px] ^= 1
		p[px] = py
ans = []
for i in range(M):
	(T, *CS) = map(int, input().split())
	if T == 1:
		(X, C) = CS
		X -= 1
		if A[X] >= 0:
			A[X] = C
		else:
			A[X] = -C
	elif T == 2:
		(X, Y) = CS
		X -= 1
		Y -= 1
		if root(X) == root(Y):
			if A[X] * A[Y] >= 0:
				blk[root(X)] = 1
		else:
			unite(X, Y)
	else:
		(X, Y, V) = CS
		X -= 1
		Y -= 1
		if root(X) != root(Y):
			ans.append('0')
			continue
		if blk[root(X)]:
			ans.append('0')
			continue
		root(X)
		root(Y)
		a = A[X] * V
		b = A[Y]
		if b < 0:
			a = -a
			b = -b
		g = gcd(abs(a), abs(b))
		ans.append('%d/%d' % (a // g, b // g))
print(*ans, sep='\n')


class disjointsets:

	def __init__(self, n):
		self.arr = [0] * n
		self.size = [1] * n
		for i in range(n):
			self.arr[i] = i

	def find(self, i):
		if self.arr[i] == i:
			return i
		else:
			self.arr[i] = self.find(self.arr[i])
			return self.arr[i]

	def union(self, i, j):
		f1 = self.find(i)
		f2 = self.find(j)
		if f1 == f2:
			return
		elif self.size[f1] > self.size[f2]:
			self.arr[f2] = f1
			self.size[f1] += self.size[f2]
		else:
			self.arr[f1] = f2
			self.size[f2] += self.size[f1]

def gcd(a, b):
	if a < b:
		temp = a
		a = b
		b = temp
	while b > 0:
		r = a % b
		a = b
		b = r
	return a
a = [int(i) for i in input().split()]
n = a[0]
m = a[1]
d1 = disjointsets(n)
d2 = disjointsets(n)
flag = [0] * n
arr = [-1] * n
colorarr = [0] * n
teeth = [int(i) for i in input().split()]
for i in range(m):
	a = [int(i) for i in input().split()]
	if a[0] == 1:
		teeth[a[1] - 1] = a[2]
	elif a[0] == 2:
		f1 = d1.find(a[1] - 1)
		f2 = d1.find(a[2] - 1)
		if f1 == f2:
			c1 = d2.find(a[1] - 1)
			c2 = d2.find(a[2] - 1)
			x = a[1] - 1
			y = a[2] - 1
			if c1 == c2:
				flag[f1] = 1
		else:
			fl1 = flag[f1]
			fl2 = flag[f2]
			x = a[1] - 1
			y = a[2] - 1
			neighx = arr[x]
			neighy = arr[y]
			d1.union(x, y)
			if neighx == neighy and neighx == -1:
				colorarr[x] = 1
				colorarr[y] = 2
			elif neighx == -1:
				c = colorarr[d2.find(neighy)]
				d2.union(x, neighy)
				colorarr[d2.find(x)] = c
			elif neighy == -1:
				c = colorarr[d2.find(neighx)]
				d2.union(neighx, y)
				colorarr[d2.find(y)] = c
			else:
				c1 = colorarr[d2.find(neighx)]
				c2 = colorarr[d2.find(neighy)]
				d2.union(neighx, y)
				d2.union(neighy, x)
				colorarr[d2.find(x)] = c2
				colorarr[d2.find(y)] = c1
			arr[x] = y
			arr[y] = x
			if fl1 == 1 or fl2 == 1:
				flag[d1.find(x)] = 1
	else:
		p = teeth[a[1] - 1] * a[3]
		q = teeth[a[2] - 1]
		g = gcd(p, q)
		p = p // g
		q = q // g
		f1 = d1.find(a[1] - 1)
		f2 = d1.find(a[2] - 1)
		if f1 == f2 and flag[f1] != 1:
			c1 = d2.find(a[1] - 1)
			c2 = d2.find(a[2] - 1)
			s = str(p) + '/' + str(q)
			if c1 == c2:
				print(s)
			else:
				print('-' + s)
		else:
			print(0)


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

def dsfind(parent, i):
	if parent[i] == i:
		return i
	return dsfind(parent, parent[i])

def dsunion(parent, rank, x, y, chn):
	xroot = dsfind(parent, x)
	yroot = dsfind(parent, y)
	sx = dssign(parent, x, chn)
	sy = dssign(parent, y, chn)
	if rank[xroot] < rank[yroot]:
		if sx == sy:
			chn[xroot] = -1
		parent[xroot] = yroot
	elif rank[xroot] > rank[yroot]:
		if sx == sy:
			chn[yroot] = -1
		parent[yroot] = xroot
	else:
		if sx == sy:
			chn[yroot] = -1
		parent[yroot] = xroot
		rank[xroot] += 1

def dssign(parent, i, chn):
	a = 1
	while parent[i] != i:
		a *= chn[i]
		i = parent[i]
	a *= chn[i]
	return a
(n, m) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
parent = []
rank = []
block = []
chn = []
for i in range(n):
	parent.append(i)
	rank.append(0)
	block.append(0)
	chn.append(1)
for i in range(m):
	l = [int(x) for x in input().split()]
	t = l[0]
	if t == 1:
		x = l[1] - 1
		c = l[2]
		arr[x] = c
	if t == 2:
		x = l[1] - 1
		y = l[2] - 1
		xroot = dsfind(parent, x)
		yroot = dsfind(parent, y)
		if xroot == yroot:
			if block[xroot] == 0:
				d1 = dssign(parent, x, chn)
				d2 = dssign(parent, y, chn)
				if d1 == d2:
					block[xroot] = 1
			continue
		if block[xroot] == 0 and block[yroot] == 1:
			block[xroot] = 1
		if block[yroot] == 0 and block[xroot] == 1:
			block[yroot] = 1
		dsunion(parent, rank, x, y, chn)
	if t == 3:
		x = l[1] - 1
		y = l[2] - 1
		v = l[3]
		xroot = dsfind(parent, x)
		yroot = dsfind(parent, y)
		if xroot != yroot:
			print(0)
			continue
		if block[xroot] == 1:
			print(0)
			continue
		temp = gcd(v * arr[x], arr[y])
		a1 = v * arr[x] // temp
		a2 = arr[y] // temp
		d1 = dssign(parent, x, chn)
		d2 = dssign(parent, y, chn)
		if d1 == d2:
			s = str(a1) + '/' + str(a2)
			print(s)
		else:
			s = str(-a1) + '/' + str(a2)
			print(s)


import math

class Node:

	def __init__(self, k):
		self.value = k
		self.children = [self.value]
		self.parent = self
		self.rank = 0
		self.link = 0
		self.incycle = 0

class Disjoint:

	def __init__(self, n):
		self.lst = [None] * n
		for i in range(n):
			self.lst[i] = self.makeset(i)

	def makeset(self, i):
		return Node(i)

	def findset(self, x):
		if x.parent != x:
			x.parent = self.findset(x.parent)
		return x.parent

	def union(self, a, b):
		p = self.findset(self.lst[a])
		q = self.findset(self.lst[b])
		if self.lst[a].link == 0 and self.lst[b].link == 0:
			self.lst[a].link = 1
			self.lst[b].link = 2
		elif self.lst[a].link == 0:
			if self.lst[b].link == 1:
				self.lst[a].link = 2
			else:
				self.lst[a].link = 1
		elif self.lst[b].link == 0:
			if self.lst[a].link == 1:
				self.lst[b].link = 2
			else:
				self.lst[b].link = 1
		else:
			if p == q:
				if self.lst[a].link == self.lst[b].link:
					self.lst[b].parent.incycle = 1
				return
			if p.incycle == 1 or q.incycle == 1:
				self.lst[a].parent.incycle = 1
				self.lst[b].parent.incycle = 1
			elif self.lst[a].link == self.lst[b].link:
				if len(self.lst[q.value].children) < len(self.lst[p.value].children):
					for i in range(len(self.lst[q.value].children)):
						if self.lst[self.lst[q.value].children[i]].link == 1:
							self.lst[self.lst[q.value].children[i]].link = 2
						else:
							self.lst[self.lst[q.value].children[i]].link = 1
				else:
					for i in range(len(self.lst[p.value].children)):
						if self.lst[self.lst[p.value].children[i]].link == 1:
							self.lst[self.lst[p.value].children[i]].link = 2
						else:
							self.lst[self.lst[p.value].children[i]].link = 1
			else:
				count = 0
		if p.rank > q.rank:
			for i in range(len(self.lst[q.value].children)):
				self.lst[self.lst[q.value].children[i]].parent = p
				self.lst[p.value].children.append(self.lst[q.value].children[i])
		elif p.rank < q.rank:
			for i in range(len(self.lst[p.value].children)):
				self.lst[self.lst[p.value].children[i]].parent = q
				self.lst[q.value].children.append(self.lst[p.value].children[i])
		else:
			for i in range(len(self.lst[q.value].children)):
				self.lst[self.lst[q.value].children[i]].parent = p
				self.lst[p.value].children.append(self.lst[q.value].children[i])
			p.rank += 1

def test3(Z, x, y, v, teeth):
	if Z.lst[x].parent.incycle == 1 or Z.lst[y].parent.incycle == 1 or Z.lst[x].parent != Z.lst[y].parent:
		print(0)
		return
	p = int(teeth[x]) * v
	q = int(teeth[y])
	r = math.gcd(p, q)
	if Z.lst[x].link == Z.lst[y].link:
		print(int(p / r), end='')
		print('/', end='')
		print(int(q / r))
	else:
		print(int(-p / r), end='')
		print('/', end='')
		print(int(q / r))

def main():
	t = 1
	for p in range(t):
		(n, m) = input().split()
		(n, m) = (int(n), int(m))
		teeth = input().split()
		Z = Disjoint(n)
		for i in range(m):
			lst = input().split()
			if int(lst[0]) == 1:
				teeth[int(lst[1]) - 1] = int(lst[2])
			elif int(lst[0]) == 2:
				Z.union(int(lst[1]) - 1, int(lst[2]) - 1)
			else:
				test3(Z, int(lst[1]) - 1, int(lst[2]) - 1, int(lst[3]), teeth)
main()


import math
import sys

def reduceSpeed(speed):
	if speed[1] == 0:
		return
	gcd = math.gcd(speed[0], speed[1])
	speed[0] //= gcd
	speed[1] //= gcd
	if speed[1] < 0:
		(speed[0], speed[1]) = (-speed[0], -speed[1])

def calcSpeed(dest_num_teeth, source_num_teeth, source_speed):
	speed = source_speed.copy()
	speed[0] *= -source_num_teeth
	speed[1] *= dest_num_teeth
	return speed

class Gear:
	num_teeth = 0
	direction = 1
	connections = []

	def __init__(self, num_teeth):
		self.num_teeth = num_teeth
		self.direction = 1
		self.connections = [self]

	def isStopped(self):
		return self.direction == 0

class GearSet:
	gears = []

	def __init__(self, teeth):
		self.gears = [Gear(t) for (i, t) in enumerate(teeth)]

	def makeStoppedGears(connections):
		for g in connections:
			g.direction = 0

	def reverseDirections(connections):
		for g in connections:
			g.direction = -g.direction

	def mergeConnections(connections1, connections2):
		for g in connections1:
			g.connections = connections2
		connections2.extend(connections1)

	def UpdateNumTeeth(self, gear, num_teeth):
		self.gears[gear].num_teeth = num_teeth

	def addConnection(self, gear1, gear2):
		g1 = self.gears[gear1]
		g2 = self.gears[gear2]
		c1 = g1.connections
		c2 = g2.connections
		if c1 is c2:
			if g1.isStopped():
				return
			if not g1.direction == -g2.direction:
				GearSet.makeStoppedGears(c1)
			return
		if len(c1) > len(c2):
			(g1, c1, g2, c2) = (g2, c2, g1, c1)
		if g1.isStopped() or g2.isStopped():
			if not g1.isStopped():
				GearSet.makeStoppedGears(c1)
			if not g2.isStopped():
				GearSet.makeStoppedGears(c2)
		elif not g1.direction == -g2.direction:
			GearSet.reverseDirections(c1)
		GearSet.mergeConnections(c1, c2)

	def calcRotation(self, dest_gear, source_gear, source_speed):
		dg = self.gears[dest_gear]
		sg = self.gears[source_gear]
		if dg.isStopped():
			return [0, 0]
		if not dg.connections == sg.connections:
			return [0, 0]
		s = calcSpeed(dg.num_teeth, sg.num_teeth, [sg.direction * source_speed, -dg.direction])
		reduceSpeed(s)
		return s
(n, m) = map(int, input().split())
gears = [0]
gears.extend(list(map(int, input().split())))
gear_set = GearSet(gears)

def processQuery(query):
	query = list(map(int, query.split()))
	if query[0] == 1:
		gear_set.UpdateNumTeeth(query[1], query[2])
	elif query[0] == 2:
		gear_set.addConnection(query[1], query[2])
	else:
		speed = gear_set.calcRotation(query[2], query[1], query[3])
		if speed[0] == 0 or speed[1] == 0:
			print(0)
		else:
			print('%d/%d' % (speed[0], speed[1]))
list(map(processQuery, sys.stdin.readlines()))


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 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):
		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)


from fractions import Fraction
[N, M] = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
A = [0] + B[:]
p = [i for i in range(N + 1)]
rank = [0] * (N + 1)
isit = [0] * (N + 1)
rot = [True] * (N + 1)
adj = {}
for i in range(1, N + 1):
	adj[i] = []

def bfs(s, val):
	level = {s: 0}
	vd = val
	rot[s] = vd
	i = 1
	frontier = [s]
	while frontier:
		nexte = []
		vd = not vd
		for u in frontier:
			for v in adj[u]:
				if not v in level:
					level[v] = i
					rot[v] = vd
					nexte.append(v)
		frontier = nexte
		i += 1

def find_set(x):
	if x != p[x]:
		p[x] = find_set(p[x])
	return p[x]

def link(x, y):
	pX = find_set(x)
	pY = find_set(y)
	if isit[pX] == -1:
		isit[pY] = -1
	elif isit[pY] == -1:
		isit[pX] = -1
	elif pX != pY:
		if rank[pX] > rank[pY]:
			bfs(y, not rot[x])
			p[pY] = pX
		else:
			bfs(x, not rot[y])
			p[pX] = pY
		if rank[pX] == rank[pY]:
			rank[pY] += 1
		adj[x].append(y)
		adj[y].append(x)
	elif pX == pY:
		if rot[x] == rot[y]:
			isit[pX] = -1
for _ in range(M):
	T = [int(x) for x in input().split()]
	if T[0] == 1:
		A[T[1]] = T[2]
	elif T[0] == 2:
		link(T[1], T[2])
	elif T[0] == 3:
		pX = find_set(T[1])
		pY = find_set(T[2])
		if pX != pY:
			print('0')
		elif isit[pX] == -1:
			print('0')
		else:
			num = T[3] * A[T[1]]
			den = A[T[2]]
			if rot[T[1]] != rot[T[2]]:
				num *= -1
			t1 = Fraction(num, den)
			print(str(t1.numerator) + '/' + str(t1.denominator))


from math import gcd
import numpy as np

def main():
	(n, m) = [int(x) for x in input().split()]
	teeth = np.array([int(x) for x in input().split()], dtype='int32')
	group = np.zeros(n, dtype='int32')
	rotation = np.zeros(n, dtype='int32')
	group_count = 0
	groups = np.zeros(10 ** 6, dtype='int32')
	for _ in range(m):
		q = [int(x) for x in input().split()]
		if q[0] == 1:
			teeth[q[1] - 1] = q[2]
		elif q[0] == 3:
			(x, y, v) = q[1:]
			(x, y) = (x - 1, y - 1)
			ans = 0
			movable = group[x] > 0 and group[x] == group[y]
			if movable:
				numerator = teeth[x] * v
				denominator = teeth[y]
				reducer = gcd(numerator, denominator)
				numerator //= reducer
				denominator //= reducer
				ans = ''
				if rotation[x] * rotation[y] < 0:
					ans = '-'
				ans = ans + '{}/{}'.format(numerator, denominator)
			print(ans)
		elif q[0] == 2:
			(x, y) = q[1:]
			(x, y) = (x - 1, y - 1)
			if group[x] == 0 and group[y] == 0:
				group_count += 1
				groups[group_count] = 2
				group[x] = group[y] = group_count
				rotation[x] = 1
				rotation[y] = -1
			elif group[x] != 0 and group[y] != 0:
				if group[x] == group[y]:
					if rotation[x] == rotation[y]:
						temp = group[x]
						group[group == temp] = -1
				elif group[x] < 0:
					temp = group[y]
					group[group == temp] = -1
				elif group[y] < 0:
					temp = group[x]
					group[group == temp] = -1
				else:
					temp = group[y]
					temp2 = group[x]
					if groups[group[y]] > groups[group[x]]:
						(temp, temp2) = (temp2, temp)
					if rotation[x] == rotation[y]:
						rotation[group == temp] *= -1
					group[group == temp] = temp2
					groups[temp2] += groups[temp]
			elif group[x] == 0:
				group[x] = group[y]
				groups[group[y]] += 1
				rotation[x] = -rotation[y]
			elif group[y] == 0:
				group[y] = group[x]
				groups[group[x]] += 1
				rotation[y] = -rotation[x]
main()


import math

class Set_Node:

	def __init__(self, value, rank):
		self.value = value
		self.parent = self
		self.rank = rank
		self.color = None
		self.arr = [self]
		self.block = 0
		self.total = 1

class Set:

	def makeset(self, val):
		t = Set_Node(val, 0)
		return t

	def findset(self, ptr):
		if ptr == None:
			return None
		else:
			if ptr == ptr.parent:
				return ptr
			ptr.parent = self.findset(ptr.parent)
			return ptr.parent

	def union(self, ptr_x, ptr_y):
		x = self.findset(ptr_x)
		y = self.findset(ptr_y)
		if x.rank > y.rank:
			y.parent = x
			x.arr += y.arr[:]
			x.total += y.total
		elif x.rank < y.rank:
			x.parent = y
			y.arr += x.arr[:]
			y.total += x.total
		else:
			y.parent = x
			x.rank += 1
			x.arr += y.arr[:]
			x.total += y.total
S = Set()
(n, m) = map(int, input().split())
arr = [int(x) for x in input().split()]
ptr = [0] * n
for i in range(n):
	ptr[i] = S.makeset(i)
for i in range(m):
	arr2 = [int(x) for x in input().split()]
	if arr2[0] == 1:
		arr[arr2[1] - 1] = arr2[2]
	elif arr2[0] == 2:
		x = arr2[1] - 1
		y = arr2[2] - 1
		l = S.findset(ptr[x])
		m = S.findset(ptr[y])
		if l != m:
			if ptr[x].color == None and ptr[y].color == None:
				ptr[x].color = 0
				ptr[y].color = 1
				S.union(ptr[x], ptr[y])
			elif ptr[x].color == None:
				ptr[x].color = (ptr[y].color + 1) % 2
				S.union(ptr[x], ptr[y])
			elif ptr[y].color == None:
				ptr[y].color = (ptr[x].color + 1) % 2
				S.union(ptr[x], ptr[y])
			elif ptr[y].color == ptr[x].color:
				if l.total > m.total:
					for j in m.arr:
						j.color = (j.color + 1) % 2
				else:
					for j in l.arr:
						j.color = (j.color + 1) % 2
				S.union(ptr[x], ptr[y])
			else:
				S.union(ptr[x], ptr[y])
		elif ptr[x].color == ptr[y].color:
			l.block = 1
	else:
		x = arr2[1] - 1
		y = arr2[2] - 1
		v = arr2[3]
		l = S.findset(ptr[x])
		m = S.findset(ptr[y])
		if l != m or l.block == 1 or m.block == 1:
			print(0)
		else:
			num = arr[x] * v
			den = arr[y]
			g = math.gcd(num, den)
			num = num // g
			den = den // g
			if ptr[x].color != ptr[y].color:
				print('-' + str(num) + '/' + str(den))
			else:
				print(str(num) + '/' + str(den))


import math
import sys

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def union(x, y, par, node, child):
	x1 = x
	while par[x1] >= 0:
		x1 = par[x1]
	y1 = y
	while par[y1] >= 0:
		y1 = par[y1]
	if x1 == y1:
		print(1 / 0)
		sys.exit()
	if len(child[x1]) < len(child[y1]) and y1 != 0 or y1 == 0:
		smr = x1
		lgr = y1
	else:
		smr = y1
		lgr = x1
	tovisit = [smr]
	mulby = node[x] * node[y] * -1
	while len(tovisit) > 0:
		x = tovisit.pop()
		child[lgr].append(x)
		node[x] *= mulby
		tovisit += child[x]
		child[x] = []
		par[x] = lgr

def findpar(x, par, child):
	x1 = x
	if par[x] < 0:
		return x
	while par[par[x]] >= 0:
		x = par[x]
	tovisit = child[x]
	x1 = par[x]
	while len(tovisit) > 0:
		x = tovisit.pop()
		child[x1].append(x)
		tovisit += child[x]
		child[x] = []
		par[x] = x1
	return x1

def setblock(x, par, node, child):
	if findpar(x, par, child) == 0:
		return
	union(x, 0, par, node, child)
(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split()))
child = [[] for i in range(n + 1)]
par = [-math.inf] + [-1 for i in range(n)]
node = [0] + [1 for i in range(n)]
for i in range(m):
	cmd = list(map(int, input().split()))
	if cmd[0] == 1:
		a[cmd[1]] = cmd[2]
	elif cmd[0] == 2:
		if findpar(cmd[1], par, child) == findpar(cmd[2], par, child):
			if node[cmd[1]] == node[cmd[2]]:
				setblock(cmd[1], par, node, child)
		else:
			union(cmd[1], cmd[2], par, node, child)
	elif findpar(cmd[1], par, child) == findpar(cmd[2], par, child) and findpar(cmd[2], par, child) != 0:
		num = a[cmd[1]] * cmd[3]
		den = a[cmd[2]]
		gcd1 = gcd(num, den)
		num //= gcd1
		den //= gcd1
		num *= node[cmd[1]] * node[cmd[2]]
		print(str(num) + '/' + str(den))
	else:
		print(0)


import queue

def find(parent, i, distance):
	root = i
	while parent[root] != root:
		root = parent[root]
		distance[i] += distance[root]
	return root

def find2(parent, i, distance):
	root = i
	while parent[root] != root:
		root = parent[root]
	return root

def update(parent, des, distance, dis, new_parent):
	root = des
	while parent[root] != new_parent:
		root = parent[root]
		temp = distance[root]
		distance[root] = dis + distance[des]
		dis = temp
		des = root

def union(parent, size, x, y, cycle, distance, parent1, parent2):
	parent_x = parent1
	parent_y = parent2
	if parent_x != parent_y:
		if cycle[parent_x] == 1:
			size[parent_x] += size[parent_y]
			parent[parent_y] = parent_x
		elif cycle[parent_y] == 1:
			size[parent_y] += size[parent_x]
			parent[parent_x] = parent_y
		elif size[parent_x] < size[parent_y]:
			size[parent_y] += size[parent_x]
			parent[parent_x] = parent_y
		else:
			size[parent_x] += size[parent_y]
			parent[parent_y] = parent_x

def bfs(edges, visited, distance, color, source, cycle, parent, count, connections):
	q = queue.Queue(100000)
	q.put(source)
	visited[source] = count
	distance[source] = 0
	color[source] = 1
	while q.empty() == False:
		source = q.get()
		parent[source] = find(parent, source)
		c = 1
		j = 0
		while c <= connections[source]:
			if visited[edges[source][j]] != count:
				visited[edges[source][j]] = count
				distance[edges[source][j]] = distance[source] + 1
				color[edges[source][j]] = 1 - color[source]
				q.put(edges[source][j])
			elif visited[edges[source][j]] == count and color[edges[source][j]] == color[source]:
				cycle[parent[source]] = 1
				break
			j += 1
			c += 1
		if cycle[parent[source]] == 1:
			break

def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
s = list(map(int, input().split()))
n = s[0]
m = s[1]
num = input().split()
num = list(map(int, num))
edges = []
parent = []
size = []
visited = []
distance = []
color = []
cycle = []
connections = []
count = 0
for i in range(0, n + 1):
	edges.append([])
	parent.append(i)
	size.append(1)
	color.append(-1)
	visited.append(0)
	distance.append(0)
	cycle.append(0)
	connections.append(0)
i = 1
while i <= m:
	st = input().split()
	st = list(map(int, st))
	type = st[0]
	if type == 1:
		index = st[1]
		teeth = st[2]
		num[index - 1] = teeth
	elif type == 2:
		src = st[1]
		des = st[2]
		parent[src] = find(parent, src, distance)
		parent[des] = find(parent, des, distance)
		if src != des:
			if parent[src] == parent[des]:
				d1 = distance[des] - distance[src]
				if d1 % 2 == 0:
					cycle[parent[src]] = 1
			else:
				prev1 = parent[src]
				prev2 = parent[des]
				dis = distance[src]
				dis1 = distance[des]
				union(parent, size, src, des, cycle, distance, parent[src], parent[des])
				new1 = find2(parent, src, distance)
				new2 = find2(parent, des, distance)
				if new1 == prev1:
					distance[des] = distance[src] + 1
					if prev2 != des:
						update(parent, des, distance, dis1, new1)
					parent[des] = find2(parent, des, distance)
				else:
					distance[src] = distance[des] + 1
					if prev1 != src:
						update(parent, src, distance, dis, new1)
					parent[src] = find2(parent, src, distance)
	else:
		count += 1
		src = st[1]
		des = st[2]
		speed = st[3]
		parent[src] = find(parent, src, distance)
		parent[des] = find(parent, des, distance)
		if parent[src] != parent[des]:
			print(0)
		elif parent[src] == parent[des]:
			if cycle[parent[src]] == 1:
				print(0)
			else:
				d = distance[des] - distance[src]
				if cycle[parent[src]] == 1:
					print(0)
				elif d % 2 == 0:
					numerator = num[src - 1]
					denominator = num[des - 1]
					numerator *= speed
					g = gcd(numerator, denominator)
					numerator //= g
					denominator //= g
					print(str(numerator) + '/' + str(denominator))
				else:
					numerator = num[src - 1]
					denominator = num[des - 1]
					numerator *= speed
					g = gcd(numerator, denominator)
					numerator //= g
					denominator //= g
					print('-' + str(numerator) + '/' + str(denominator))
	i += 1


class Node:

	def __init__(self, i, v, p):
		self.data = i
		self.val = v
		self.parent = p

def gcd(a, b):
	if a > b:
		a = a % b
		if a == 0:
			return b
	else:
		b = b % a
		if b == 0:
			return a
	return gcd(a, b)
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
gear = [0] * (n + 1)
blocked = [0] * (n + 1)
st = [0] * (n + 1)
for i in range(n + 1):
	gear[i] = Node(i, -1, -1)
	st[i] = []
qr = [0] * 4
for i in range(m):
	qr = list(map(int, input().split()))
	if qr[0] == 1:
		arr[qr[1] - 1] = qr[2]
	elif qr[0] == 2:
		if gear[qr[1]].parent == -1 and gear[qr[2]].parent == -1:
			gear[qr[2]].parent = qr[1]
			gear[qr[2]].val = 1
			gear[qr[1]].parent = qr[1]
			gear[qr[1]].val = 0
			st[qr[1]].append(gear[qr[1]].data)
			st[qr[1]].append(gear[qr[2]].data)
		elif gear[qr[1]].parent == -1:
			gear[qr[1]].parent = gear[qr[2]].parent
			gear[qr[1]].val = 1
			if gear[qr[2]].val == 1:
				gear[qr[1]].val = 0
			st[gear[qr[2]].parent].append(gear[qr[1]].data)
		elif gear[qr[2]].parent == -1:
			gear[qr[2]].parent = gear[qr[1]].parent
			gear[qr[2]].val = 1
			if gear[qr[1]].val == 1:
				gear[qr[2]].val = 0
			st[gear[qr[1]].parent].append(gear[qr[2]].data)
		elif gear[qr[1]].parent == gear[qr[2]].parent:
			if gear[qr[2]].val == gear[qr[1]].val:
				blocked[gear[qr[1]].parent] = 1
		else:
			a = gear[qr[1]].parent
			b = gear[qr[2]].parent
			if len(st[a]) < len(st[b]):
				b = gear[qr[1]].parent
				a = gear[qr[2]].parent
			if gear[qr[1]].val == gear[qr[2]].val:
				for i in range(len(st[b])):
					if gear[st[b][i]].val == 0:
						gear[st[b][i]].val = 1
					else:
						gear[st[b][i]].val = 0
					gear[st[b][i]].parent = a
				st[a].extend(st[b])
			else:
				for i in range(len(st[b])):
					gear[st[b][i]].parent = a
				st[a].extend(st[b])
	else:
		f = gear[qr[1]]
		s = gear[qr[2]]
		if f.parent == -1 or s.parent == -1 or f.parent != s.parent or (blocked[f.parent] == 1) or (blocked[s.parent] == 1):
			print('0')
		else:
			g = gcd(qr[3] * arr[qr[1] - 1], arr[qr[2] - 1])
			if f.val != s.val:
				print('-', end='')
			print(qr[3] * arr[qr[1] - 1] // g, end='/')
			print(arr[qr[2] - 1] // g)


import sys
from collections import defaultdict as dd
from itertools import permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
mod = 10 ** 9 + 7
(n, m) = [int(i) for i in input().split()]
a = [0] + [int(i) for i in input().split()]
dis = [0 for i in range(n + 1)]

def MakeSet(x):
	x.parent = x
	x.rank = 0
	x.size = 1
	x.nouse = 0

def Union(x, y):
	xRoot = Find(x)
	yRoot = Find(y)
	if xRoot.rank > yRoot.rank:
		yRoot.parent = xRoot
		xRoot.size += yRoot.size
		xRoot.nouse = max(xRoot.nouse, yRoot.nouse)
	elif xRoot.rank < yRoot.rank:
		xRoot.parent = yRoot
		yRoot.size += xRoot.size
		yRoot.nouse = max(xRoot.nouse, yRoot.nouse)
	elif xRoot != yRoot:
		yRoot.parent = xRoot
		xRoot.size += yRoot.size
		xRoot.rank = xRoot.rank + 1
		xRoot.nouse = max(xRoot.nouse, yRoot.nouse)

def Find(x):
	if x.parent == x:
		return x
	else:
		x.parent = Find(x.parent)
		return x.parent
import itertools

class Node:

	def __init__(self, label):
		self.label = label

	def __str__(self):
		return self.label
g = [Node(str(ch)) for ch in range(n + 1)]
[MakeSet(ch) for ch in g]
graph = dd(list)
vis = [0 for i in range(n + 1)]

def changedis(s):
	rechange = [s]
	start = s
	bfs = [s]
	vis[s] = 1
	while bfs:
		k = bfs.pop(0)
		dis[k] ^= 1
		for i in graph[k]:
			if vis[i] == 0:
				bfs.append(i)
				vis[i] = 1
				rechange.append(i)
	for i in rechange:
		vis[i] = 0

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for i in range(m):
	qu = [int(i) for i in input().split()]
	(ch, x, y) = (qu[0], qu[1], qu[2])
	if ch == 1:
		a[x] = y
	if ch == 2:
		xx = Find(g[x])
		yy = Find(g[y])
		if xx == yy:
			if dis[x] != dis[y]:
				pass
			else:
				xx.nouse = 1
		else:
			Union(g[x], g[y])
			if dis[x] == dis[y]:
				if xx.size > yy.size:
					changedis(y)
				else:
					changedis(x)
		graph[x].append(y)
		graph[y].append(x)
	if ch == 3:
		v = qu[3]
		xx = Find(g[x])
		yy = Find(g[y])
		if xx != yy:
			print(0)
		elif xx.nouse == 1:
			print(0)
		else:
			num = v * a[x]
			den = a[y]
			div = gcd(num, den)
			num = num // div
			den = den // div
			if dis[x] == dis[y]:
				print(str(num) + '/' + str(den))
			else:
				print('-' + str(num) + '/' + str(den))