範囲最大値クエリ (Range Maximum Queries)

n 個の要素からなる配列と、q 個のクエリが与えられます。クエリには以下の2種類があります。

1. 指定した範囲内での最大値を取得するクエリ

2. 配列の特定の位置を更新するクエリ

これらのクエリを効率的に処理するのが、あなたの課題です。

入力

最初の行には、配列の要素数 n と、クエリの数 q (1 ≤ n, q ≤ 100000) が与えられます。

続く行では、n 個の整数 ($1 ≤ a_i ≤ 10^9$) が空白区切りで与えられ、これは配列の初期状態を表します。

その後の q 行には、それぞれクエリが1つずつ書かれています。

1. 範囲最大値クエリの場合: 行の先頭が 1 で、続けて2つの整数 と ($1 ≤ li ≤ ri ≤ n$) が指定されます。この場合、[ ] の範囲における最大値を求めます。

2. 配列更新クエリの場合: 行の先頭が 2 で、続けて2つの整数 と ($1 ≤ pi ≤ n, 1 ≤ xi ≤ 10^9$) が指定されます。この場合、配列の 番目の要素を新しい値 に更新します。

出力

範囲最大値クエリについては、各クエリごとに、その範囲での最大値を1行ずつ出力してください。

例