```go
package main

import (
	"io"
	"os"
)

var buf []byte
var bufIdx, bufLen int

func nextInt() int {
	for bufIdx < bufLen && buf[bufIdx] <= 32 {
		bufIdx++
	}
	if bufIdx >= bufLen {
		return 0
	}
	res := 0
	for bufIdx < bufLen && buf[bufIdx] > 32 {
		res = res*10 + int(buf[bufIdx]-'0')
		bufIdx++
	}
	return res
}

type Node struct {
	key      int
	comp     int
	priority uint32
	left     *Node
	right    *Node
}

var nodePool []Node
var nodeCount int

func newNode(key, comp int) *Node {
	n := &nodePool[nodeCount]
	nodeCount++
	n.key = key
	n.comp = comp
	n.priority = fastRand()
	return n
}

var seed uint32 = 123456789

func fastRand() uint32 {
	seed ^= seed << 13
	seed ^= seed >> 17
	seed ^= seed << 5
	return seed
}

func split(root *Node, key int) (*Node, *Node) {
	if root == nil {
		return nil, nil
	}
	if root.key <= key {
		left, right := split(root.right, key)
		root.right = left
		return root, right
	} else {
		left, right := split(root.left, key)
		root.left = right
		return left, root
	}
}

func merge(left, right *Node) *Node {
	if left == nil {
		return right
	}
	if right == nil {
		return left
	}
	if left.priority > right.priority {
		left.right = merge(left.right, right)
		return left
	} else {
		right.left = merge(left, right.left)
		return right
	}
}

var parent []int
var val []int
var size []int

func newComp(v int) int {
	id := len(parent)
	parent = append(parent, id)
	val = append(val, v)
	size = append(size, 1)
	return id
}

func find(i int) int {
	root := i
	for root != parent[root] {
		root = parent[root]
	}
	curr := i
	for curr != root {
		nxt := parent[curr]
		parent[curr] = root
		curr = nxt
	}
	return root
}

func union(i, j int) int {
	rootI := find(i)
	rootJ := find(j)
	if rootI != rootJ {
		if size[rootI] < size[rootJ] {
			rootI, rootJ = rootJ, rootI
		}
		parent[rootJ] = rootI
		size[rootI] += size[rootJ]
		return rootI
	}
	return rootI
}

func insert(root *Node, key, comp int) *Node {
	L, R := split(root, key)
	L1, L2 := split(L, key-1)
	if L2 != nil {
		L2.comp = union(L2.comp, comp)
		val[find(L2.comp)] = key
	} else {
		L2 = newNode(key, comp)
		val[find(comp)] = key
	}
	return merge(merge(L1, L2), R)
}

var stack []*Node

func getComp(T *Node) int {
	stack = stack[:0]
	stack = append(stack, T)
	first := true
	var C int
	for len(stack) > 0 {
		n := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if first {
			C = n.comp
			first = false
		} else {
			C = union(C, n.comp)
		}
		if n.left != nil {
			stack = append(stack, n.left)
		}
		if n.right != nil {
			stack = append(stack, n.right)
		}
	}
	return C
}

func main() {
	buf, _ = io.ReadAll(os.Stdin)
	bufLen = len(buf)

	nodePool = make([]Node, 2000005)
	parent = make([]int, 0, 800005)
	val = make([]int, 0, 800005)
	size = make([]int, 0, 800005)
	stack = make([]*Node, 0, 1024)

	n := nextInt()
	if n == 0 {
		return
	}

	b_id := make([]int, n+1)
	var root *Node

	for i := 1; i <= n; i++ {
		A_i := nextInt()
		e := newComp(A_i)
		b_id[i] = e
		root = insert(root, A_i, e)
	}

	q := nextInt()
	out := make([]byte, 0, 1024*1024)
	var tmp [20]byte

	for i := 0; i < q; i++ {
		typ := nextInt()
		if typ == 1 {
			k := nextInt()
			w := nextInt()
			e := newComp(w)
			b_id[k] = e
			root = insert(root, w, e)
		} else if typ == 2 {
			k := nextInt()
			ans := val[find(b_id[k])]
			idx := 20
			if ans == 0 {
				out = append(out, '0', '\n')
			} else {
				for ans > 0 {
					idx--
					tmp[idx] = byte(ans%10 + '0')
					ans /= 10
				}
				out = append(out, tmp[idx:]...)
				out = append(out, '\n')
			}
		} else if typ == 3 {
			l := nextInt()
			r := nextInt()
			mid_floor := (l + r) / 2

			T1, T234 := split(root, l-1)
			T2, T34 := split(T234, mid_floor)
			T3, T4 := split(T34, r)

			if T2 != nil {
				C2 := getComp(T2)
				val[find(C2)] = l - 1

				T1A, T1B := split(T1, l-2)
				if T1B != nil {
					T1B.comp = union(T1B.comp, C2)
					val[find(T1B.comp)] = l - 1
				} else {
					T1B = newNode(l-1, C2)
					val[find(C2)] = l - 1
				}
				T1 = merge(T1A, T1B)
			}

			if T3 != nil {
				C3 := getComp(T3)
				val[find(C3)] = r + 1

				T4A, T4B := split(T4, r+1)
				if T4A != nil {
					T4A.comp = union(T4A.comp, C3)
					val[find(T4A.comp)] = r + 1
				} else {
					T4A = newNode(r+1, C3)
					val[find(C3)] = r + 1
				}
				T4 = merge(T4A, T4B)
			}

			root = merge(T1, T4)
		}
	}
	os.Stdout.Write(out)
}
```