<p>You are given a 2D <code>matrix</code> of size <code>m x n</code>, consisting of non-negative integers. You are also given an integer <code>k</code>.</p>

<p>The <strong>value</strong> of coordinate <code>(a, b)</code> of the matrix is the XOR of all <code>matrix[i][j]</code> where <code>0 &lt;= i &lt;= a &lt; m</code> and <code>0 &lt;= j &lt;= b &lt; n</code> <strong>(0-indexed)</strong>.</p>

<p>Find the <code>k<sup>th</sup></code> largest value <strong>(1-indexed)</strong> of all the coordinates of <code>matrix</code>.</p>

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

<pre>
<strong>Input:</strong> matrix = [[5,2],[1,6]], k = 1
<strong>Output:</strong> 7
<strong>Explanation:</strong> The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.
</pre>

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

<pre>
<strong>Input:</strong> matrix = [[5,2],[1,6]], k = 2
<strong>Output:</strong> 5
<strong>Explanation:</strong> The value of coordinate (0,0) is 5 = 5, which is the 2nd largest value.
</pre>

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

<pre>
<strong>Input:</strong> matrix = [[5,2],[1,6]], k = 3
<strong>Output:</strong> 4
<strong>Explanation:</strong> The value of coordinate (1,0) is 5 XOR 1 = 4, which is the 3rd largest value.</pre>

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

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 1000</code></li>
	<li><code>0 &lt;= matrix[i][j] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= k &lt;= m * n</code></li>
</ul>

class Solution:
    def quickselect(self, arr, k, low, high):
        """
        select k largest element
        """
        def swap(arr, i, j):
            arr[i], arr[j] = arr[j], arr[i]

        def partition(arr, low, high):
            """
            select last elem as pivot, return the pivot index after rearranged array
            """
            # randomly choose index
            randidx = random.randint(low,high)
            pivot = arr[randidx]
            swap(arr, randidx, high)

            i = low
            for j in range(low, high):
                if arr[j] > pivot:
                    swap(arr, i, j)
                    i += 1

            swap(arr, i, high)
            return i
        
        if low == high:
            return arr[low]

        pivot_idx = partition(arr, low, high)

        if k-1 == pivot_idx:
            return arr[pivot_idx]
        elif k-1 > pivot_idx: 
            return self.quickselect(arr, k, pivot_idx+1, high)
        else:
            return self.quickselect(arr, k, low, pivot_idx-1)

        return quickselect(nums, k, 0, len(nums)-1)
    
    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
        """
        prefix-XOR
        flatten matrix into 1d
        quickselect(k)
        [ ][-][+][ ]
        [ ][+][x][ ]
        [ ][ ][ ][ ]
        [ ][ ][ ][ ]
        """
        nrow, ncol = len(matrix), len(matrix[0])
        prefix_XOR = [[0 for _ in range(ncol)] for _ in range(nrow)] 
        
        # init first row and first col
        prefix_XOR[0][0] = matrix[0][0]
        for i in range(1,ncol):
            prefix_XOR[0][i] = prefix_XOR[0][i-1] ^ matrix[0][i]
        for i in range(1,nrow):
            prefix_XOR[i][0] = prefix_XOR[i-1][0] ^ matrix[i][0]
        # prefix XOR
        for i in range(1,nrow):
            for j in range(1,ncol):
                prefix_XOR[i][j] = matrix[i][j] ^ prefix_XOR[i-1][j] ^ prefix_XOR[i][j-1] ^ prefix_XOR[i-1][j-1]
                
        # flatten 2d matrix into 1d
        flatten = []
        for i in prefix_XOR:
            flatten += i
            
        # quick select k
        # res = self.quickselect(flatten, k, 0, len(flatten)-1) # why quickselect not working? (TLE)
        res = sorted(flatten)[-k] # why built-in sorted() works?
        
        return res
54700