paint_down_to_common: use prio_queue