package main

import (
	"sort"
)

type Change struct {
	day    int
	friend int32
	add    bool
}

type SavedState struct {
	day       int
	offset    int32
	length    int32
	changeIdx int32
}

var H []int
var changes [][]Change
var savedStates [][]SavedState
var pool []int32
var currentFriends []map[int]struct{}
var seen []int32
var queryID int32

func Init(N int, D int, H_arr []int) {
	H = H_arr
	changes = make([][]Change, N)
	savedStates = make([][]SavedState, N)
	pool = make([]int32, 0)
	currentFriends = make([]map[int]struct{}, N)
	seen = make([]int32, N)
	queryID = 0

	for i := 0; i < N; i++ {
		savedStates[i] = append(savedStates[i], SavedState{
			day:       0,
			offset:    0,
			length:    0,
			changeIdx: 0,
		})
		currentFriends[i] = make(map[int]struct{})
	}
}

func CurseChanges(U int, A []int, B []int) {
	for i := 0; i < U; i++ {
		u := A[i]
		w := B[i]
		day := i + 1

		applyUpdate(u, w, day)
		applyUpdate(w, u, day)
	}
	currentFriends = nil
}

func applyUpdate(u, w, day int) {
	if _, ok := currentFriends[u][w]; ok {
		delete(currentFriends[u], w)
		changes[u] = append(changes[u], Change{day: day, friend: int32(w), add: false})
	} else {
		currentFriends[u][w] = struct{}{}
		changes[u] = append(changes[u], Change{day: day, friend: int32(w), add: true})
	}

	lastState := savedStates[u][len(savedStates[u])-1]
	if len(changes[u])-int(lastState.changeIdx) >= 40 {
		offset := len(pool)
		for f := range currentFriends[u] {
			pool = append(pool, int32(f))
		}
		savedStates[u] = append(savedStates[u], SavedState{
			day:       day,
			offset:    int32(offset),
			length:    int32(len(currentFriends[u])),
			changeIdx: int32(len(changes[u])),
		})
	}
}

func getFriends(u int, v int) []int {
	low, high := 0, len(savedStates[u])-1
	best := 0
	for low <= high {
		mid := (low + high) / 2
		if savedStates[u][mid].day <= v {
			best = mid
			low = mid + 1
		} else {
			high = mid - 1
		}
	}

	state := savedStates[u][best]
	queryID++

	for i := int32(0); i < state.length; i++ {
		f := pool[int(state.offset+i)]
		seen[int(f)] = queryID
	}

	for i := int(state.changeIdx); i < len(changes[u]); i++ {
		c := changes[u][i]
		if c.day > v {
			break
		}
		if c.add {
			seen[int(c.friend)] = queryID
		} else {
			seen[int(c.friend)] = 0
		}
	}

	res := make([]int, 0, int(state.length)+40)
	for i := int32(0); i < state.length; i++ {
		f := pool[int(state.offset+i)]
		if seen[int(f)] == queryID {
			res = append(res, int(f))
			seen[int(f)] = -queryID
		}
	}
	for i := int(state.changeIdx); i < len(changes[u]); i++ {
		c := changes[u][i]
		if c.day > v {
			break
		}
		if c.add && seen[int(c.friend)] == queryID {
			res = append(res, int(c.friend))
			seen[int(c.friend)] = -queryID
		}
	}

	sort.Slice(res, func(i, j int) bool {
		return H[res[i]] < H[res[j]]
	})

	return res
}

func Question(x int, y int, v int) int {
	fx := getFriends(x, v)
	fy := getFriends(y, v)

	if len(fx) == 0 || len(fy) == 0 {
		return 1000000000
	}

	ans := 1000000000
	i, j := 0, 0
	for i < len(fx) && j < len(fy) {
		dist := H[fx[i]] - H[fy[j]]
		if dist < 0 {
			dist = -dist
		}
		if dist == 0 {
			return 0
		}
		if dist < ans {
			ans = dist
		}
		if H[fx[i]] < H[fy[j]] {
			i++
		} else {
			j++
		}
	}

	return ans
}

func main() {}