Sorting tuples with respect to multiple criteria
Multivariate optimisation (a subproblem of sorting) is usually hard, even offline, because there are no longer "optima" but you have to deal with several Pareto-optimal elements. 

Luckily, you have specified that such ties should be broken by strict priorities. In that case, lexicographic sorting (w.r.t. your criteria and in order of the priorities) solves the problem.