Xor и and запросы на массиве

Допустим, у меня есть массив состоящий из элементов a1, a2, ..., an. Будут поступать q запросов 2 видов:
а) xor-равно на отрезке (т. е. выполнить al:= al ⊕ x, . . . , ar := ar ⊕ x) ⊕ - это xor;
б) сообщить and на отрезке (т. е. al ∧ al+1 ∧ . . . ∧ ar).
Как мне осуществить это за O(n + q log n)?