#include <iostream>
#include <vector>

namespace segment_tree {

template<typename T>
class SegmentTree;

class TravelState {
 public:
	int index, left, right;

	TravelState(int index, int left, int right) : index(index), left(left), 
	right(right) {}

	inline bool isLeaf() {
		return left == right;
	}

	inline int mid() {
		return (left + right)>>1;
	}

	inline int now() {
		return index;
	}

	inline int leftSon() {
		return index<<1;
	}

	inline int rightSon() {
		return index<<1^1;
	}

	inline TravelState goLeft() {
		return TravelState(leftSon(), left, mid());
	}

	inline TravelState goRight() {
		return TravelState(rightSon(), mid()+1, right);
	}
};


template<typename T>
class BaseOp {
 public:
	SegmentTree<T>* segTree;

	BaseOp() : segTree(NULL) {}

	void bind(SegmentTree<T>* segTree) {
		this->segTree = segTree;
	}

	void unbind() {
		segTree = NULL;
	}

	virtual bool shouldStop(TravelState& s) {
		return s.isLeaf();
	}

	virtual bool shouldGoLeft(TravelState& s) {
		return true;
	}

	virtual bool shouldGoRight(TravelState& s) {
		return true;
	}

	virtual void before() {}

	virtual void stopping(TravelState& s) {}

	virtual void going(TravelState& s) {}

	virtual void returning(TravelState& s) {}

	virtual void after() {}
};

template<typename T>
class Build : public BaseOp<T> {
  public:
  	virtual bool shouldStop(TravelState& s) {
		return s.isLeaf();
	}

	virtual bool shouldGoLeft(TravelState& s) {
		return true;
	}

	virtual bool shouldGoRight(TravelState& s) {
		return true;
	}

	virtual void returning(TravelState& s) {
		this->segTree->recalculate((*this->segTree).v[s.now()], (*this->segTree).v[s.leftSon()], 
			(*this->segTree).v[s.rightSon()]);
	}
};

template<typename T>
class PointOp : public BaseOp<T> {
  public:
	int pos;

	PointOp(int pos) : pos(pos) {}

	virtual bool shouldGoLeft(TravelState& s) {
		return (pos <= s.mid());
	}

	virtual bool shouldGoRight(TravelState& s) {
		return (pos > s.mid());
	}
};

template<typename T>
class RangeOp : public BaseOp<T> {
  public:
	int left, right;

	RangeOp(int left, int right) : left(left), right(right) {}

	virtual bool shouldStop(TravelState& s) {
		return (left <= s.left && s.right <= right);
	}

	virtual bool shouldGoLeft(TravelState& s) {
		return (left <= s.mid());
	}

	virtual bool shouldGoRight(TravelState& s) {
		return (right > s.mid());
	}
};

template<typename T, typename U>
class PointUpdate : public PointOp<T> {
  public:
	U upd;
	PointUpdate(int pos, U upd) : PointOp<T>(pos), upd(upd) {}

	virtual void apply(TravelState& s, U& updater) {}

	virtual void stopping(TravelState& s) {
		apply(s, upd);
	}

	virtual void returning(TravelState& s) {
		this->segTree->recalculate((*this->segTree).v[s.now()], (*this->segTree).v[s.leftSon()], 
			(*this->segTree).v[s.rightSon()]);
	}
};

// Type T needs to have fields value and lazy.
// L must be the type of T.lazy.
// Type W from apply will be either T.lazy or U.
template<typename T, typename U, typename L>
class LazyRangeUpdate : public RangeOp<T> {
  public:
	U upd;
	LazyRangeUpdate(int left, int right, U upd) : RangeOp<T>(left, right), upd(upd) {}

	virtual void apply(TravelState& s, U& updater) {}

	virtual void apply(TravelState& s, L& updater) {}

	virtual void unloadLazy(TravelState& s) {
		auto ls = s.leftSon();
		apply(ls, (*this->segTree).v[s.now()].lazy);
		auto rs = s.rightSon();
		apply(rs, (*this->segTree).v[s.now()].lazy);
	}

	virtual void stopping(TravelState& s) {
		apply(s, upd);
	}

	virtual void going(TravelState& s) {
		unloadLazy(s);
	}

	virtual void returning(TravelState& s) {
		this->segTree->recalculate((*this->segTree).v[s.now()], (*this->segTree).v[s.leftSon()], 
			(*this->segTree).v[s.rightSon()]);
	}
};

// Define operator += on T.
template<typename T>
class SumQuery : public RangeOp<T> {
  public:
	T result;
	SumQuery(int left, int right, T init) : 
	RangeOp<T>(left, right), result(init) {}

	virtual void stopping(TravelState& s) {
		std::cout << s.left << " " << s.right << "\n";
		result += (*this->segTree).v[s.now()];
	}
};

// Define operator > on T.
template<typename T>
class MaxRangeQuery : public RangeOp<T> {
  public:
	T result;
	MaxRangeQuery(int left, int right, T init) : 
	RangeOp<T>(left, right), result(init) {}

