<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 MyNode:
    def __init__(self, stt, end, ct=0, left: 'MyNode' = None, right: 'MyNode' = None):
        self.stt = stt
        self.end = end
        self.ct = 0
        self.left = left
        self.right = right
        self.child_same_sign = 1
    
    def flip(self, stt=None, end=None):
        #print(f'stt is {stt}, end is {end} ({self.stt}, {self.end})')
        stt = self.stt if stt is None else stt
        end = self.end if end is None else end

        if stt == self.stt and end == self.end:
            self.ct = end - stt + 1 - self.ct
            if self.stt < self.end:
                self.child_same_sign *= -1
            return
        
        if self.child_same_sign < 0:
            self.left.flip()
            self.right.flip()
            self.child_same_sign *= -1
        
        if stt <= self.left.end:
            self.left.flip(max(stt, self.stt), min(self.left.end, end))
        if end >= self.right.stt:
            self.right.flip(max(self.right.stt, stt), min(end, self.end))
        self.ct = self.left.ct + self.right.ct

class Solution:
    def build_tree(self, nd):
        if nd.stt == nd.end:
            nd.ct = self.nums1[nd.stt]
            return
        
        mid = (nd.stt + nd.end) // 2
        nd.left = MyNode(nd.stt, mid)
        nd.right = MyNode(mid+1, nd.end)
        self.build_tree(nd.left)
        self.build_tree(nd.right)
        nd.ct = nd.left.ct + nd.right.ct

    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        self.nums1 = nums1
        self.root = MyNode(0, len(nums1)-1)
        self.build_tree(self.root)
        #print(self.root.ct)

        sm2 = sum(nums2)
        add1 = 0
        rst = []
        for tp, l, r in queries:
            if tp == 1:
                self.root.flip(l, r)
            elif tp == 2:
                add1 += l * self.root.ct
            else:
                rst.append(sm2 + add1)
        return rst
70300