#!/usr/bin/env python3 from array import array import sys BITS = 30 VALUE_MASK = (1 << BITS) - 1 LOW15_MASK = (1 << 15) - 1 _BIT_POS_LO = tuple(tuple(b for b in range(15) if mask & (1 << b)) for mask in range(1 << 15)) _BIT_POS_HI = tuple(tuple(b + 15 for b in bits) for bits in _BIT_POS_LO) def parse_input(): data = sys.stdin.buffer.read() if not data or data[-1] > 32: data += b"\0" i = 0 while data[i] <= 32: i += 1 n = 0 while data[i] > 32: n = n * 10 + data[i] - 48 i += 1 while data[i] <= 32: i += 1 m = 0 while data[i] > 32: m = m * 10 + data[i] - 48 i += 1 def read_array(length, leading_zero=False, data=data): nonlocal i out = array("I", [0]) * (length + leading_zero) j = 1 if leading_zero else 0 end = j + length while j < end: while data[i] <= 32: i += 1 value = 0 while data[i] > 32: value = value * 10 + data[i] - 48 i += 1 out[j] = value j += 1 return out initial = read_array(n) left_data = read_array(m, True) right_data = read_array(m, True) mask_data = read_array(m, True) sum_left_data = read_array(m, True) sum_right_data = read_array(m, True) while data[i] <= 32: i += 1 problem_count = 0 while data[i] > 32: problem_count = problem_count * 10 + data[i] - 48 i += 1 starts = array("I", [0]) * problem_count counts = array("I", [0]) * problem_count k = 0 while k < problem_count: while data[i] <= 32: i += 1 value = 0 while data[i] > 32: value = value * 10 + data[i] - 48 i += 1 starts[k] = value while data[i] <= 32: i += 1 value = 0 while data[i] > 32: value = value * 10 + data[i] - 48 i += 1 counts[k] = value k += 1 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 total = array("Q", [0]) * nodes counts = [array("I", [0]) * nodes for _ in range(BITS)] any_bits = array("I", [0]) * nodes all_bits = array("I", [0]) * nodes lazy_and = array("I", [VALUE_MASK]) * nodes lazy_or = array("I", [0]) * nodes saved_epoch = array("I", [0]) * nodes base = size bit_pos_lo = _BIT_POS_LO bit_pos_hi = _BIT_POS_HI low15 = LOW15_MASK for i, value in enumerate(values): p = base + i total[p] = value any_bits[p] = value all_bits[p] = value for b in bit_pos_lo[value & low15]: counts[b][p] = 1 for b in bit_pos_hi[value >> 15]: counts[b][p] = 1 for p in range(size - 1, 0, -1): left = p << 1 right = left | 1 total[p] = total[left] + total[right] any_bits[p] = any_bits[left] | any_bits[right] all_bits[p] = all_bits[left] & all_bits[right] node_range = range(size - 1, 0, -1) for bit_counts in counts: for p in node_range: left = p << 1 bit_counts[p] = bit_counts[left] + bit_counts[left | 1] hist_index = [] hist_total = [] hist_any = [] hist_all = [] hist_lazy_and = [] hist_lazy_or = [] hist_counts = [] hi_append = hist_index.append ht_append = hist_total.append ha_append = hist_any.append hall_append = hist_all.append hla_append = hist_lazy_and.append hlo_append = hist_lazy_or.append hist_count_append = hist_counts.append def save_full(p, epoch, total=total, counts=counts, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved_epoch=saved_epoch, hi_append=hi_append, ht_append=ht_append, ha_append=ha_append, hall_append=hall_append, hla_append=hla_append, hlo_append=hlo_append, hist_count_append=hist_count_append): saved_epoch[p] = epoch hi_append(p) ht_append(total[p]) ha_append(any_bits[p]) hall_append(all_bits[p]) hla_append(lazy_and[p]) hlo_append(lazy_or[p]) c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25, c26, c27, c28, c29 = counts hist_count_append(c0[p]) hist_count_append(c1[p]) hist_count_append(c2[p]) hist_count_append(c3[p]) hist_count_append(c4[p]) hist_count_append(c5[p]) hist_count_append(c6[p]) hist_count_append(c7[p]) hist_count_append(c8[p]) hist_count_append(c9[p]) hist_count_append(c10[p]) hist_count_append(c11[p]) hist_count_append(c12[p]) hist_count_append(c13[p]) hist_count_append(c14[p]) hist_count_append(c15[p]) hist_count_append(c16[p]) hist_count_append(c17[p]) hist_count_append(c18[p]) hist_count_append(c19[p]) hist_count_append(c20[p]) hist_count_append(c21[p]) hist_count_append(c22[p]) hist_count_append(c23[p]) hist_count_append(c24[p]) hist_count_append(c25[p]) hist_count_append(c26[p]) hist_count_append(c27[p]) hist_count_append(c28[p]) hist_count_append(c29[p]) def push_nonidentity(p, half, epoch, parent_and, parent_or, total=total, counts=counts, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved_epoch=saved_epoch, bit_pos_lo=bit_pos_lo, bit_pos_hi=bit_pos_hi, low15=low15, save_full=save_full): child = p << 1 child_and = lazy_and[child] child_or = lazy_or[child] new_and = (child_and & parent_and) | parent_or new_or = (child_or & parent_and) | parent_or 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 or new_and != child_and or new_or != child_or: if saved_epoch[child] != epoch: save_full(child, epoch) value = total[child] for b in bit_pos_lo[clear_bits & low15]: bit_counts = counts[b] value -= bit_counts[child] << b bit_counts[child] = 0 for b in bit_pos_hi[clear_bits >> 15]: bit_counts = counts[b] value -= bit_counts[child] << b bit_counts[child] = 0 for b in bit_pos_lo[set_bits & low15]: bit_counts = counts[b] old_count = bit_counts[child] value += (half - old_count) << b bit_counts[child] = half for b in bit_pos_hi[set_bits >> 15]: bit_counts = counts[b] old_count = bit_counts[child] value += (half - old_count) << b bit_counts[child] = half total[child] = value any_bits[child] = (old_any & parent_and) | parent_or all_bits[child] = (old_all & parent_and) | parent_or lazy_and[child] = new_and lazy_or[child] = new_or child = (p << 1) | 1 child_and = lazy_and[child] child_or = lazy_or[child] new_and = (child_and & parent_and) | parent_or new_or = (child_or & parent_and) | parent_or 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 or new_and != child_and or new_or != child_or: if saved_epoch[child] != epoch: save_full(child, epoch) value = total[child] for b in bit_pos_lo[clear_bits & low15]: bit_counts = counts[b] value -= bit_counts[child] << b bit_counts[child] = 0 for b in bit_pos_hi[clear_bits >> 15]: bit_counts = counts[b] value -= bit_counts[child] << b bit_counts[child] = 0 for b in bit_pos_lo[set_bits & low15]: bit_counts = counts[b] old_count = bit_counts[child] value += (half - old_count) << b bit_counts[child] = half for b in bit_pos_hi[set_bits >> 15]: bit_counts = counts[b] old_count = bit_counts[child] value += (half - old_count) << b bit_counts[child] = half total[child] = value any_bits[child] = (old_any & parent_and) | parent_or all_bits[child] = (old_all & parent_and) | parent_or lazy_and[child] = new_and lazy_or[child] = new_or lazy_and[p] = VALUE_MASK lazy_or[p] = 0 def range_and(p, left_bound, length, query_left, query_right, mask, epoch, total=total, counts=counts, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved_epoch=saved_epoch, bit_pos_lo=bit_pos_lo, bit_pos_hi=bit_pos_hi, low15=low15, push_nonidentity=push_nonidentity, save_full=save_full): if query_left <= left_bound and left_bound + length <= query_right: changed = any_bits[p] & (VALUE_MASK ^ mask) if not changed: return 0 if saved_epoch[p] != epoch: save_full(p, epoch) value = total[p] for b in bit_pos_lo[changed & low15]: bit_counts = counts[b] value -= bit_counts[p] << b bit_counts[p] = 0 for b in bit_pos_hi[changed >> 15]: bit_counts = counts[b] value -= bit_counts[p] << b bit_counts[p] = 0 total[p] = value any_bits[p] &= mask all_bits[p] &= mask lazy_and[p] &= mask lazy_or[p] &= mask return changed half = length >> 1 parent_and = lazy_and[p] parent_or = lazy_or[p] if parent_and != VALUE_MASK or parent_or: push_nonidentity(p, half, epoch, parent_and, parent_or) middle = left_bound + half if query_right <= middle: changed = range_and(p << 1, left_bound, half, query_left, query_right, mask, epoch) elif query_left >= middle: changed = range_and(p << 1 | 1, middle, half, query_left, query_right, mask, epoch) else: changed = range_and(p << 1, left_bound, half, query_left, query_right, mask, epoch) changed |= range_and(p << 1 | 1, middle, half, query_left, query_right, mask, epoch) if changed: if saved_epoch[p] != epoch: save_full(p, epoch) left = p << 1 right = left | 1 for b in bit_pos_lo[changed & low15]: bit_counts = counts[b] bit_counts[p] = bit_counts[left] + bit_counts[right] for b in bit_pos_hi[changed >> 15]: bit_counts = counts[b] bit_counts[p] = bit_counts[left] + bit_counts[right] total[p] = total[left] + total[right] any_bits[p] = any_bits[left] | any_bits[right] all_bits[p] = all_bits[left] & all_bits[right] return changed def range_or(p, left_bound, length, query_left, query_right, mask, epoch, total=total, counts=counts, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, saved_epoch=saved_epoch, bit_pos_lo=bit_pos_lo, bit_pos_hi=bit_pos_hi, low15=low15, push_nonidentity=push_nonidentity, save_full=save_full): if query_left <= left_bound and left_bound + length <= query_right: changed = mask & (VALUE_MASK ^ all_bits[p]) if not changed: return 0 if saved_epoch[p] != epoch: save_full(p, epoch) value = total[p] for b in bit_pos_lo[changed & low15]: bit_counts = counts[b] old_count = bit_counts[p] value += (length - old_count) << b bit_counts[p] = length for b in bit_pos_hi[changed >> 15]: bit_counts = counts[b] old_count = bit_counts[p] value += (length - old_count) << b bit_counts[p] = length total[p] = value any_bits[p] |= mask all_bits[p] |= mask lazy_and[p] |= mask lazy_or[p] |= mask return changed half = length >> 1 parent_and = lazy_and[p] parent_or = lazy_or[p] if parent_and != VALUE_MASK or parent_or: push_nonidentity(p, half, epoch, parent_and, parent_or) middle = left_bound + half if query_right <= middle: changed = range_or(p << 1, left_bound, half, query_left, query_right, mask, epoch) elif query_left >= middle: changed = range_or(p << 1 | 1, middle, half, query_left, query_right, mask, epoch) else: changed = range_or(p << 1, left_bound, half, query_left, query_right, mask, epoch) changed |= range_or(p << 1 | 1, middle, half, query_left, query_right, mask, epoch) if changed: if saved_epoch[p] != epoch: save_full(p, epoch) left = p << 1 right = left | 1 for b in bit_pos_lo[changed & low15]: bit_counts = counts[b] bit_counts[p] = bit_counts[left] + bit_counts[right] for b in bit_pos_hi[changed >> 15]: bit_counts = counts[b] bit_counts[p] = bit_counts[left] + bit_counts[right] total[p] = total[left] + total[right] any_bits[p] = any_bits[left] | any_bits[right] all_bits[p] = all_bits[left] & all_bits[right] return changed def range_sum(p, left_bound, length, query_left, query_right, pending_and=VALUE_MASK, pending_or=0, total=total, counts=counts, any_bits=any_bits, all_bits=all_bits, lazy_and=lazy_and, lazy_or=lazy_or, bit_pos_lo=bit_pos_lo, bit_pos_hi=bit_pos_hi, low15=low15): if query_left <= left_bound and left_bound + length <= query_right: if pending_and == VALUE_MASK and pending_or == 0: return total[p] if pending_and == pending_or: return length * pending_or value = total[p] clear_bits = any_bits[p] & (VALUE_MASK ^ pending_and) set_bits = pending_or & (VALUE_MASK ^ all_bits[p]) for b in bit_pos_lo[clear_bits & low15]: value -= counts[b][p] << b for b in bit_pos_hi[clear_bits >> 15]: value -= counts[b][p] << b for b in bit_pos_lo[set_bits & low15]: value += (length - counts[b][p]) << b for b in bit_pos_hi[set_bits >> 15]: value += (length - counts[b][p]) << b return value node_and = lazy_and[p] node_or = lazy_or[p] child_pending_and = (node_and & pending_and) | pending_or child_pending_or = (node_or & pending_and) | pending_or half = length >> 1 middle = left_bound + half if query_right <= middle: return range_sum(p << 1, left_bound, half, query_left, query_right, child_pending_and, child_pending_or) if query_left >= middle: return range_sum(p << 1 | 1, middle, half, query_left, query_right, child_pending_and, child_pending_or) return (range_sum(p << 1, left_bound, half, query_left, query_right, child_pending_and, child_pending_or) + range_sum(p << 1 | 1, middle, half, query_left, query_right, child_pending_and, child_pending_or)) def begin(): hist_index.clear() hist_total.clear() hist_any.clear() hist_all.clear() hist_lazy_and.clear() hist_lazy_or.clear() hist_counts.clear() def rollback(): for p, old_total, old_any, old_all, old_and, old_or in zip( hist_index, hist_total, hist_any, hist_all, hist_lazy_and, hist_lazy_or): total[p] = old_total any_bits[p] = old_any all_bits[p] = old_all lazy_and[p] = old_and lazy_or[p] = old_or c0, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19, c20, c21, c22, c23, c24, c25, c26, c27, c28, c29 = counts k = 0 for p in hist_index: c0[p] = hist_counts[k + 0] c1[p] = hist_counts[k + 1] c2[p] = hist_counts[k + 2] c3[p] = hist_counts[k + 3] c4[p] = hist_counts[k + 4] c5[p] = hist_counts[k + 5] c6[p] = hist_counts[k + 6] c7[p] = hist_counts[k + 7] c8[p] = hist_counts[k + 8] c9[p] = hist_counts[k + 9] c10[p] = hist_counts[k + 10] c11[p] = hist_counts[k + 11] c12[p] = hist_counts[k + 12] c13[p] = hist_counts[k + 13] c14[p] = hist_counts[k + 14] c15[p] = hist_counts[k + 15] c16[p] = hist_counts[k + 16] c17[p] = hist_counts[k + 17] c18[p] = hist_counts[k + 18] c19[p] = hist_counts[k + 19] c20[p] = hist_counts[k + 20] c21[p] = hist_counts[k + 21] c22[p] = hist_counts[k + 22] c23[p] = hist_counts[k + 23] c24[p] = hist_counts[k + 24] c25[p] = hist_counts[k + 25] c26[p] = hist_counts[k + 26] c27[p] = hist_counts[k + 27] c28[p] = hist_counts[k + 28] c29[p] = hist_counts[k + 29] k += 30 return size, begin, rollback, 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, range_and, range_or, range_sum = build_tree(initial) output = [] output_append = output.append write = sys.stdout.write epoch = 0 problem_index = 0 while problem_index < problem_count: epoch += 1 begin() y = problem_index + 1 query_count = query_counts[problem_index] z = ((starts[problem_index] + 1) % m) + 1 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 z & 1: range_and(1, 0, size, update_left, update_right, update_mask, epoch) else: range_or(1, 0, size, update_left, update_right, update_mask, epoch) y = range_sum(1, 0, size, sum_left, sum_right) & VALUE_MASK z += 1 if z > m: z = 1 query_count -= 1 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()