Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

You are given an array of N integers. You should support the following queries on this array.

0 L R : Find the minimum integer in the range A_{L}, A_{L+1}, ..., A_{R}.
1 L R X :  You should apply the assignment A[i] = A[i] & X, for all indices i in range [L, R], where & denotes bitwise AND operation.

------ Input ------ 

First line of the input contains two space separated integers N and Q.
Second line contains N integer numbers denoting array A. 
In the next Q lines, each contain one of the queries described above.

------ Output ------ 

For each query of the type 0, output  a single line containing the answer of the query.

------ Constraints ------ 

$1 ≤ N, Q ≤ 10^{5}$
$1 ≤ A_{i}, X ≤ 10^{9}$
$1 ≤ L ≤ R ≤ N $

------ Example ------ 

Input:
5 5
1 5 2 3 4
0 2 5
1 1 5 6
0 2 2
1 2 5 3
0 1 3

Output:
2
4
0

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Square root algorithms

Range queries

Segment trees revisited

Mathematics

Data structures


Solutions:
(n, q) = map(int, input().split())
global segment_tree, arr
arr = list(map(int, input().split()))
segment_tree = [0] * (4 * n)

class Node:

	def __init__(self):
		self.xory = 0
		self.min_val = 10 ** 9

def build_tree(start, end, treenode=0):
	global segment_tree, arr
	if start == end:
		node = Node()
		node.min_val = arr[start]
		node.xory = arr[start]
		segment_tree[treenode] = node
		return
	mid = (start + end) // 2
	build_tree(start, mid, 2 * treenode + 1)
	build_tree(mid + 1, end, 2 * treenode + 2)
	n1 = segment_tree[2 * treenode + 1]
	n2 = segment_tree[2 * treenode + 2]
	node = Node()
	node.min_val = min(n1.min_val, n2.min_val)
	node.xory = n1.xory | n2.xory
	segment_tree[treenode] = node

def update_query(start, end, left, right, value, treenode=0):
	global segment_tree
	if left > end or right < start:
		return
	elif start == end and left <= start and (right >= end):
		segment_tree[treenode].min_val = segment_tree[treenode].min_val & value
		segment_tree[treenode].xory = segment_tree[treenode].min_val
		return
	else:
		call = False
		for bit_count in range(32):
			if not value >> bit_count & 1 and segment_tree[treenode].xory >> bit_count & 1:
				call = True
				break
		if not call:
			return
		mid = (start + end) // 2
		update_query(start, mid, left, right, value, 2 * treenode + 1)
		update_query(mid + 1, end, left, right, value, 2 * treenode + 2)
	n1 = segment_tree[2 * treenode + 1]
	n2 = segment_tree[2 * treenode + 2]
	segment_tree[treenode].min_val = min(n1.min_val, n2.min_val)
	segment_tree[treenode].xory = n1.xory | n2.xory

def retrieve_query(start, end, left, right, treenode=0):
	if left > end or right < start:
		return 10 ** 9
	elif left <= start and right >= end:
		return segment_tree[treenode].min_val
	else:
		mid = (start + end) // 2
		ans1 = retrieve_query(start, mid, left, right, 2 * treenode + 1)
		ans2 = retrieve_query(mid + 1, end, left, right, 2 * treenode + 2)
		return min(ans1, ans2)
build_tree(0, len(arr) - 1)
for _ in range(q):
	query = list(map(int, input().split()))
	if query[0] == 0:
		print(retrieve_query(0, len(arr) - 1, query[1] - 1, query[2] - 1))
	else:
		update_query(0, len(arr) - 1, query[1] - 1, query[2] - 1, query[3])


import numpy
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a = numpy.array(a)
for _ in range(q):
	aa = list(map(int, input().split()))
	if aa[0] == 1:
		a[aa[1] - 1:aa[2]] &= aa[3]
	else:
		print(numpy.amin(a[aa[1] - 1:aa[2]]))