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 k^2 over the fastest algorithm previously known for this problem that arise in Wang's procedure, faster than the algorithm of Borradaile et al .