```go
package main
import (
"bufio"
"io"
"os"
"strconv"
)
type FastScanner struct {
data []byte
idx int
n int
}
func NewFastScanner() *FastScanner {
data, _ := io.ReadAll(os.Stdin)
return &FastScanner{data: data, n: len(data)}
}
func (fs *FastScanner) Int64() int64 {
for fs.idx < fs.n && (fs.data[fs.idx] < '0' || fs.data[fs.idx] > '9') {
fs.idx++
}
var v int64
for fs.idx < fs.n && fs.data[fs.idx] >= '0' && fs.data[fs.idx] <= '9' {
v = v*10 + int64(fs.data[fs.idx]-'0')
fs.idx++
}
return v
}
type Pair struct {
val int64
id int
}
type GPair struct {
val int64
g int
}
var (
n, q int
t []int64
wv []int64
selfv []int64
base []int64
d []int
f []int
minHs [][]Pair
maxHs [][]Pair
gMinH []GPair
gMaxH []GPair
seen []int
changed []int
stamp int
)
func calc(tv int64, deg int) (int64, int64) {
x := tv / int64(deg+2)
return x, tv - int64(deg+1)*x
}
func pushMinPair(h *[]Pair, x Pair) {
a := *h
a = append(a, x)
i := len(a) - 1
for i > 0 {
p := (i - 1) >> 1
if a[p].val <= a[i].val {
break
}
a[p], a[i] = a[i], a[p]
i = p
}
*h = a
}
func popMinPair(h *[]Pair) Pair {
a := *h
res := a[0]
nn := len(a) - 1
if nn == 0 {
*h = a[:0]
return res
}
a[0] = a[nn]
a = a[:nn]
i := 0
for {
l := i*2 + 1
if l >= nn {
break
}
r := l + 1
c := l
if r < nn && a[r].val < a[l].val {
c = r
}
if a[i].val <= a[c].val {
break
}
a[i], a[c] = a[c], a[i]
i = c
}
*h = a
return res
}
func pushMaxPair(h *[]Pair, x Pair) {
a := *h
a = append(a, x)
i := len(a) - 1
for i > 0 {
p := (i - 1) >> 1
if a[p].val >= a[i].val {
break
}
a[p], a[i] = a[i], a[p]
i = p
}
*h = a
}
func popMaxPair(h *[]Pair) Pair {
a := *h
res := a[0]
nn := len(a) - 1
if nn == 0 {
*h = a[:0]
return res
}
a[0] = a[nn]
a = a[:nn]
i := 0
for {
l := i*2 + 1
if l >= nn {
break
}
r := l + 1
c := l
if r < nn && a[r].val > a[l].val {
c = r
}
if a[i].val >= a[c].val {
break
}
a[i], a[c] = a[c], a[i]
i = c
}
*h = a
return res
}
func pushGMin(h *[]GPair, x GPair) {
a := *h
a = append(a, x)
i := len(a) - 1
for i > 0 {
p := (i - 1) >> 1
if a[p].val <= a[i].val {
break
}
a[p], a[i] = a[i], a[p]
i = p
}
*h = a
}
func popGMin(h *[]GPair) GPair {
a := *h
res := a[0]
nn := len(a) - 1
if nn == 0 {
*h = a[:0]
return res
}
a[0] = a[nn]
a = a[:nn]
i := 0
for {
l := i*2 + 1
if l >= nn {
break
}
r := l + 1
c := l
if r < nn && a[r].val < a[l].val {
c = r
}
if a[i].val <= a[c].val {
break
}
a[i], a[c] = a[c], a[i]
i = c
}
*h = a
return res
}
func pushGMax(h *[]GPair, x GPair) {
a := *h
a = append(a, x)
i := len(a) - 1
for i > 0 {
p := (i - 1) >> 1
if a[p].val >= a[i].val {
break
}
a[p], a[i] = a[i], a[p]
i = p
}
*h = a
}
func popGMax(h *[]GPair) GPair {
a := *h
res := a[0]
nn := len(a) - 1
if nn == 0 {
*h = a[:0]
return res
}
a[0] = a[nn]
a = a[:nn]
i := 0
for {
l := i*2 + 1
if l >= nn {
break
}
r := l + 1
c := l
if r < nn && a[r].val > a[l].val {
c = r
}
if a[i].val >= a[c].val {
break
}
a[i], a[c] = a[c], a[i]
i = c
}
*h = a
return res
}
func mark(g int) {
if seen[g] != stamp {
seen[g] = stamp
changed = append(changed, g)
}
}
func pushMember(id int) {
g := f[id]
pushMinPair(&minHs[g], Pair{val: base[id], id: id})
pushMaxPair(&maxHs[g], Pair{val: base[id], id: id})
}
func addBase(id int, delta int64) {
if delta == 0 {
return
}
base[id] += delta
pushMember(id)
mark(f[id])
}
func moveTarget(id, newg int) {
old := f[id]
f[id] = newg
pushMember(id)
mark(old)
mark(newg)
}
func groupMinVal(g int) (bool, int64) {
h := &minHs[g]
for len(*h) > 0 {
p := (*h)[0]
if f[p.id] != g || base[p.id] != p.val {
popMinPair(h)
} else {
return true, p.val
}
}
return false, 0
}
func groupMaxVal(g int) (bool, int64) {
h := &maxHs[g]
for len(*h) > 0 {
p := (*h)[0]
if f[p.id] != g || base[p.id] != p.val {
popMaxPair(h)
} else {
return true, p.val
}
}
return false, 0
}
func refreshGroup(g int) {
if ok, mn := groupMinVal(g); ok {
pushGMin(&gMinH, GPair{val: mn + wv[g], g: g})
}
if ok, mx := groupMaxVal(g); ok {
pushGMax(&gMaxH, GPair{val: mx + wv[g], g: g})
}
}
func changeDegree(id, newd int) {
oldW := wv[id]
oldS := selfv[id]
nw, ns := calc(t[id], newd)
d[id] = newd
selfv[id] = ns
wv[id] = nw
if ns != oldS {
addBase(id, ns-oldS)
}
if nw != oldW {
addBase(f[id], nw-oldW)
mark(id)
}
}
func globalMinVal() int64 {
for len(gMinH) > 0 {
p := gMinH[0]
if ok, mn := groupMinVal(p.g); ok && mn+wv[p.g] == p.val {
return p.val
}
popGMin(&gMinH)
}
return 0
}
func globalMaxVal() int64 {
for len(gMaxH) > 0 {
p := gMaxH[0]
if ok, mx := groupMaxVal(p.g); ok && mx+wv[p.g] == p.val {
return p.val
}
popGMax(&gMaxH)
}
return 0
}
func writeInt64(wr *bufio.Writer, x int64) {
var buf [32]byte
b := strconv.AppendInt(buf[:0], x, 10)
wr.Write(b)
wr.WriteByte('\n')
}
func writeTwoInt64(wr *bufio.Writer, a, b int64) {
var buf1 [32]byte
var buf2 [32]byte
x := strconv.AppendInt(buf1[:0], a, 10)
y := strconv.AppendInt(buf2[:0], b, 10)
wr.Write(x)
wr.WriteByte(' ')
wr.Write(y)
wr.WriteByte('\n')
}
func main() {
fs := NewFastScanner()
n = int(fs.Int64())
q = int(fs.Int64())
t = make([]int64, n+1)
for i := 1; i <= n; i++ {
t[i] = fs.Int64()
}
f = make([]int, n+1)
d = make([]int, n+1)
for i := 1; i <= n; i++ {
f[i] = int(fs.Int64())
d[f[i]]++
}
wv = make([]int64, n+1)
selfv = make([]int64, n+1)
for i := 1; i <= n; i++ {
wv[i], selfv[i] = calc(t[i], d[i])
}
followSum := make([]int64, n+1)
for i := 1; i <= n; i++ {
followSum[f[i]] += wv[i]
}
base = make([]int64, n+1)
for i := 1; i <= n; i++ {
base[i] = selfv[i] + followSum[i]
}
minHs = make([][]Pair, n+1)
maxHs = make([][]Pair, n+1)
for i := 1; i <= n; i++ {
pushMember(i)
}
gMinH = make([]GPair, 0, n+q*8+5)
gMaxH = make([]GPair, 0, n+q*8+5)
for g := 1; g <= n; g++ {
refreshGroup(g)
}
seen = make([]int, n+1)
changed = make([]int, 0, 16)
stamp = 1
wr := bufio.NewWriterSize(os.Stdout, 1<<20)
for qq := 0; qq < q; qq++ {
typ := int(fs.Int64())
if typ == 1 {
i := int(fs.Int64())
j := int(fs.Int64())
stamp++
changed = changed[:0]
old := f[i]
wi := wv[i]
moveTarget(i, j)
addBase(old, -wi)
addBase(j, wi)
changeDegree(old, d[old]-1)
changeDegree(j, d[j]+1)
for _, g := range changed {
refreshGroup(g)
}
} else if typ == 2 {
i := int(fs.Int64())
writeInt64(wr, base[i]+wv[f[i]])
} else {
writeTwoInt64(wr, globalMinVal(), globalMaxVal())
}
}
wr.Flush()
}
```