#!/usr/bin/env python3 from array import array import sys BITS = 30 VALUE_MASK = (1 << BITS) - 1 LOW15_MASK = (1 << 15) - 1 def parse_input(): values = list(map(int, sys.stdin.buffer.read().split())) i = 0 n = values[i] m = values[i + 1] i += 2 initial = values[i:i + n] i += n left_data = [0] + values[i:i + m] i += m right_data = [0] + values[i:i + m] i += m mask_data = [0] + values[i:i + m] i += m sum_left_data = [0] + values[i:i + m] i += m sum_right_data = [0] + values[i:i + m] i += m problem_count = values[i] i += 1 tail = values[i:] starts = tail[0::2] counts = tail[1::2] return (n, m, initial, left_data, right_data, mask_data, sum_left_data, sum_right_data, problem_count, starts, counts) def build_tree(values): n = len(values) size = 1 while size < n: size <<= 1 nodes = size << 1 height = size.bit_length() - 1 # Base-B digits are per-bit population counts. B is chosen so that # evaluating the digit polynomial at 2 via mod (B-2) is exact. width = (n * VALUE_MASK + 2).bit_length() base = 1 << width field_ones = base - 1 eval_mod = base - 2 high_shift = 15 * width field_mask_lo = [0] * (1 << 15) digit_all = 0 for bit in range(30): digit_all |= 1 << (bit * width) for mask in range(1, 1 << 15): low = mask & -mask field_mask_lo[mask] = field_mask_lo[mask ^ low] | (field_ones << ((low.bit_length() - 1) * width)) field_mask_hi = [v << high_shift for v in field_mask_lo] total = [0] * nodes packed = [0] * nodes any_bits = [0] * nodes all_bits = [0] * nodes lazy_and = [VALUE_MASK] * nodes lazy_or = [0] * nodes saved = bytearray(nodes) p = size fmlo = field_mask_lo fmhi = field_mask_hi low15 = LOW15_MASK for value in values: total[p] = value packed[p] = (fmlo[value & low15] | fmhi[value >> 15]) & digit_all any_bits[p] = value all_bits[p] = value p += 1 p = size - 1 while p: left = p << 1 right = left | 1 total[p] = total[left] + total[right] packed[p] = packed[left] + packed[right] any_bits[p] = any_bits[left] | any_bits[right] all_bits[p] = all_bits[left] & all_bits[right] p -= 1 initial_total = total.copy() initial_packed = packed.copy() initial_any = any_bits.copy() initial_all = all_bits.copy() history = [] history_append = history.append def save(p, saved=saved, history_append=history_append): saved[p] = 1 history_append(p) def push(p, half, parent_and, parent_or, total=total, packed=packed, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15, eval_mod=eval_mod): left = p << 1 right = left | 1 if parent_and == parent_or: constant = parent_or constant_field = fmlo[constant & low15] | fmhi[constant >> 15] constant_packed = (constant_field & digit_all) * half old_any = any_bits[left] if old_any != constant or all_bits[left] != constant: if not saved[left]: save(left) total[left] = half * constant packed[left] = constant_packed any_bits[left] = constant all_bits[left] = constant lazy_and[left] = constant lazy_or[left] = constant old_any = any_bits[right] if old_any != constant or all_bits[right] != constant: if not saved[right]: save(right) total[right] = half * constant packed[right] = constant_packed any_bits[right] = constant all_bits[right] = constant lazy_and[right] = constant lazy_or[right] = constant elif parent_and == VALUE_MASK: mask = parent_or old_all = all_bits[left] changed = mask & (VALUE_MASK ^ old_all) if changed: if not saved[left]: save(left) field_mask = fmlo[changed & low15] | fmhi[changed >> 15] digit = field_mask & digit_all old_packed = packed[left] total[left] += half * changed - ((old_packed & field_mask) % eval_mod) packed[left] = (old_packed & ~field_mask) | (digit * half) any_bits[left] |= mask all_bits[left] = old_all | mask lazy_and[left] |= mask lazy_or[left] |= mask old_all = all_bits[right] changed = mask & (VALUE_MASK ^ old_all) if changed: if not saved[right]: save(right) field_mask = fmlo[changed & low15] | fmhi[changed >> 15] digit = field_mask & digit_all old_packed = packed[right] total[right] += half * changed - ((old_packed & field_mask) % eval_mod) packed[right] = (old_packed & ~field_mask) | (digit * half) any_bits[right] |= mask all_bits[right] = old_all | mask lazy_and[right] |= mask lazy_or[right] |= mask elif parent_or == 0: mask = parent_and clear_mask = VALUE_MASK ^ mask old_any = any_bits[left] changed = old_any & clear_mask if changed: if not saved[left]: save(left) field_mask = fmlo[changed & low15] | fmhi[changed >> 15] old_packed = packed[left] total[left] -= (old_packed & field_mask) % eval_mod packed[left] = old_packed & ~field_mask any_bits[left] = old_any & mask all_bits[left] &= mask lazy_and[left] &= mask lazy_or[left] &= mask old_any = any_bits[right] changed = old_any & clear_mask if changed: if not saved[right]: save(right) field_mask = fmlo[changed & low15] | fmhi[changed >> 15] old_packed = packed[right] total[right] -= (old_packed & field_mask) % eval_mod packed[right] = old_packed & ~field_mask any_bits[right] = old_any & mask all_bits[right] &= mask lazy_and[right] &= mask lazy_or[right] &= mask else: child = left old_any = any_bits[child] old_all = all_bits[child] clear_bits = old_any & (VALUE_MASK ^ parent_and) set_bits = parent_or & (VALUE_MASK ^ old_all) changed = clear_bits | set_bits if changed: if not saved[child]: save(child) set_field = fmlo[set_bits & low15] | fmhi[set_bits >> 15] set_digit = set_field & digit_all field_mask = fmlo[changed & low15] | fmhi[changed >> 15] old_packed = packed[child] total[child] += half * set_bits - ((old_packed & field_mask) % eval_mod) packed[child] = (old_packed & ~field_mask) | (set_digit * half) any_bits[child] = (old_any & parent_and) | parent_or all_bits[child] = (old_all & parent_and) | parent_or lazy_and[child] = (lazy_and[child] & parent_and) | parent_or lazy_or[child] = (lazy_or[child] & parent_and) | parent_or child = right old_any = any_bits[child] old_all = all_bits[child] clear_bits = old_any & (VALUE_MASK ^ parent_and) set_bits = parent_or & (VALUE_MASK ^ old_all) changed = clear_bits | set_bits if changed: if not saved[child]: save(child) set_field = fmlo[set_bits & low15] | fmhi[set_bits >> 15] set_digit = set_field & digit_all field_mask = fmlo[changed & low15] | fmhi[changed >> 15] old_packed = packed[child] total[child] += half * set_bits - ((old_packed & field_mask) % eval_mod) packed[child] = (old_packed & ~field_mask) | (set_digit * half) any_bits[child] = (old_any & parent_and) | parent_or all_bits[child] = (old_all & parent_and) | parent_or lazy_and[child] = (lazy_and[child] & parent_and) | parent_or lazy_or[child] = (lazy_or[child] & parent_and) | parent_or lazy_and[p] = VALUE_MASK lazy_or[p] = 0 update_parents = [0] * ((size.bit_length() << 2) + 4) def range_and(query_left, query_right, mask, total=total, packed=packed, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save, push=push, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15, size=size, update_parents=update_parents): clear_mask = VALUE_MASK ^ mask if not clear_mask: return parent_count = 0 p = 1 left_bound = 0 length = size while True: changed = any_bits[p] & clear_mask if not changed: break if query_left <= left_bound and left_bound + length <= query_right: if not saved[p]: save(p) field_mask = fmlo[changed & low15] | fmhi[changed >> 15] old_packed = packed[p] total[p] -= (old_packed & field_mask) % eval_mod packed[p] = old_packed & ~field_mask any_bits[p] &= mask all_bits[p] &= mask lazy_and[p] &= mask lazy_or[p] &= mask break half = length >> 1 parent_and = lazy_and[p] parent_or = lazy_or[p] if parent_and != VALUE_MASK or parent_or: push(p, half, parent_and, parent_or) update_parents[parent_count] = p parent_count += 1 middle = left_bound + half if query_right <= middle: p <<= 1 length = half continue if query_left >= middle: p = p << 1 | 1 left_bound = middle length = half continue # Left suffix [query_left, middle). branch = p << 1 branch_left = left_bound branch_length = half while True: changed = any_bits[branch] & clear_mask if not changed: break if query_left <= branch_left: if not saved[branch]: save(branch) field_mask = fmlo[changed & low15] | fmhi[changed >> 15] old_packed = packed[branch] total[branch] -= (old_packed & field_mask) % eval_mod packed[branch] = old_packed & ~field_mask any_bits[branch] &= mask all_bits[branch] &= mask lazy_and[branch] &= mask lazy_or[branch] &= mask break branch_half = branch_length >> 1 parent_and = lazy_and[branch] parent_or = lazy_or[branch] if parent_and != VALUE_MASK or parent_or: push(branch, branch_half, parent_and, parent_or) update_parents[parent_count] = branch parent_count += 1 branch_middle = branch_left + branch_half if query_left >= branch_middle: branch = branch << 1 | 1 branch_left = branch_middle branch_length = branch_half else: sibling = branch << 1 | 1 sibling_changed = any_bits[sibling] & clear_mask if sibling_changed: if not saved[sibling]: save(sibling) field_mask = fmlo[sibling_changed & low15] | fmhi[sibling_changed >> 15] old_packed = packed[sibling] total[sibling] -= (old_packed & field_mask) % eval_mod packed[sibling] = old_packed & ~field_mask any_bits[sibling] &= mask all_bits[sibling] &= mask lazy_and[sibling] &= mask lazy_or[sibling] &= mask branch <<= 1 branch_length = branch_half # Right prefix [middle, query_right). branch = p << 1 | 1 branch_left = middle branch_length = half while True: changed = any_bits[branch] & clear_mask if not changed: break if branch_left + branch_length <= query_right: if not saved[branch]: save(branch) field_mask = fmlo[changed & low15] | fmhi[changed >> 15] old_packed = packed[branch] total[branch] -= (old_packed & field_mask) % eval_mod packed[branch] = old_packed & ~field_mask any_bits[branch] &= mask all_bits[branch] &= mask lazy_and[branch] &= mask lazy_or[branch] &= mask break branch_half = branch_length >> 1 parent_and = lazy_and[branch] parent_or = lazy_or[branch] if parent_and != VALUE_MASK or parent_or: push(branch, branch_half, parent_and, parent_or) update_parents[parent_count] = branch parent_count += 1 branch_middle = branch_left + branch_half if query_right <= branch_middle: branch <<= 1 branch_length = branch_half else: sibling = branch << 1 sibling_changed = any_bits[sibling] & clear_mask if sibling_changed: if not saved[sibling]: save(sibling) field_mask = fmlo[sibling_changed & low15] | fmhi[sibling_changed >> 15] old_packed = packed[sibling] total[sibling] -= (old_packed & field_mask) % eval_mod packed[sibling] = old_packed & ~field_mask any_bits[sibling] &= mask all_bits[sibling] &= mask lazy_and[sibling] &= mask lazy_or[sibling] &= mask branch = branch << 1 | 1 branch_left = branch_middle branch_length = branch_half break while parent_count: parent_count -= 1 p = update_parents[parent_count] left = p << 1 right = left | 1 new_total = total[left] + total[right] if new_total != total[p]: if not saved[p]: save(p) total[p] = new_total packed[p] = packed[left] + packed[right] any_bits[p] = any_bits[left] | any_bits[right] all_bits[p] = all_bits[left] & all_bits[right] def range_or(query_left, query_right, mask, total=total, packed=packed, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save, push=push, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15, size=size, update_parents=update_parents): if not mask: return parent_count = 0 p = 1 left_bound = 0 length = size while True: changed = mask & (VALUE_MASK ^ all_bits[p]) if not changed: break if query_left <= left_bound and left_bound + length <= query_right: if not saved[p]: save(p) field_mask = fmlo[changed & low15] | fmhi[changed >> 15] digit = field_mask & digit_all old_packed = packed[p] total[p] += length * changed - ((old_packed & field_mask) % eval_mod) packed[p] = (old_packed & ~field_mask) | (digit * length) any_bits[p] |= mask all_bits[p] |= mask lazy_and[p] |= mask lazy_or[p] |= mask break half = length >> 1 parent_and = lazy_and[p] parent_or = lazy_or[p] if parent_and != VALUE_MASK or parent_or: push(p, half, parent_and, parent_or) update_parents[parent_count] = p parent_count += 1 middle = left_bound + half if query_right <= middle: p <<= 1 length = half continue if query_left >= middle: p = p << 1 | 1 left_bound = middle length = half continue branch = p << 1 branch_left = left_bound branch_length = half while True: changed = mask & (VALUE_MASK ^ all_bits[branch]) if not changed: break if query_left <= branch_left: if not saved[branch]: save(branch) field_mask = fmlo[changed & low15] | fmhi[changed >> 15] digit = field_mask & digit_all old_packed = packed[branch] total[branch] += branch_length * changed - ((old_packed & field_mask) % eval_mod) packed[branch] = (old_packed & ~field_mask) | (digit * branch_length) any_bits[branch] |= mask all_bits[branch] |= mask lazy_and[branch] |= mask lazy_or[branch] |= mask break branch_half = branch_length >> 1 parent_and = lazy_and[branch] parent_or = lazy_or[branch] if parent_and != VALUE_MASK or parent_or: push(branch, branch_half, parent_and, parent_or) update_parents[parent_count] = branch parent_count += 1 branch_middle = branch_left + branch_half if query_left >= branch_middle: branch = branch << 1 | 1 branch_left = branch_middle branch_length = branch_half else: sibling = branch << 1 | 1 sibling_changed = mask & (VALUE_MASK ^ all_bits[sibling]) if sibling_changed: if not saved[sibling]: save(sibling) field_mask = fmlo[sibling_changed & low15] | fmhi[sibling_changed >> 15] digit = field_mask & digit_all old_packed = packed[sibling] total[sibling] += branch_half * sibling_changed - ((old_packed & field_mask) % eval_mod) packed[sibling] = (old_packed & ~field_mask) | (digit * branch_half) any_bits[sibling] |= mask all_bits[sibling] |= mask lazy_and[sibling] |= mask lazy_or[sibling] |= mask branch <<= 1 branch_length = branch_half branch = p << 1 | 1 branch_left = middle branch_length = half while True: changed = mask & (VALUE_MASK ^ all_bits[branch]) if not changed: break if branch_left + branch_length <= query_right: if not saved[branch]: save(branch) field_mask = fmlo[changed & low15] | fmhi[changed >> 15] digit = field_mask & digit_all old_packed = packed[branch] total[branch] += branch_length * changed - ((old_packed & field_mask) % eval_mod) packed[branch] = (old_packed & ~field_mask) | (digit * branch_length) any_bits[branch] |= mask all_bits[branch] |= mask lazy_and[branch] |= mask lazy_or[branch] |= mask break branch_half = branch_length >> 1 parent_and = lazy_and[branch] parent_or = lazy_or[branch] if parent_and != VALUE_MASK or parent_or: push(branch, branch_half, parent_and, parent_or) update_parents[parent_count] = branch parent_count += 1 branch_middle = branch_left + branch_half if query_right <= branch_middle: branch <<= 1 branch_length = branch_half else: sibling = branch << 1 sibling_changed = mask & (VALUE_MASK ^ all_bits[sibling]) if sibling_changed: if not saved[sibling]: save(sibling) field_mask = fmlo[sibling_changed & low15] | fmhi[sibling_changed >> 15] digit = field_mask & digit_all old_packed = packed[sibling] total[sibling] += branch_half * sibling_changed - ((old_packed & field_mask) % eval_mod) packed[sibling] = (old_packed & ~field_mask) | (digit * branch_half) any_bits[sibling] |= mask all_bits[sibling] |= mask lazy_and[sibling] |= mask lazy_or[sibling] |= mask branch = branch << 1 | 1 branch_left = branch_middle branch_length = branch_half break while parent_count: parent_count -= 1 p = update_parents[parent_count] left = p << 1 right = left | 1 new_total = total[left] + total[right] if new_total != total[p]: if not saved[p]: save(p) total[p] = new_total packed[p] = packed[left] + packed[right] any_bits[p] = any_bits[left] | any_bits[right] all_bits[p] = all_bits[left] & all_bits[right] def point_and(index, mask, total=total, packed=packed, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save, push=push, fmlo=fmlo, fmhi=fmhi, low15=low15, eval_mod=eval_mod, size=size, update_parents=update_parents): clear_mask = VALUE_MASK ^ mask if not clear_mask: return p = 1 left_bound = 0 length = size parent_count = 0 while length > 1: if not (any_bits[p] & clear_mask): return half = length >> 1 parent_and = lazy_and[p] parent_or = lazy_or[p] if parent_and != VALUE_MASK or parent_or: push(p, half, parent_and, parent_or) update_parents[parent_count] = p parent_count += 1 middle = left_bound + half if index < middle: p <<= 1 else: p = p << 1 | 1 left_bound = middle length = half changed = any_bits[p] & clear_mask if not changed: return if not saved[p]: save(p) new_value = total[p] & mask total[p] = new_value packed[p] = (fmlo[new_value & low15] | fmhi[new_value >> 15]) & digit_all any_bits[p] = new_value all_bits[p] = new_value lazy_and[p] = VALUE_MASK lazy_or[p] = 0 while parent_count: parent_count -= 1 p = update_parents[parent_count] left = p << 1 right = left | 1 if not saved[p]: save(p) total[p] = total[left] + total[right] packed[p] = packed[left] + packed[right] any_bits[p] = any_bits[left] | any_bits[right] all_bits[p] = all_bits[left] & all_bits[right] def point_or(index, mask, total=total, packed=packed, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save, push=push, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15, eval_mod=eval_mod, size=size, update_parents=update_parents): if not mask: return p = 1 left_bound = 0 length = size parent_count = 0 while length > 1: if not (mask & (VALUE_MASK ^ all_bits[p])): return half = length >> 1 parent_and = lazy_and[p] parent_or = lazy_or[p] if parent_and != VALUE_MASK or parent_or: push(p, half, parent_and, parent_or) update_parents[parent_count] = p parent_count += 1 middle = left_bound + half if index < middle: p <<= 1 else: p = p << 1 | 1 left_bound = middle length = half changed = mask & (VALUE_MASK ^ all_bits[p]) if not changed: return if not saved[p]: save(p) new_value = total[p] | mask total[p] = new_value packed[p] = (fmlo[new_value & low15] | fmhi[new_value >> 15]) & digit_all any_bits[p] = new_value all_bits[p] = new_value lazy_and[p] = VALUE_MASK lazy_or[p] = 0 while parent_count: parent_count -= 1 p = update_parents[parent_count] left = p << 1 right = left | 1 if not saved[p]: save(p) total[p] = total[left] + total[right] packed[p] = packed[left] + packed[right] any_bits[p] = any_bits[left] | any_bits[right] all_bits[p] = all_bits[left] & all_bits[right] def point_set(index, new_value, total=total, packed=packed, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save, push=push, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15, height=height): p = 1 shift = height - 1 while shift >= 0: parent_and = lazy_and[p] parent_or = lazy_or[p] if parent_and != VALUE_MASK or parent_or: push(p, 1 << shift, parent_and, parent_or) p = (p << 1) | ((index >> shift) & 1) shift -= 1 if total[p] == new_value: return if not saved[p]: save(p) total[p] = new_value packed[p] = (fmlo[new_value & low15] | fmhi[new_value >> 15]) & digit_all any_bits[p] = new_value all_bits[p] = new_value lazy_and[p] = VALUE_MASK lazy_or[p] = 0 p >>= 1 while p: left = p << 1 right = left | 1 if not saved[p]: save(p) total[p] = total[left] + total[right] packed[p] = packed[left] + packed[right] any_bits[p] = any_bits[left] | any_bits[right] all_bits[p] = all_bits[left] & all_bits[right] p >>= 1 def point_and_value(index, mask, total=total, packed=packed, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save, push=push, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15, height=height): p = 1 shift = height - 1 while shift >= 0: parent_and = lazy_and[p] parent_or = lazy_or[p] if parent_and != VALUE_MASK or parent_or: push(p, 1 << shift, parent_and, parent_or) p = (p << 1) | ((index >> shift) & 1) shift -= 1 old_value = total[p] new_value = old_value & mask if new_value != old_value: if not saved[p]: save(p) total[p] = new_value packed[p] = (fmlo[new_value & low15] | fmhi[new_value >> 15]) & digit_all any_bits[p] = new_value all_bits[p] = new_value lazy_and[p] = VALUE_MASK lazy_or[p] = 0 p >>= 1 while p: left = p << 1 right = left | 1 if not saved[p]: save(p) total[p] = total[left] + total[right] packed[p] = packed[left] + packed[right] any_bits[p] = any_bits[left] | any_bits[right] all_bits[p] = all_bits[left] & all_bits[right] p >>= 1 return new_value def point_or_value(index, mask, total=total, packed=packed, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, save=save, push=push, fmlo=fmlo, fmhi=fmhi, digit_all=digit_all, low15=low15, height=height): p = 1 shift = height - 1 while shift >= 0: parent_and = lazy_and[p] parent_or = lazy_or[p] if parent_and != VALUE_MASK or parent_or: push(p, 1 << shift, parent_and, parent_or) p = (p << 1) | ((index >> shift) & 1) shift -= 1 old_value = total[p] new_value = old_value | mask if new_value != old_value: if not saved[p]: save(p) total[p] = new_value packed[p] = (fmlo[new_value & low15] | fmhi[new_value >> 15]) & digit_all any_bits[p] = new_value all_bits[p] = new_value lazy_and[p] = VALUE_MASK lazy_or[p] = 0 p >>= 1 while p: left = p << 1 right = left | 1 if not saved[p]: save(p) total[p] = total[left] + total[right] packed[p] = packed[left] + packed[right] any_bits[p] = any_bits[left] | any_bits[right] all_bits[p] = all_bits[left] & all_bits[right] p >>= 1 return new_value def point_value(index, total=total, lazy_and=lazy_and, lazy_or=lazy_or, size=size): p = 1 left_bound = 0 length = size pending_and = VALUE_MASK pending_or = 0 while length > 1: node_and = lazy_and[p] node_or = lazy_or[p] if pending_and == VALUE_MASK and pending_or == 0: pending_and = node_and pending_or = node_or elif node_and != VALUE_MASK or node_or: old_pending_and = pending_and pending_and = (node_and & old_pending_and) | pending_or pending_or = (node_or & old_pending_and) | pending_or half = length >> 1 middle = left_bound + half if index < middle: p <<= 1 else: p = p << 1 | 1 left_bound = middle length = half return (total[p] & pending_and) | pending_or def range_sum(query_left, query_right, total=total, packed=packed, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, fmlo=fmlo, fmhi=fmhi, low15=low15, eval_mod=eval_mod, size=size): result = 0 p = 1 left_bound = 0 length = size pending_and = VALUE_MASK pending_or = 0 while True: if query_left <= left_bound and left_bound + length <= query_right: if pending_and == VALUE_MASK and pending_or == 0: result += total[p] elif pending_and == pending_or: result += length * pending_or else: clear_bits = any_bits[p] & (VALUE_MASK ^ pending_and) set_bits = pending_or & (VALUE_MASK ^ all_bits[p]) changed = clear_bits | set_bits if changed: field_mask = fmlo[changed & low15] | fmhi[changed >> 15] result += total[p] + length * set_bits - ((packed[p] & field_mask) % eval_mod) else: result += total[p] return result node_and = lazy_and[p] node_or = lazy_or[p] if pending_and == VALUE_MASK and pending_or == 0: child_and = node_and child_or = node_or elif node_and == VALUE_MASK and node_or == 0: child_and = pending_and child_or = pending_or else: child_and = (node_and & pending_and) | pending_or child_or = (node_or & pending_and) | pending_or half = length >> 1 middle = left_bound + half if query_right <= middle: p <<= 1 length = half pending_and = child_and pending_or = child_or continue if query_left >= middle: p = p << 1 | 1 left_bound = middle length = half pending_and = child_and pending_or = child_or continue # Left suffix [query_left, middle). branch = p << 1 branch_left = left_bound branch_length = half branch_and = child_and branch_or = child_or while True: if query_left <= branch_left: if branch_and == VALUE_MASK and branch_or == 0: result += total[branch] elif branch_and == branch_or: result += branch_length * branch_or else: clear_bits = any_bits[branch] & (VALUE_MASK ^ branch_and) set_bits = branch_or & (VALUE_MASK ^ all_bits[branch]) changed = clear_bits | set_bits if changed: field_mask = fmlo[changed & low15] | fmhi[changed >> 15] result += total[branch] + branch_length * set_bits - ((packed[branch] & field_mask) % eval_mod) else: result += total[branch] break node_and = lazy_and[branch] node_or = lazy_or[branch] if branch_and == VALUE_MASK and branch_or == 0: next_and = node_and next_or = node_or elif node_and == VALUE_MASK and node_or == 0: next_and = branch_and next_or = branch_or else: next_and = (node_and & branch_and) | branch_or next_or = (node_or & branch_and) | branch_or branch_half = branch_length >> 1 branch_middle = branch_left + branch_half if query_left >= branch_middle: branch = branch << 1 | 1 branch_left = branch_middle branch_length = branch_half branch_and = next_and branch_or = next_or else: sibling = branch << 1 | 1 if next_and == VALUE_MASK and next_or == 0: result += total[sibling] elif next_and == next_or: result += branch_half * next_or else: clear_bits = any_bits[sibling] & (VALUE_MASK ^ next_and) set_bits = next_or & (VALUE_MASK ^ all_bits[sibling]) changed = clear_bits | set_bits if changed: field_mask = fmlo[changed & low15] | fmhi[changed >> 15] result += total[sibling] + branch_half * set_bits - ((packed[sibling] & field_mask) % eval_mod) else: result += total[sibling] branch <<= 1 branch_length = branch_half branch_and = next_and branch_or = next_or # Right prefix [middle, query_right). branch = p << 1 | 1 branch_left = middle branch_length = half branch_and = child_and branch_or = child_or while True: if branch_left + branch_length <= query_right: if branch_and == VALUE_MASK and branch_or == 0: result += total[branch] elif branch_and == branch_or: result += branch_length * branch_or else: clear_bits = any_bits[branch] & (VALUE_MASK ^ branch_and) set_bits = branch_or & (VALUE_MASK ^ all_bits[branch]) changed = clear_bits | set_bits if changed: field_mask = fmlo[changed & low15] | fmhi[changed >> 15] result += total[branch] + branch_length * set_bits - ((packed[branch] & field_mask) % eval_mod) else: result += total[branch] break node_and = lazy_and[branch] node_or = lazy_or[branch] if branch_and == VALUE_MASK and branch_or == 0: next_and = node_and next_or = node_or elif node_and == VALUE_MASK and node_or == 0: next_and = branch_and next_or = branch_or else: next_and = (node_and & branch_and) | branch_or next_or = (node_or & branch_and) | branch_or branch_half = branch_length >> 1 branch_middle = branch_left + branch_half if query_right <= branch_middle: branch <<= 1 branch_length = branch_half branch_and = next_and branch_or = next_or else: sibling = branch << 1 if next_and == VALUE_MASK and next_or == 0: result += total[sibling] elif next_and == next_or: result += branch_half * next_or else: clear_bits = any_bits[sibling] & (VALUE_MASK ^ next_and) set_bits = next_or & (VALUE_MASK ^ all_bits[sibling]) changed = clear_bits | set_bits if changed: field_mask = fmlo[changed & low15] | fmhi[changed >> 15] result += total[sibling] + branch_half * set_bits - ((packed[sibling] & field_mask) % eval_mod) else: result += total[sibling] branch = branch << 1 | 1 branch_left = branch_middle branch_length = branch_half branch_and = next_and branch_or = next_or return result def begin(): history.clear() def rollback(total=total, packed=packed, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved=saved, initial_total=initial_total, initial_packed=initial_packed, initial_any=initial_any, initial_all=initial_all, history=history): for p in history: total[p] = initial_total[p] packed[p] = initial_packed[p] any_bits[p] = initial_any[p] all_bits[p] = initial_all[p] lazy_and[p] = VALUE_MASK lazy_or[p] = 0 saved[p] = 0 history.clear() return (size, begin, rollback, point_set, point_value, range_and, range_or, range_sum) def main(): (n, m, initial, left_data, right_data, mask_data, sum_left_data, sum_right_data, problem_count, starts, query_counts) = parse_input() (size, begin, rollback, point_set, point_value, range_and, range_or, range_sum) = build_tree(initial) # Multi-point overlay storage. The overwhelmingly common one-point case # stays entirely in scalar locals and never touches this dictionary/Fenwick tree. pending = {} fenwick = [0] * (n + 1) fenwick_seen = bytearray(n + 1) fenwick_touched = [] fenwick_touched_append = fenwick_touched.append pending_limit = 64 def fenwick_add(index, delta, fenwick=fenwick, fenwick_seen=fenwick_seen, fenwick_touched_append=fenwick_touched_append, n=n): index += 1 while index <= n: if not fenwick_seen[index]: fenwick_seen[index] = 1 fenwick_touched_append(index) fenwick[index] += delta index += index & -index def fenwick_range(left, right, fenwick=fenwick): a = 0 i = left while i: a += fenwick[i] i &= i - 1 b = 0 i = right while i: b += fenwick[i] i &= i - 1 return b - a def clear_multi(pending=pending, fenwick=fenwick, fenwick_seen=fenwick_seen, fenwick_touched=fenwick_touched): pending.clear() for i in fenwick_touched: fenwick[i] = 0 fenwick_seen[i] = 0 fenwick_touched.clear() output = [] output_append = output.append write = sys.stdout.write problem_index = 0 while problem_index < problem_count: begin() y = problem_index + 1 query_count = query_counts[problem_index] z = ((starts[problem_index] + 1) % m) + 1 multi = False single_index = -1 single_base = 0 single_value = 0 while query_count: u = left_data[z] ^ y if u < 1: u = 1 elif u > n: u = n v = right_data[z] ^ y if v < 1: v = 1 elif v > n: v = n if u <= v: update_left = u - 1 update_right = v else: update_left = v - 1 update_right = u u = sum_left_data[z] ^ y if u < 1: u = 1 elif u > n: u = n v = sum_right_data[z] ^ y if v < 1: v = 1 elif v > n: v = n if u <= v: sum_left = u - 1 sum_right = v else: sum_left = v - 1 sum_right = u update_mask = (mask_data[z] ^ y) & VALUE_MASK if update_right - update_left == 1: index = update_left if not multi: if index == single_index: old_value = single_value elif single_index < 0: base_value = point_value(index) single_index = index single_base = base_value single_value = base_value old_value = base_value else: pair = [single_base, single_value] pending[single_index] = pair delta = single_value - single_base if delta: fenwick_add(single_index, delta) multi = True base_value = point_value(index) pair = [base_value, base_value] pending[index] = pair old_value = base_value if z & 1: new_value = old_value & update_mask else: new_value = old_value | update_mask if new_value != old_value: if multi: pair[1] = new_value fenwick_add(index, new_value - old_value) else: single_value = new_value else: pair = pending.get(index) if pair is None: if len(pending) >= pending_limit: for flush_index, flush_pair in pending.items(): point_set(flush_index, flush_pair[1]) clear_multi() multi = False base_value = point_value(index) single_index = index single_base = base_value single_value = base_value old_value = base_value if z & 1: new_value = old_value & update_mask else: new_value = old_value | update_mask if new_value != old_value: single_value = new_value else: base_value = point_value(index) pair = [base_value, base_value] pending[index] = pair old_value = base_value if z & 1: new_value = old_value & update_mask else: new_value = old_value | update_mask if new_value != old_value: pair[1] = new_value fenwick_add(index, new_value - old_value) else: old_value = pair[1] if z & 1: new_value = old_value & update_mask else: new_value = old_value | update_mask if new_value != old_value: pair[1] = new_value fenwick_add(index, new_value - old_value) else: if z & 1: range_and(update_left, update_right, update_mask) if multi: for index, pair in pending.items(): if update_left <= index < update_right: old_base = pair[0] old_value = pair[1] new_base = old_base & update_mask new_value = old_value & update_mask if new_base != old_base or new_value != old_value: pair[0] = new_base pair[1] = new_value delta_change = (new_value - new_base) - (old_value - old_base) if delta_change: fenwick_add(index, delta_change) elif single_index >= 0 and update_left <= single_index < update_right: single_base &= update_mask single_value &= update_mask else: range_or(update_left, update_right, update_mask) if multi: for index, pair in pending.items(): if update_left <= index < update_right: old_base = pair[0] old_value = pair[1] new_base = old_base | update_mask new_value = old_value | update_mask if new_base != old_base or new_value != old_value: pair[0] = new_base pair[1] = new_value delta_change = (new_value - new_base) - (old_value - old_base) if delta_change: fenwick_add(index, delta_change) elif single_index >= 0 and update_left <= single_index < update_right: single_base |= update_mask single_value |= update_mask if sum_right - sum_left == 1: if multi: pair = pending.get(sum_left) if pair is None: y = point_value(sum_left) & VALUE_MASK else: y = pair[1] & VALUE_MASK elif sum_left == single_index: y = single_value & VALUE_MASK else: y = point_value(sum_left) & VALUE_MASK else: y = range_sum(sum_left, sum_right) if multi: y += fenwick_range(sum_left, sum_right) elif single_index >= sum_left and single_index < sum_right: y += single_value - single_base y &= VALUE_MASK z += 1 if z > m: z = 1 query_count -= 1 if multi: clear_multi() output_append(str(y)) rollback() if len(output) == 4096: write("\n".join(output) + "\n") output.clear() problem_index += 1 if output: write("\n".join(output) + "\n") if __name__ == "__main__": main()