# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py import math from bisect import bisect_left, bisect_right import time from heapq import * def main(B_SIZE, n, q, A, Q): time0 = time.time() class SortedMultiset: BUCKET_RATIO = 16 SPLIT_RATIO = 24 def __init__(self, a = []): "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)" a = list(a) n = self.size = len(a) if any(a[i] > a[i + 1] for i in range(n - 1)): a.sort() num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO))) self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)] def __iter__(self): for i in self.a: for j in i: yield j def __reversed__(self): for i in reversed(self.a): for j in reversed(i): yield j def __eq__(self, other) -> bool: return list(self) == list(other) def __len__(self) -> int: return self.size def __repr__(self) -> str: return "SortedMultiset" + str(self.a) def __str__(self) -> str: s = str(list(self)) return "{" + s[1 : len(s) - 1] + "}" def _position(self, x): "return the bucket, index of the bucket and position in which x should be. self must not be empty." for i, a in enumerate(self.a): if x <= a[-1]: break return (a, i, bisect_left(a, x)) def __contains__(self, x) -> bool: if self.size == 0: return False a, _, i = self._position(x) return i != len(a) and a[i] == x def count(self, x) -> int: "Count the number of x." return self.index_right(x) - self.index(x) def add(self, x) -> None: "Add an element. / O(√N)" if self.size == 0: self.a = [[x]] self.size = 1 return a, b, i = self._position(x) a.insert(i, x) self.size += 1 if len(a) > len(self.a) * self.SPLIT_RATIO: mid = len(a) >> 1 self.a[b:b+1] = [a[:mid], a[mid:]] def _pop(self, a, b: int, i: int): ans = a.pop(i) self.size -= 1 if not a: del self.a[b] return ans def discard(self, x) -> bool: "Remove an element and return True if removed. / O(√N)" if self.size == 0: return False a, b, i = self._position(x) if i == len(a) or a[i] != x: return False self._pop(a, b, i) return True def lt(self, x): "Find the largest element < x, or None if it doesn't exist." for a in reversed(self.a): if a[0] < x: return a[bisect_left(a, x) - 1] def le(self, x): "Find the largest element <= x, or None if it doesn't exist." for a in reversed(self.a): if a[0] <= x: return a[bisect_right(a, x) - 1] def gt(self, x): "Find the smallest element > x, or None if it doesn't exist." for a in self.a: if a[-1] > x: return a[bisect_right(a, x)] def ge(self, x): "Find the smallest element >= x, or None if it doesn't exist." for a in self.a: if a[-1] >= x: return a[bisect_left(a, x)] def __getitem__(self, i: int): "Return the i-th element." if i < 0: for a in reversed(self.a): i += len(a) if i >= 0: return a[i] else: for a in self.a: if i < len(a): return a[i] i -= len(a) raise IndexError def pop(self, i: int = -1): "Pop and return the i-th element." if i < 0: for b, a in enumerate(reversed(self.a)): i += len(a) if i >= 0: return self._pop(a, ~b, i) else: for b, a in enumerate(self.a): if i < len(a): return self._pop(a, b, i) i -= len(a) raise IndexError def index(self, x) -> int: "Count the number of elements < x." ans = 0 for a in self.a: if a[-1] >= x: return ans + bisect_left(a, x) ans += len(a) return ans def index_right(self, x) -> int: "Count the number of elements <= x." ans = 0 for a in self.a: if a[-1] > x: return ans + bisect_right(a, x) ans += len(a) return ans A_ = [A[i] for i in range(n)] inf = 1 << 30 q0 = q1 = 0 Q_ = [] T = [] for i in range(q): if Q[i][0] == 1: T.append((Q[i][1], A_[Q[i][1]], Q[i][2])) A_[Q[i][1]] = Q[i][2] q0 += 1 else: Q_.append((q0, Q[i][1], q1)) q1 += 1 Ans = [-1] * q1 b_siz = int((2*n*q0/q1) ** 0.5) + 1 b_siz = B_SIZE b_cnt = n // b_siz + 1 #print(b_siz) #print(b_cnt) D = [[] for _ in range(b_cnt)] for i in range(q1): t, r, idx = Q_[i] D[r//b_siz].append((t, r, idx)) for i in range(b_cnt): if i % 2: D[i].sort(reverse = True) else: D[i].sort() nt = nr = 0 S = SortedMultiset([inf]) hq0 = [] hq1 = [] cnt = 0 for x in range(b_cnt): nr = x * b_siz for now in range(max(0, (x-1)*b_siz), min(n, x*b_siz)): a = A[now] S.add(a) idx = S.index(a) if idx: heappush(hq1, S[idx-1]^S[idx+1]) heappush(hq0, S[idx-1]^S[idx]) heappush(hq0, S[idx]^S[idx+1]) for t, r, ans_idx in D[x]: if nt <= t: for now in range(nt, t): i, pa, a = T[now] if i < nr: idx = S.index(pa) if idx: heappush(hq0, S[idx-1]^S[idx+1]) heappush(hq1, S[idx-1]^S[idx]) heappush(hq1, S[idx]^S[idx+1]) S.discard(pa) S.add(a) idx = S.index(a) if idx: heappush(hq1, S[idx-1]^S[idx+1]) heappush(hq0, S[idx-1]^S[idx]) heappush(hq0, S[idx]^S[idx+1]) A[i] = a else: for now in range(nt-1, t-1, -1): i, pa, a = T[now] if i < nr: idx = S.index(a) if idx: heappush(hq0, S[idx-1]^S[idx+1]) heappush(hq1, S[idx-1]^S[idx]) heappush(hq1, S[idx]^S[idx+1]) S.discard(a) S.add(pa) idx = S.index(pa) if idx: heappush(hq1, S[idx-1]^S[idx+1]) heappush(hq0, S[idx-1]^S[idx]) heappush(hq0, S[idx]^S[idx+1]) A[i] = pa while hq0 and hq1 and hq0[0] == hq1[0]: heappop(hq0) heappop(hq1) if hq0: ans = hq0[0] else: ans = inf B = A[x*b_siz :r] nt = t B.sort() for i in range(len(B)-1): ans = min(ans, B[i]^B[i+1]) for b in B: idx = S.index(b) if idx: ans = min(ans, b^S[idx-1]) ans = min(ans, b^S[idx]) Ans[ans_idx] = ans for ans in Ans: print(ans) #continue #print(time.time()-time0) #print() n, q = map(int, input().split()) A = list(map(int, input().split())) Q = [list(map(int, input().split())) for _ in range(q)] for i in range(q): if Q[i][0] == 1: Q[i][1] -= 1 for i in range(90, 91, 10): main(i, n, q, A, Q)