<p>You are given an array <code>nums</code> of <code>n</code> integers, and a 2D integer array <code>queries</code> of size <code>q</code>, where <code>queries[i] = [l<sub>i</sub>, r<sub>i</sub>]</code>.</p>

<p>For each query, you must find the <strong>maximum XOR score</strong> of any <span data-keyword="subarray">subarray</span> of <code>nums[l<sub>i</sub>..r<sub>i</sub>]</code>.</p>

<p>The <strong>XOR score</strong> of an array <code>a</code> is found by repeatedly applying the following operations on <code>a</code> so that only one element remains, that is the <strong>score</strong>:</p>

<ul>
	<li>Simultaneously replace <code>a[i]</code> with <code>a[i] XOR a[i + 1]</code> for all indices <code>i</code> except the last one.</li>
	<li>Remove the last element of <code>a</code>.</li>
</ul>

<p>Return an array <code>answer</code> of size <code>q</code> where <code>answer[i]</code> is the answer to query <code>i</code>.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[12,60,60]</span></p>

<p><strong>Explanation:</strong></p>

<p>In the first query, <code>nums[0..2]</code> has 6 subarrays <code>[2]</code>, <code>[8]</code>, <code>[4]</code>, <code>[2, 8]</code>, <code>[8, 4]</code>, and <code>[2, 8, 4]</code> each with a respective XOR score of 2, 8, 4, 10, 12, and 6. The answer for the query is 12, the largest of all XOR scores.</p>

<p>In the second query, the subarray of <code>nums[1..4]</code> with the largest XOR score is <code>nums[1..4]</code> with a score of 60.</p>

<p>In the third query, the subarray of <code>nums[0..5]</code> with the largest XOR score is <code>nums[1..4]</code> with a score of 60.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [0,7,3,2,8,5,1], queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[7,14,11,14,5]</span></p>

<p><strong>Explanation:</strong></p>

<table height="70" width="472">
	<thead>
		<tr>
			<th>Index</th>
			<th>nums[l<sub>i</sub>..r<sub>i</sub>]</th>
			<th>Maximum XOR Score Subarray</th>
			<th>Maximum Subarray XOR Score</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>0</td>
			<td>[0, 7, 3, 2]</td>
			<td>[7]</td>
			<td>7</td>
		</tr>
		<tr>
			<td>1</td>
			<td>[7, 3, 2, 8, 5]</td>
			<td>[7, 3, 2, 8]</td>
			<td>14</td>
		</tr>
		<tr>
			<td>2</td>
			<td>[3, 2, 8]</td>
			<td>[3, 2, 8]</td>
			<td>11</td>
		</tr>
		<tr>
			<td>3</td>
			<td>[3, 2, 8, 5, 1]</td>
			<td>[2, 8, 5, 1]</td>
			<td>14</td>
		</tr>
		<tr>
			<td>4</td>
			<td>[5, 1]</td>
			<td>[5]</td>
			<td>5</td>
		</tr>
	</tbody>
</table>
</div>

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

<ul>
	<li><code>1 &lt;= n == nums.length &lt;= 2000</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>1 &lt;= q == queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>queries[i].length == 2 </code></li>
	<li><code>queries[i] = [l<sub>i</sub>, r<sub>i</sub>]</code></li>
	<li><code>0 &lt;= l<sub>i</sub> &lt;= r<sub>i</sub> &lt;= n - 1</code></li>
</ul>

def bit_ceil(n):
    x = 1
    while x < n: x *= 2
    return x

def countr_zero(n):
    for i in range(32):
        if n & 1 << i:
            return i
    return 32

class Segtree:
    def __init__(self, v):
        n = len(v)
        self._n = n
        self.size = bit_ceil(n)
        self.log = countr_zero(self.size)
        self.d = [e() for _ in range(2 * self.size)]
        for i in range(n):
            self.d[self.size + i] = v[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def _psh(self, p):
        for i in range(self.log, 0, -1):
            self.push(p >> i)

    def _upd(self, p):
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def set(self, p, x):
        assert 0 <= p and p < self._n
        p += self.size
        self.d[p] = x
        self._upd(p)

    def get(self, p):
        assert 0 <= p and p < self._n
        return self.d[p + self.size]

    def prod(self, l, r):
        # assert 0 <= l and l <= r and r <= self._n
        l = max(l, 0)
        r = min(r, self._n)
        
        if l >= r: return e()
        l += self.size
        r += self.size
        sml, smr = e(), e()
        while l < r:
            if l & 1:
                sml = op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = op(self.d[r], smr)
            l >>= 1
            r >>= 1

        return op(sml, smr)
    
    def all_prod(self):
        return self.d[1]

    # maximum i s.t. g(a[l]...a[i]) == True
    def max_right(self, l, g):
        assert 0 <= l and l <= self._n
        assert g(e())
        if l == self._n: return self._n
        l += self.size
        sm = e()
        while True:
            while l % 2 == 0: l >>= 1
            if not g(op(sm, self.d[l])):
                while l < self.size:
                    l = 2 * l
                    if g(op(sm, self.d[l])):
                        sm = op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = op(sm, self.d[l])
            l += 1
            if l & -l == l:
                break
        return self._n

    # minimum i s.t. g(a[i]...a[r - 1]) == True
    def min_left(self, r, g):
        assert 0 <= r and r <= self._n
        assert g(e())
        if r == 0: return 0
        r += self.size
        sm = e()
        while True:
            r -= 1
            while r > 1 and r % 2: r >>= 1
            if not g(op(self.d[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if g(op(self.d[r], sm)):
                        sm = op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = op(self.d[r], sm)
            if r & -r == r:
                break
        return 0

    def update(self, k):
        self.d[k] = op(self.d[2 * k], self.d[2 * k + 1])

def op(l, r):
    return max(l, r)

def e():
    return 0

class Solution:
    def maximumSubarrayXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        R = len(nums)
        tree = Segtree([0] * R)
        l = [nums[:]]
        while len(l[-1]) != 1:
            q = []
            for i in range(len(l[-1])-1):
                q.append(l[-1][i] ^ l[-1][i+1])
            l.append(q)
        d = defaultdict(list)
        for i in range(len(l)):
            for st in range(len(l[i])):
                ed = st + i
                d[ed].append((st, l[i][st]))
        ans = {}
        qs = sorted(queries, key=lambda x:x[1])
        lst = -1
        val = [0] * R
        for x, y in qs:
            while lst < y:
                lst += 1
                for a, b in d[lst]:
                    if val[a] < b:
                        val[a] = b
                        tree.set(a, val[a])
            ans[x, y] = tree.prod(x, y+1)
        return [ans[x, y] for (x, y) in queries]
263216