问题描述

给定 $n$ 个数 $a_1, a_2, a_3, \dots, a_n$，支持 $q$ 个操作：

1. 1 x d：修改 $a_x = d$。
2. 2 l r：查询 $a_{l\sim r}$ 的最大值与次大值。

输入格式

• 第一行包含两个整数 $n, q$，满足 $1 \leq n, q \leq 2 \times 10^5$。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，满足 $1 \leq a_i \leq 10^6$。
• 接下来 $q$ 行，每行一个操作，保证：
  • 1 x d 操作中，$1 \leq x \leq n$，$1 \leq d \leq 10^6$。
  • 2 l r 操作中，$1 \leq l < r \leq n$。

输出格式

对于每个 2 l r 查询，输出一行两个数，分别表示最大值与次大值。

样例输入

6 5
1 1 4 5 1 4
2 1 2
2 1 3
2 1 4
1 2 3
2 1 3

样例输出

1 1
4 1
5 4
4 3