/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    prev := (*ListNode)(nil)
    
    for head != nil {
        next := head.Next
        head.Next = prev
        prev = head
        head = next
    }
    
    return prev
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    if head.Next == nil {
        return head
    }
    
    next := head.Next
    newHead := reverseList(next)
    
    next.Next = head
    head.Next = nil
    
    return newHead
}

func reverseN(head *ListNode, n int) *ListNode {
    oldHead := head
    
    prev := (*ListNode)(nil)
    for i := 0; i < n; i++ {
        next := head.Next
        head.Next = prev
        prev = head
        head = next
    }
    
    newNext := prev
    oldHead.Next = head
    
    return newNext
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if left == 1 {
        return reverseN(head, right-left+1)
    }
    
    h := head
    prev := (*ListNode)(nil)
    for i := 1; i < left; i++ {
        prev = h
        h = h.Next
    }
    
    newPartHead := reverseN(h, right-left+1)
    prev.Next = newPartHead

    return head
}

func reverseN(head *ListNode, n int) *ListNode {
    oldHead := head
    
    prev := (*ListNode)(nil)
    for i := 0; i < n; i++ {
        next := head.Next
        head.Next = prev
        prev = head
        head = next
    }
    
    newNext := prev
    oldHead.Next = head
    
    return newNext
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    l := getListLength(head)
    if l < k {
        return head
    }
    
    newHead := (*ListNode)(nil)
    partHead := head
    prevPartTail := (*ListNode)(nil)
    for l >= k {        
        nextPartHead := reverseN(partHead, k)
        
        if newHead == nil {
            newHead = nextPartHead
        }
        
        if prevPartTail != nil {
            prevPartTail.Next = nextPartHead
        }
        
        partHead = nextPartHead
        for i := 0; i < k; i++ {
            prevPartTail = partHead
            partHead = partHead.Next
        }
        
        l -= k
    }
    
    return newHead
}

func getListLength(head *ListNode) int {
    l := 0
    for head != nil {
        l++
        head = head.Next
    }
    return l
}

func reverseN(head *ListNode, n int) *ListNode {
    oldHead := head
    
    prev := (*ListNode)(nil)
    for i := 0; i < n; i++ {
        next := head.Next
        head.Next = prev
        prev = head
        head = next
    }
    
    newNext := prev
    oldHead.Next = head
    
    return newNext
}

func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)
    pointers := make([]int, n)
    
    result := 0
   
    for i := 0; i < k; i++ {
        minI := -1
        minV := 10_000_000_000
        
        for i, p := range pointers {
            if p < n && matrix[i][p] < minV {
                minI = i
                minV = matrix[i][p]
            }
        }
        
        result = minV
        pointers[minI]++
    }
    
    return result
}

func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)
    
    hv := make(CellHeap, 0, n)
    h := &hv
    for i := 0; i < n; i++ {
        heap.Push(h, Cell{matrix[i][0], i, 0})
    }
    
    result := 0
   
    for i := 0; i < k; i++ {
        cell := heap.Pop(h).(Cell)
        
        result = cell[0]
        if cell[2] < n-1 {
            r := cell[1]
            c := cell[2]+1
            
            heap.Push(h, Cell{matrix[r][c], r, c})
        }
    }
    
    return result
}

type Cell [3]int
type CellHeap []Cell

func (h CellHeap) Len() int { return len(h) }
func (h CellHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h CellHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *CellHeap) Push(x any) { *h = append(*h, x.(Cell)) }
func (h *CellHeap) Pop() any {
    l := h.Len()
    v := (*h)[l-1]
    (*h) = (*h)[:l-1]
    return v
}

func kthSmallest(matrix [][]int, k int) int {
    n := len(matrix)

    L, R := matrix[0][0], matrix[n-1][n-1]
    for L < R {
        mid := L + (R - L) / 2

        c := count(matrix, mid)
        if c >= k {
            R = mid
        } else {
            L = mid + 1
        }
    }

    return R
}

func count(matrix [][]int, x int) int {
    n := len(matrix)
    num := 0
    i, j := n-1, 0
    for i >= 0 && j < n {
        if matrix[i][j] <= x {
            num += i+1
            j++
        } else {
            i--
        }
    }
    return num
}