神圣庄严的古战场
题号：NC252420
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

把战场划分为 n 个区块，每个区块有属性 a_i 和权值 w_i，a_i \in \{0,1\}。

八坂神奈子会做出 m 次操作，操作有两类：
1. 将第 x 个元素的权值修改为 w_i
2. 询问区间 [l, r] 的危险程度。此时你需要将结果告诉她。

危险程度定义为：可以将相邻的两个元素，且前一个元素的属性为 0，后一个元素的属性为 1 消去。进行有限次消去操作，令剩下的元素中最大的权值最小。该权值即为危险程度。

输入描述:

第一行两个正整数 n, m。
第二行 n 个正整数 a_i。
第三行 n 个正整数 w_i。
接下来 m 行，每行一个操作，为以下两种之一：
1\ x\ w，表示将第 x 个元素的权值修改为 w_i；
2\ l\ r，表示询问区间 [l, r] 的危险程度。

输出描述:

对于每个 2\ l\ r 操作，输出一行，每行一个整数，该区间的危险程度。
示例1

输入

复制 
10 10
0 1 1 0 1 1 0 1 0 0
12 7 17 13 9 2 4 19 10 6
1 7 12
1 1 14
1 4 6
1 7 1
2 6 10
2 4 5
2 2 10
1 6 19
2 2 9
1 10 2

输出

复制 
10
0
17
19

备注:

n, m \leq 100000, a_i \in \{0,1\}, 0 \leq w_i < 2^{30}