<p>You are given two <strong>0-indexed</strong> arrays <code>nums1</code> and <code>nums2</code> and a 2D array <code>queries</code> of queries. There are three types of queries:</p>

<ol>
	<li>For a query of type 1, <code>queries[i]&nbsp;= [1, l, r]</code>. Flip the values from <code>0</code> to <code>1</code> and from <code>1</code> to <code>0</code> in <code>nums1</code>&nbsp;from index <code>l</code> to index <code>r</code>. Both <code>l</code> and <code>r</code> are <strong>0-indexed</strong>.</li>
	<li>For a query of type 2, <code>queries[i]&nbsp;= [2, p, 0]</code>. For every index <code>0 &lt;= i &lt; n</code>, set&nbsp;<code>nums2[i] =&nbsp;nums2[i]&nbsp;+ nums1[i]&nbsp;* p</code>.</li>
	<li>For a query of type 3, <code>queries[i]&nbsp;= [3, 0, 0]</code>. Find the sum of the elements in <code>nums2</code>.</li>
</ol>

<p>Return <em>an array containing all the answers to the third type&nbsp;queries.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]
<strong>Output:</strong> [3]
<strong>Explanation:</strong> After the first query nums1 becomes [1,1,1]. After the second query, nums2 becomes [1,1,1], so the answer to the third query is 3. Thus, [3] is returned.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]
<strong>Output:</strong> [5]
<strong>Explanation:</strong> After the first query, nums2 remains [5], so the answer to the second query is 5. Thus, [5] is returned.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums1.length,nums2.length &lt;= 10<sup>5</sup></code></li>
	<li><code>nums1.length = nums2.length</code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code><font face="monospace">queries[i].length = 3</font></code></li>
	<li><code><font face="monospace">0 &lt;= l &lt;= r &lt;= nums1.length - 1</font></code></li>
	<li><code><font face="monospace">0 &lt;= p &lt;= 10<sup>6</sup></font></code></li>
	<li><code>0 &lt;= nums1[i] &lt;= 1</code></li>
	<li><code>0 &lt;= nums2[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
  def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
    class SegmentTree:
      def __init__(self, nums: List[int]) -> NoReturn:
        self.n = len(nums)
        tree_size = (1 << (ceil(log2(self.n)) + 1)) - 1
        self.tree = [0 for _ in range(tree_size)]
        self.lazy = [False for _ in range(tree_size)]
        self.build_tree(nums, 0, 0, self.n)
      
      def build_tree(self, nums: List[int], node: int, begin: int, end: int) -> NoReturn:
        if end - begin == 1:
          self.tree[node] = nums[begin]
          return
        
        mid = begin + ((end - begin) >> 1)
        left_node = (node << 1) + 1
        right_node = (node << 1) + 2
        
        self.build_tree(nums, left_node, begin, mid)
        self.build_tree(nums, right_node, mid, end)
        self.tree[node] = self.tree[left_node] + self.tree[right_node]
        
      def push_down(self, node: int, begin: int, end: int) -> NoReturn:
        if not self.lazy[node]:
          return
        
        mid = begin + ((end - begin) >> 1)
        left_node = (node << 1) + 1
        right_node = (node << 1) + 2
        
        left_ones = self.tree[left_node]
        left_zeros = mid - begin - left_ones
        self.tree[left_node] = left_zeros
        self.lazy[left_node] = not self.lazy[left_node]
        
        right_ones = self.tree[right_node]
        right_zeros = end - mid - right_ones
        self.tree[right_node] = right_zeros
        self.lazy[right_node] = not self.lazy[right_node]
        
        self.lazy[node] = False
      
      def read(self):
        def read_impl(node: int, begin: int, end: int, left: int, right: int) -> int:
          if left >= end or right <= begin:
            return 0
          
          if left <= begin and end <= right:
            return self.tree[node]
          
          self.push_down(node, begin, end)
          
          mid = begin + ((end - begin) >> 1)
          left_node = (node << 1) + 1
          right_node = (node << 1) + 2
          
          return read_impl(left_node, begin, mid, left, right) + read_impl(right_node, mid, end, left, right)
        
        return read_impl(0, 0, self.n, 0, self.n)
      
      def update(self, left: int, right: int) -> NoReturn:
        def update_impl(node: int, begin: int, end: int, left: int, right: int) -> NoReturn:
          if left >= end or right <= begin:
            return
          
          if left <= begin and end <= right:
            ones = self.tree[node]
            zeros = end - begin - ones
            self.tree[node] = zeros
            self.lazy[node] = not self.lazy[node]
            return
          
          self.push_down(node, begin, end)
          
          mid = begin + ((end - begin) >> 1)
          left_node = (node << 1) + 1
          right_node = (node << 1) + 2
          
          update_impl(left_node, begin, mid, left, right)
          update_impl(right_node, mid, end, left, right)
          self.tree[node] = self.tree[left_node] + self.tree[right_node]
        
        update_impl(0, 0, self.n, left, right)
    
    segment_tree = SegmentTree(nums1)
    s = sum(nums2)
    ret = []
    for t, a, b in queries:
      if t == 1:
        segment_tree.update(a, b + 1)
      elif t == 2:
        s += a * segment_tree.read()
      else:
        ret.append(s)
    return ret

51900