package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
var sc = bufio.NewScanner(os.Stdin)
func Scan() string {
sc.Scan()
return sc.Text()
}
func rScan() []rune {
return []rune(Scan())
}
func iScan() int {
n, _ := strconv.Atoi(Scan())
return n
}
func fScan() float64 {
n, _ := strconv.ParseFloat(Scan(), 64)
return n
}
func stringToInt(s string) int {
n, _ := strconv.Atoi(s)
return n
}
func SScan(n int) []string {
a := make([]string, n)
for i := 0; i < n; i++ {
a[i] = Scan()
}
return a
}
func iSScan(n int) []int {
a := make([]int, n)
for i := 0; i < n; i++ {
a[i] = iScan()
}
return a
}
func abs(x int) int {
if x < 0 {
x = -x
}
return x
}
func mod(x, d int) int {
x %= d
if x < 0 {
x += d
}
return x
}
func larger(a, b int) int {
if a < b {
return b
} else {
return a
}
}
func smaller(a, b int) int {
if a > b {
return b
} else {
return a
}
}
func max(a []int) int {
x := a[0]
for i := 0; i < len(a); i++ {
if x < a[i] {
x = a[i]
}
}
return x
}
func min(a []int) int {
x := a[0]
for i := 0; i < len(a); i++ {
if x > a[i] {
x = a[i]
}
}
return x
}
func sum(a []int) int {
x := 0
for _, v := range a {
x += v
}
return x
}
func fSum(a []float64) float64 {
x := 0.
for _, v := range a {
x += v
}
return x
}
func bPrint(f bool, x string, y string) {
if f {
fmt.Println(x)
} else {
fmt.Println(y)
}
}
func iSSPrint(x []int) {
fmt.Println(strings.Trim(fmt.Sprint(x), "[]"))
}
var lp1 int = 1000000007
var lp2 int = 998244353
func main() {
buf := make([]byte, 0)
sc.Buffer(buf, lp1)
sc.Split(bufio.ScanWords)
n, q := iScan(), iScan()
a := iSScan(n)
MaxE := func() int {
return -int(1e+18)
}
MaxMerger := func(a, b int) int {
if a > b {
return a
} else {
return b
}
}
seg := newSegtree(a, MaxE, MaxMerger)
for i := 0; i < q; i++ {
t := iScan()
if t == 1 {
x, v := iScan(), iScan()
x--
seg.Set(x, v)
} else if t == 2 {
l, r := iScan(), iScan()
l--
fmt.Println(seg.Prod(l, r))
} else if t == 3 {
p, target := iScan(), iScan()
p--
fmt.Println(seg.MaxRight(p, func(v int) bool { return v < target }) + 1)
}
}
}
type E func() int
type Merger func(a, b int) int
type Compare func(v int) bool
type Segtree struct {
n int
size int
log int
d []int
e E
merger Merger
}
func newSegtree(v []int, e E, m Merger) *Segtree {
seg := new(Segtree)
seg.n = len(v)
seg.log = seg.ceilPow2(seg.n)
seg.size = 1 << uint(seg.log)
seg.d = make([]int, 2*seg.size)
seg.e = e
seg.merger = m
for i, _ := range seg.d {
seg.d[i] = seg.e()
}
for i := 0; i < seg.n; i++ {
seg.d[seg.size+i] = v[i]
}
for i := seg.size - 1; i >= 1; i-- {
seg.Update(i)
}
return seg
}
func (seg *Segtree) Update(k int) {
seg.d[k] = seg.merger(seg.d[2*k], seg.d[2*k+1])
}
func (seg *Segtree) Set(p, x int) {
p += seg.size
seg.d[p] = x
for i := 1; i <= seg.log; i++ {
seg.Update(p >> uint(i))
}
}
func (seg *Segtree) Get(p int) int {
return seg.d[p+seg.size]
}
func (seg *Segtree) Prod(l, r int) int {
sml, smr := seg.e(), seg.e()
l += seg.size
r += seg.size
for l < r {
if (l & 1) == 1 {
sml = seg.merger(sml, seg.d[l])
l++
}
if (r & 1) == 1 {
r--
smr = seg.merger(seg.d[r], smr)
}
l >>= 1
r >>= 1
}
return seg.merger(sml, smr)
}
func (seg *Segtree) AllProd() int {
return seg.d[1]
}
func (seg *Segtree) MaxRight(l int, cmp Compare) int {
if l == seg.n {
return seg.n
}
l += seg.size
sm := seg.e()
for {
for l%2 == 0 {
l >>= 1
}
if !cmp(seg.merger(sm, seg.d[l])) {
for l < seg.size {
l = 2 * l
if cmp(seg.merger(sm, seg.d[l])) {
sm = seg.merger(sm, seg.d[l])
l++
}
}
return l - seg.size
}
sm = seg.merger(sm, seg.d[l])
l++
if l&-l == l {
break
}
}
return seg.n
}
func (seg *Segtree) MinLeft(r int, cmp Compare) int {
if r == 0 {
return 0
}
r += seg.size
sm := seg.e()
for {
r--
for r > 1 && r%2 != 0 {
r >>= 1
}
if !cmp(seg.merger(seg.d[r], sm)) {
for r < seg.size {
r = 2*r + 1
if cmp(seg.merger(seg.d[r], sm)) {
sm = seg.merger(seg.d[r], sm)
r--
}
}
return r + 1 - seg.size
}
sm = seg.merger(seg.d[r], sm)
if r&-r == r {
break
}
}
return 0
}
func (seg *Segtree) ceilPow2(n int) int {
x := 0
for (1 << uint(x)) < n {
x++
}
return x
}