#P18264. Barkley III

Barkley III

Barkley III

题目描述

Pigeland 有 nn 只擅长程序设计的小猪,第 ii 只的实力值为 aia_i。一个队伍的实力值等于所有队员实力值的按位与。

有些比赛只有编号在 [l,r][l,r] 内的小猪能参加。由于经费不足,必须从这一区间中恰好去掉一只,其余所有小猪都参加。教练希望通过选择被去掉的小猪,使队伍的实力值最大。

训练和比赛也会改变小猪的实力值。请依次处理以下 qq 个事件:

  • 1 l r x:对所有 l≤i≤rl\le i\le r,令 ai←ai&xa_i\leftarrow a_i\mathbin{\&}x。
  • 2 s x:令 as←xa_s\leftarrow x。
  • 3 l r:从 al,al+1,…,ara_l,a_{l+1},\ldots,a_r 中恰好删除一个数,输出剩余所有数的按位与的最大可能值。

其中 &\& 表示按位与。修改会影响后续事件。查询只要求输出最优实力值,不改变数组。

输入格式

每个输入文件只有一组测试数据。

第一行包含两个整数 n,qn,q(2≤n≤1062\le n\le10^6,1≤q≤1061\le q\le10^6)。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n(0≤ai<2630\le a_i<2^{63})。

接下来 qq 行,每行描述一个事件,格式如下:

  • 若事件为 1 l r x,则 1≤l≤r≤n1\le l\le r\le n,0≤x<2630\le x<2^{63}。
  • 若事件为 2 s x,则 1≤s≤n1\le s\le n,0≤x<2630\le x<2^{63}。
  • 若事件为 3 l r,则 1≤l<r≤n1\le l<r\le n。

输出格式

对于每个第三类事件,输出一行一个整数,表示该次查询的答案。

样例

5 9
7 7 7 6 7
3 1 5
2 1 3
3 1 5
3 1 3
1 1 2 3
3 1 3
2 2 8
3 1 3
3 1 2
7
6
7
3
3
8