#1627. 「雅礼集训 2018 Day7」A

「雅礼集训 2018 Day7」A

题目描述

给定一个长度为 nn 的序列 AiA_i,下标从 11 开始。对其依次进行 mm 次操作或询问,分为 33 种类型:

  • 1 l r x:将 Al...rA_{l...r} 中每个元素二进制与上一个数 xx
  • 2 l r x:将 Al...rA_{l...r} 中每个元素二进制或上一个数 xx
  • 3 l r:求 Al...rA_{l...r} 中的最小值

输入格式

第一行两个整数 n,mn, m

接下来一行 nn 个整数表示序列 A1,...,AnA_1, ..., A_n

接下来 mm 行一行表示一个操作或询问,格式如上文所述。

输出格式

对于每个询问,输出一行一个整数表示最小值。

样例

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

数据范围与提示

对于所有数据,1n,m500000,0Ai,xi<2311 \leq n, m \leq 500000, 0 \leq A_i, x_i < 2^{31}

  • 子任务 1(points:20)\rm 1(points: 20)n,m1000n, m \leq 1000
  • 子任务 2(points:20)\rm 2(points: 20)n,m10000n, m \leq 10000
  • 子任务 3(points:30)\rm 3(points: 30)n,m100000n, m \leq 100000
  • 子任务 4(points:30)\rm 4(points: 30)n,m500000n, m \leq 500000