DanilPRO20172007

31.03.2020 20:14 •  Информатика

Впоследнее время становится все больше олимпиад по программированию. чтобы участникам
было удобнее, организаторы стараются, чтобы олимпиады не пересекались по времени, однако иногда такое случается.
однажды две олимпиады были запланированы в один день. первая олимпиада должна была
начаться в момент времени s1 и длиться d1 (таким образом, заканчиваясь в момент s1 + d1), вторая
же должна начаться в момент времени s2 и длиться d2 (заканчиваясь в s2 + d2). длительность
олимпиад изменять нельзя, однако начало можно двигать по времени. при этом оба организатора
имеют следующие ограничения на передвижение олимпиад. первая олимпиада должна начаться не
раньше l1 и закончиться не позже r1, вторая — начаться не раньше l2 и закончиться не позже r2.
ваша — написать программу, которая бы организаторам олимпиад перенести их
таким образом, чтобы они не пересекались, и при этом выполнялись все ограничения. если решений
несколько, вам требуется найти такое, в котором суммарное изменение времени начала олимпиад,
минимально. то есть, если олимпиады нужно начать в моменты времени c1 и c2, то вам нужно
минимизировать величину (|s1 − c1| + |s2 − c2|).
формат входных данных
входные данные содержат несколько тестов.
первая строка содержит целое число n — число тестов, которые нужно решить (1 6 n 6 50 000)
далее следуют описания n тестов. описание каждого теста состоит из двух строк.
первая из этих строк содержит четыре целых числа l1, r1, l2 и r2 — ограничение на время проведения олимпиад (0 6 li < ri 6 109
).
вторая из этих строк содержит четыре целых числа s1, d1, s2 и d2 — времена начала олимпиад
и их длительности (li 6 si
; si + di 6 ri).
формат выходных данных
выведите n строк. в i строке выведите ответ на i-й тест.
в качестве ответа на тест выведите два целых числа c1 и c2: времена начала первой и второй
олимпиады в новом расписании, соответственно. если есть несколько решений, минимизирующих
суммарный сдвиг, выведите любое. если невозможно провести олимпиады, удовлетворив все ограничения, выведите два числа −1.