Условия Дан массив a длины n, состоящий из чисел от 0 до 106. Требуется отвечать на запросы типа «найдите значение побитового AND всех целых чисел в интервале от l до r включительно».
Напоминаем, что результат побитового AND нескольких чисел — это число, в котором бит равен единице тогда и только тогда, когда во всех этих числах соответствующий бит равен единице.
Система оценки Всего в задаче 20 тестов (не считая примера). Каждый тест оценивается в 5 баллов.
Гарантируется, что не менее, чем в 30% тестов n,q ≤ 1000 и не менее, чем в 30% тестов ai равны 0 или 1.
Формат входных данных Первая строка входных данных содержит два целых числа n и q (1 ≤ n ≤ 2·105; 1 ≤ q ≤ 2·105) — количество чисел и количество запросов соответственно. Вторая строка содержит массив a, перечисленный слева направо, и содержит n целых чисел ai (0 ≤ ai ≤ 106). Каждая из последующих q строк содержит по два целых числа l и r — границы интервала для очередного запроса (1 ≤ l ≤ r ≤ n).
Формат выходных данных Для каждого запроса в отдельной строке выведите одно целое число — результат ответа на очередной запрос.
Примеры
Входные данные:
5 4
2 5 3 4 1
1 3
4 5
2 5
2 3
Выходные данные:
0
0
0
1
Мой вариант:
from operator import __and__
from functools import reduce
n, q = map(int, input().split())
*a, = map(int, input().split())
res = []
for _ in range(q):
left, right = map(int, input().split())
res.append(reduce(__and__, a[left-1:right]))
print(*res, sep='\n')