	virtual void stopping(TravelState& s) {
		if ((*this->segTree).v[s.now()] > result) {
			result = (*this->segTree).v[s.now()];
		}
	}
};

// Define operator < on T.
template<typename T>
class MinRangeQuery : public RangeOp<T> {
  public:
	T result;
	MinRangeQuery(int left, int right, const T& init) : 
	RangeOp<T>(left, right), result(init) {}

	virtual void stopping(TravelState& s) {
		if ((*this->segTree).v[s.now()] < result) {
			result = (*this->segTree).v[s.now()];
		}
	}
};

// Define operator = between T and U.
template<typename T, typename U>
class PointReplace : public PointUpdate<T, U> {
  public:
	PointReplace(int pos, const U& upd) : PointUpdate<T, U>(pos, upd) {}

	virtual void apply(TravelState& s, U& updater) {
		(*this->segTree).v[s.now()] = updater;
	}
};

// Type T needs to have fields value and lazy.
// L must be the type of T.lazy.
// Type W from apply will be either T.lazy or U.
// Define operator = between all 4 of these pairs of types:
// {T.value, T.lazy} x {U, T.lazy}.
template<typename T, typename U, typename L>
class RangeReplace : public LazyRangeUpdate<T, U, L> {
  public:
	RangeReplace(int left, int right, const U& upd) 
	: LazyRangeUpdate<T, U, L>(left, right, upd) {}

	virtual void apply(TravelState& s, U& updater) {
		(*this->segTree).v[s.now()].value = updater;
		(*this->segTree).v[s.now()].lazy = updater;
	}

	virtual void apply(TravelState& s, L& updater) {
		(*this->segTree).v[s.now()].value = updater;
		(*this->segTree).v[s.now()].lazy = updater;
	}
};

// Same as RangeReplace, but with operator += instead of =.
template<typename T, typename U, typename L>
class RangeAdd : public LazyRangeUpdate<T, U, L> {
  public:
	RangeAdd(int left, int right, const U& upd) : 
	LazyRangeUpdate<T, U, L>(left, right, upd) {}

	virtual void apply(TravelState& s, U& updater) {
		(*this->segTree).v[s.now()].value += updater;
		(*this->segTree).v[s.now()].lazy += updater;
	}

	virtual void apply(TravelState& s, L& updater) {
		(*this->segTree).v[s.now()].value += updater;
		(*this->segTree).v[s.now()].lazy += updater;
	}
};

template<typename T>
class InitFromVector : public Build<T> {
	std::vector<T>& v;
  public:
  	InitFromVector(std::vector<T>& v) : v(v) {}

  	virtual void stopping(TravelState& s) {
  		(*this->segTree).v[s.now()] = v[s.left-1];
  	}
};

template<typename T>
class SegmentTree {
  public:
	int size;
	std::vector<T> v;

	SegmentTree(int size) : size(size) {
		v.resize(4*size);
	}
	
	virtual void recalculate(T& node, const T& leftSon, const T& rightSon)=0;

	void travel(TravelState& s, BaseOp<T>& op) {
		if (op.shouldStop(s)) {
			op.stopping(s);
		} else {
			op.going(s);
			if (op.shouldGoLeft(s)) {
				auto sl = s.goLeft();
				travel(sl, op);
			}
			if (op.shouldGoRight(s)) {
				auto sr = s.goRight();
				travel(sr, op);
			}
			op.returning(s);
		}
	}

	void apply(BaseOp<T>& op) {
		op.bind(this);
		op.before();
		auto state = TravelState(1, 1, size);
		travel(state, op);
		op.after();
		op.unbind();
	}
};

template<typename T>
class SumSegmentTree : public SegmentTree<T> {
  public:
  	SumSegmentTree(int size) : SegmentTree<T>(size) {}
	virtual void recalculate(T& node, const T& leftSon, const T& rightSon) {
		node = leftSon + rightSon;
	}
};

template<typename T>
class MaxSegmentTree : public SegmentTree<T> {
  public:
  	MaxSegmentTree(int size) : SegmentTree<T>(size) {}
  	virtual void recalculate(T& node, const T& leftSon, const T& rightSon) {
  		if (leftSon > rightSon)
  			node = leftSon;
  		else node = rightSon;
	}
};

}

using namespace std;
using namespace segment_tree;

int main() {
	freopen("arbint.in", "r", stdin);
	freopen("arbint.out", "w", stdout);
	int n, m;

	cin >> n >> m;

	vector<int> v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}

	MaxSegmentTree<int> tree(n);

	auto op = InitFromVector<int>(v);
	tree.apply(op);
	
	for (int i = 1; i <= m; ++i) {
		int t, a, b;
		cin >> t >> a >> b;
		if (t == 0) {
			auto op = MaxRangeQuery<int>(a, b, 0);
			tree.apply(op);
			cout << op.result << "\n";
		} else {
			auto op = PointReplace<int, int>(a, b);
			tree.apply(op);
		}
	}
}