<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 kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
        m,n=len(matrix),len(matrix[0])
        dp=[[0 for j in range(n)] for i in range(m)]
        mnhp=[]
        #xor_vl=[]

        for i in range(m):
            for j in range(n):
                dp[i][j]=matrix[i][j]

                if i>0:
                    dp[i][j]^=dp[i-1][j]
                if j>0:
                    dp[i][j]^=dp[i][j-1]
                if i>0 and j>0:
                    dp[i][j]^=dp[i-1][j-1]
                
                if len(mnhp)<k:
                    heapq.heappush(mnhp,dp[i][j])
                else:
                    heapq.heappushpop(mnhp,dp[i][j])
        
        return mnhp[0]
                #xor_vl.append(dp[i][j])

        #def prtn(lf,rt,pv_ind):
        #    pv=xor_vl[pv_ind]
        #    xor_vl[rt],xor_vl[pv_ind]=xor_vl[pv_ind],xor_vl[rt]
        #    stlf=lf

        #    for i in range(lf,rt):
        #        if xor_vl[i]>pv:
        #            xor_vl[stlf],xor_vl[i]=xor_vl[i],xor_vl[stlf]
        #            stlf+=1

        #    xor_vl[stlf],xor_vl[rt]=xor_vl[rt],xor_vl[stlf]
        #    return stlf

        #def qksl(lf,rt,k):
        #    if lf==rt:
        #        return xor_vl[lf]

        #    pv_ind=random.randint(lf,rt)
        #    pv_ind=prtn(lf,rt,pv_ind)

        #    if k==pv_ind:
        #        return xor_vl[pv_ind]
        #    elif k<pv_ind:
        #        return qksl(lf,pv_ind-1,k)
        #    else:
        #        return qksl(pv_ind+1,rt,k)
        
        #return qksl(0,len(xor_vl)-1,k-1)

41000