// Infoarena-arbint.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <memory>
#include <fstream>
#include <algorithm>

struct MaximumIntervalTreeInternal
{
    int max = 0;
    int leftIdx = 0;
    int rightIdx = 0;
    std::shared_ptr<MaximumIntervalTreeInternal> left;
    std::shared_ptr<MaximumIntervalTreeInternal> right;
};

void updateMax(std::shared_ptr<MaximumIntervalTreeInternal> root)
{
    if (!root->left && !root->right)
    {
        return;
    }
    if (!root->left)
    {
        root->max = root->right->max;
    }
    else if (!root->right)
    {
        root->max = root->left->max;
    }
    else
    {
        root->max = root->left->max > root->right->max ? root->left->max : root->right->max;
    }
}

std::shared_ptr<MaximumIntervalTreeInternal> buildInternalTreeRec(const std::vector<int>& BackingArray, int Left, int Right)
{
    auto root = std::make_shared<MaximumIntervalTreeInternal>();
    root->leftIdx = Left;
    root->rightIdx = Right;

    if (Left == Right)
    {
        root->max = BackingArray[Left];
        return root;
    }

    int mid = (Right + Left) / 2;
    root->left = buildInternalTreeRec(BackingArray, Left, mid);
    root->right = buildInternalTreeRec(BackingArray, mid + 1, Right);
    updateMax(root);
    return root;
}

std::shared_ptr<MaximumIntervalTreeInternal> buildInternalTree(const std::vector<int>& BackingArray)
{
    return buildInternalTreeRec(BackingArray, 0, BackingArray.size() - 1);
}

void updateValue(std::shared_ptr<MaximumIntervalTreeInternal> Root, int NewValue, int Index)
{
    if (Root->leftIdx == Root->rightIdx && Root->leftIdx == Index)
    {
        Root->max = NewValue;
        return;
    }

    int mid = (Root->rightIdx + Root->leftIdx) / 2;
    if (Index <= mid && Root->left)
    {
        updateValue(Root->left, NewValue, Index);
    }
    else if(Index > mid && Root->right)
    {
        updateValue(Root->right, NewValue, Index);
    }
    updateMax(Root);
}

int getMaximum(std::shared_ptr<MaximumIntervalTreeInternal> root, int Left, int Right)
{
    if (Left == root->leftIdx && Right == root->rightIdx)
    {
        return root->max;
    }

    int mid = (root->leftIdx + root->rightIdx) / 2;
    if (Left <= mid && Right <= mid)
    {
        return getMaximum(root->left, Left, Right);
    }
    else if (Left > mid && Right > mid)
    {
        return getMaximum(root->right, Left, Right);
    }
    else
    {
        return std::max(getMaximum(root->left, Left, mid), getMaximum(root->right, mid + 1, Right));
    }
}

class MaximumIntervalTree
{
public:
    MaximumIntervalTree(const std::vector<int>& BackingArray)
        : root{buildInternalTree(BackingArray)}
    {}

    int maxInRange(int Left, int Right)
    {
        return getMaximum(root, Left, Right);
    }

    void updateMax(int NewValue, int Index)
    {
        updateValue(root, NewValue, Index);
    }

private:
    std::shared_ptr<MaximumIntervalTreeInternal> root;
};

std::vector<int> readBackingArray(std::istream& in, int n)
{
    std::vector<int> arr(n, 0);
    for (int i = 0; i < n; ++i)
    {
        in >> arr[i];
    }
    return arr;
}

void processInput(std::istream& in, std::ostream& out, MaximumIntervalTree& Tree, int CommandCount)
{
    while (CommandCount--)
    {
        int command;
        in >> command;
        switch (command)
        {
        case 0:
            int left, right;
            in >> left >> right;
            out << Tree.maxInRange(--left, --right) << std::endl;
            break;
        case 1:
            int index, newValue;
            in >> index >> newValue;
            Tree.updateMax(newValue, --index);
            break;
        }
    }
}

int main()
{
    std::ifstream in("arbint.in");
    std::ofstream out("arbint.out");
    int arrSize, commandsCount;
    in >> arrSize >> commandsCount;
    auto backingArray = readBackingArray(in, arrSize);
    MaximumIntervalTree tree{ backingArray };
    
    processInput(in, out, tree, commandsCount);
    //processInput(in, std::cout, tree, commandsCount);
    return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file