Before revision:  This improves by a factor of k^2 over the fastest algorithm previously known for this problem [Wang, SODA 2019].
After revision:  This improves by a factor of \max(k^2,k\log^2 n) over the fastest algorithm previously known for this problem [Wang, SODA 2019].