暂无测试数据。

Background

Description

九条可怜有 n 盒拼图，每盒拼图都有若干拼图块，可以拼出许多矩形图案。可是，可怜经常会弄丢拼图块，因此她需要将一些拼图送回厂家进行补块。可怜懒得将所有拼图拼好来检查完整性，仅当她的一盒拼图的拼图块数无法组成任何r 块×c 块的矩形图案（其中 r,c≥2），可怜才认为这盒拼图需要返厂补块。返厂补块需要的运费只和含有图块数最多的拼图有关。
可怜将 n 盒拼图从 1 到 n 编号。每次，可怜都想知道，如果从编号在[l,r]区间内的拼图中选择 k 盒一定需要补块的拼图，拼图块数最多的拼图的拼图块数最少是多少。当然，可怜只是随口问问，并不会真的将这些拼图返厂，所以询问后所有拼图的块数都不会变化。
有时，可怜会发现自己数错了拼图的块数，并将第 x 盒拼图的拼图块数更新为 y。她希望你能即时回答这些询问。

Format

Input

第一行两个整数 n,k,m， m 表示可怜询问和修改的数量和。
接下来一行 n 个正整数，第 i 个数表示第 i 盒拼图初始时的拼图块数。
接下来 m 行，每行 3 个数 opt,l,r。为了表明你在即时回答可怜的询问，真实的 opt,l,r 为输入的 opt,l,r 分别异或（ XOR） lastans，其中 lastans 表示上一次询问的答案，若之前没有询问操作，则 lastans=0。
若 opt=1，则表示这是一次询问操作，询问的区间为[l,r]。
若 opt=2，则表示这是一次修改操作，把第 l 盒拼图的块数修改为 r。

Output

对于每个询问操作，输出一行一个整数，表示拼图块数最多的拼图的拼图块
数最少是多少。保证答案存在。

Sample 1

Input

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

Output

5
7

Sample 2

Input

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

Output

7
5

Limitation

对于 30%的数据， n,m≤1000。
对于另 30%的数据，没有修改操作。
对于 100%的数据， 1≤n,m,k≤200000， l,r 合法，所有拼图的块数在任何时刻是[4,1000000]区间中的整数。
1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST