package atcoder.acl; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.Arrays; import java.util.Random; import java.util.StringTokenizer; public final class J { private static class SegTree { int leftMost, rightMost; SegTree left, right; int max; SegTree(int leftMost, int rightMost, int[] arr) { this.leftMost = leftMost; this.rightMost = rightMost; if (leftMost == rightMost) { max = arr[leftMost]; } else { final int mid = leftMost + rightMost >>> 1; left = new SegTree(leftMost, mid, arr); right = new SegTree(mid + 1, rightMost, arr); recalc(); } } private void recalc() { if (leftMost == rightMost) { return; } max = Math.max(left.max, right.max); } private int query1(int l, int r) { if (r < leftMost || l > rightMost) { return Integer.MIN_VALUE; } if (l <= leftMost && rightMost <= r) { return max; } return Math.max(left.query1(l, r), right.query1(l, r)); } private int query2(int k, int l) { if (max < k || rightMost < l) { return -1; } if (leftMost == rightMost) { return leftMost; } final int resL = left.query2(k, l); return resL != -1 ? resL : right.query2(k, l); } private void update(int idx, int val) { if (leftMost == rightMost) { max = val; } else { final int mid = leftMost + rightMost >>> 1; if (idx <= mid) { left.update(idx, val); } else { right.update(idx, val); } recalc(); } } } public static void main(String[] args) { final FastScanner fs = new FastScanner(); final PrintWriter pw = new PrintWriter(System.out); final int n = fs.nextInt(); final int q = fs.nextInt(); final int[] arr = fs.nextIntArray(n); final SegTree st = new SegTree(0, n - 1, arr); for (int i = 0; i < q; i++) { final int type = fs.nextInt(); if (type == 1) { final int idx = fs.nextInt() - 1; final int val = fs.nextInt(); st.update(idx, val); } else if (type == 2) { final int l = fs.nextInt() - 1; final int r = fs.nextInt() - 1; pw.println(st.query1(l, r)); } else { final int idx = fs.nextInt() - 1; final int val = fs.nextInt(); final int res = st.query2(val, idx); pw.println(res == -1 ? n + 1 : res + 1); } } pw.close(); } static final class Utils { public static void shuffleSort(int[] arr) { shuffle(arr); Arrays.sort(arr); } public static void shuffleSort(long[] arr) { shuffle(arr); Arrays.sort(arr); } public static void shuffle(int[] arr) { final Random r = new Random(); for (int i = 0; i <= arr.length - 2; i++) { final int j = i + r.nextInt(arr.length - i); swap(arr, i, j); } } public static void shuffle(long[] arr) { final Random r = new Random(); for (int i = 0; i <= arr.length - 2; i++) { final int j = i + r.nextInt(arr.length - i); swap(arr, i, j); } } public static void swap(int[] arr, int i, int j) { final int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void swap(long[] arr, int i, int j) { final long t = arr[i]; arr[i] = arr[j]; arr[j] = t; } private Utils() {} } static class FastScanner { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(""); private String next() { while (!st.hasMoreTokens()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { //noinspection CallToPrintStackTrace e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } int[] nextIntArray(int n) { final int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = nextInt(); } return a; } long[] nextLongArray(int n) { final long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = nextLong(); } return a; } } }