<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 segtree():
    def __init__(self, n, nums):
        self.lazy = defaultdict(int)
        self.len = defaultdict(int)
        self.tree = defaultdict(int)
        # initial length and summation
        self.init_len(1, 0, n, 0, n, nums)
        self.init_num(1, 0, n, 0, n, nums)
        
    def init_len(self, ind, ul, ur, cl, cr, num):
        if cr < cl or cl >= len(num):
            return 0
        if cr == cl:
            self.len[ind] = 1
            return 1
        mid = (cl + cr) // 2
        if cl != cr:
            self.init_len(ind*2, ul, ur, cl, mid, num)
        self.init_len(ind*2+1, ul, ur, mid+1, cr, num)
        self.len[ind] = self.len[ind*2] + self.len[ind*2+1]
    
    def init_num(self, ind, ul, ur, cl, cr, num):
        if cr < cl or cl >= len(num):
            return
        if cl == cr:
            self.tree[ind] = num[cl]
            return
        mid = (cl + cr) // 2
        if cl != cr:
            self.init_num(ind*2, ul, ur, cl, mid, num)
        self.init_num(ind*2+1, ul, ur, mid+1, cr, num)
        
        self.tree[ind] = self.tree[ind*2] + self.tree[ind*2+1]
        
    
    def proplazy(self, ind):
        # if the parent node has the notation to flip, then we update all summation of children nodes.
        if self.lazy[ind]:
            self.lazy[ind*2] ^= self.lazy[ind]
            self.tree[ind*2] = self.len[ind*2] - self.tree[ind*2]
            self.lazy[ind*2 + 1] ^= self.lazy[ind]
            self.tree[ind*2 + 1] = self.len[ind*2+1] - self.tree[ind*2 + 1]
            self.tree[ind] = self.tree[ind*2] + self.tree[ind*2+1]
            self.lazy[ind] = 0
        
    def update(self, ind, ul, ur, cl, cr):
        if cl > ur or cr < ul:
            return 
        if ul <= cl and cr <= ur:
            # mark to flip
            self.lazy[ind] ^= 1
            self.tree[ind] = self.len[ind] - self.tree[ind]
        else:
            mid = (cl + cr) // 2
            self.proplazy(ind)
            self.update(ind*2, ul, ur, cl, mid)
            self.update(ind*2+1, ul, ur, mid+1, cr)
            self.tree[ind] = self.tree[ind*2] + self.tree[ind*2+1]
           
    def query(self, ind, ul, ur, cl, cr):
        if cl > ur or cr < ul:
            return 0
        if ul <= cl and cr <= ur:
            return self.tree[ind]
        else:
            mid = (cl + cr) // 2
            self.proplazy(ind)
            return self.query(ind*2, ul, ur, cl, mid) + self.query(ind*2+1, ul, ur, mid+1, cr)
         
class Solution:
    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        seg = segtree(len(nums1) + 10, nums1)
        anss = []
        ans = sum(nums2)
        n = len(nums1) + 10
        for i, j, k in queries:
            if i == 1:
                seg.update(1, j, k, 0, n)
            if i == 2:
                ans += seg.tree[1] * j
            if i == 3:
                anss.append(ans)
        return anss
79400