Окабэ Ринтаро в отчаянии. Его ассистентка и подруга Курису Макисэ вчера была убита при захвате их лаборатории. Неожиданно в его комнату врывается Судзуха Аманэ, представляется путешественницей во времени и сообщает, что Курису осталась жива ровно в одной временной линии, да и в ней она была захвачена сотрудниками Организации. Наш герой во что бы то ни стало решает спасти её.
Судзуха сообщает Окабэ, что они сейчас находятся во временной линии со значением дивергенции равным $$$s$$$, а его ассистентка — со значением $$$t$$$. Проанализировав $$$n$$$ временных веток, Ринтаро придумал $$$m$$$ «D-mail'ов», посылая которые себе в прошлое, можно перемещаться между временными линиями. Для удобства он принял текущее время равным $$$0$$$ и установил, что $$$i$$$-й «D-mail» можно отправить, находясь только в ветке с дивергенцией равной $$$u_i$$$. Пусть в этой ветке текущее время равно $$$t_0$$$, тогда после отправки «D-mail'a» герой переместится в ветку с дивергенцией равной $$$v_i$$$, а время в ней будет равно $$$t_0+w_i$$$. Чтобы не рвать ткань пространственно-временного континуума окончательно, Ринтаро решил не отправлять следующее сообщение, пока предыдущее не будет прочитано и, соответственно, он не переместится в другую ветку.
Однако не всё так просто. Чтобы сообщение подействовало, необходимо, чтобы Ринтаро из прошлого его прочитал, однако это произойдёт, только если его телефон заряжен. Окабэ из прошлого, которому придёт $$$i$$$-е сообщение, в очередной раз включает свой телефон в $$$d_i$$$ секунду, тот держит заряд ровно $$$g_i$$$ секунд, после чего выключается, и герой заряжает его следующие $$$p_i$$$ секунд, лишь после чего включает телефон и может вновь увидеть сообщение. Этот процесс повторяется бесконечно. Более формально, телефон включен ..., с $$$d_i-g_i-p_i$$$ по $$$d_i-p_i - 1$$$, с $$$d_i$$$ по $$$d_i+g_i - 1$$$, с $$$d_i+ g_i + p_i$$$ по $$$d_i+2 \cdot g_i + p_i - 1$$$, ... секунды включительно.
Но и это ещё не всё. Из-за безответственных игр со временем во временных линиях появились аномалии, по одной в каждой линии: в $$$i$$$-й аномалия начнётся в $$$l_i$$$ секунду и продлится вплоть до $$$r_i$$$ секунды включительно. Попасть в любую такую смерти подобно, что для него, что для Курису, поэтому они должны избегать их.
План Окабэ заключается в следующем: он перемещается в одну ветку с ещё живой Курису, освобождает её (мгновенно, его гаджеты помогут ему в этом), и они вместе перемещаются в уже безопасную ветку, т.е. в такую, в которой аномалия уже закончилась. На этом операция по спасению оканчивается. К сожалению, далеко не факт, что операция пройдёт так гладко. Возможны и три других исхода: Окабэ освободит Курису, но они попадут вдвоём в аномалию. Окабэ не успеет освободить Курису, и она попадёт в аномалию, но сам он сможет добраться до безопасной ветки. И, наконец, худший: Окабэ ни Курису не освободит, ни сам не избежит попадания в аномалию. Конечно, Окабэ предпочтёт попасть в аномалию вместе с подругой, нежели сбежать и выжить, предав её, однако если он и добраться до неё не успеет, то предпочтёт спастись самому. Более того, если ему(им) придётся расстаться с жизнью, то он(и) желает(ют), чтобы это случилось как можно позже, и чтобы в момент попадания в аномалию он(и) успели окинуть взглядом этот мир хоть на секунду. Иными словами, аномалия должна застичь героя(ев) не ранее, чем через секунду, после последнего перемещения (если таковое было), и среди всех таких вариантов он(и) выберут тот, в котором это случится как можно позже).
Окабэ просит помощи с подсчётами у Аманэ, но не знает, что то же самое попросили ещё несколько его копий из параллельных вселенных, всего $$$T$$$. У Судзухи уже голова идёт кругом от всего этого, помогите ей с вычислениями.
В первой строке записано одно целое число $$$T$$$ ($$$1 \le T \le 10^5$$$) — количество параллельных вселенных, в которых Окабэ требуется помощь. Далее следует описание каждой.
В первой строке описания каждой вселенной содержится два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le m \le 10^5$$$) — количество временных линий и количество придуманных Окабэ «D-mail'ов» соответственно.
В $$$i$$$-й из следующих $$$m$$$ строк даны шесть чисел $$$u_i$$$, $$$v_i$$$, $$$w_i$$$, $$$d_i$$$, $$$g_i$$$, $$$p_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w_i, g_i, p_i \le 10^9$$$, $$$0 \le d_i < g_i + p_i$$$) — значения дивергенции временных линий, в которой нужно находиться, чтобы отправить $$$i$$$-е сообщение, и той, в которую оно перемещает, разница во времени при перемещении, момент времени, в который адресат этого письма в очередной раз включит телефон, сколько последний держит заряд и сколько его нужно заряжать соответственно.
В следующих $$$n$$$ строках дано описание аномалий. В $$$i$$$-й из них даны два целых числа $$$l_i$$$, $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$) — время начала и конца аномалии во временной линии с дивергенцией равной $$$i$$$.
Наконец, в последней строке описания вселенной даны два целых числа $$$s$$$ и $$$t$$$ ($$$1 \le s, t \le n$$$, $$$s \ne t$$$) — дивергенции временных линий, в которых изначально находятся Окабэ и Курису соответственно.
Гарантируется, что сумма $$$n$$$ и $$$m$$$ по всем параллельным вселенным, в которых Окабэ требуется помощь, не превосходит $$$10^5$$$.
Если операция по спасению может завершиться удачно, выведите Happy end in $$$t$$$ sec, где $$$t$$$ — минимально возможное время в секундах, в которое может завершиться операция.
Если Окабэ успеет освободить Курису, но они не смогут избежать смерти, выведите Tragic death in $$$t$$$ sec, где $$$t$$$ — максимально возможное время попадания героев в аномалию при соблюдении всех описанных условий.
Если Окабэ не успеет спасти Курису, но сможет добраться до безопасной ветки сам, выведите Traitor's escape in $$$t$$$ sec, где $$$t$$$ — минимально возможное время в секундах, в которое Окабэ может оказаться в уже безопасной ветке.
Наконец, если Окабэ и Курису суждено попасть в аномалии по отдельности, выведите Loser's death in $$$t$$$ sec, где $$$t$$$ — максимально возможное время попадания Окабэ в аномалию при соблюдении всех описанных условий.
42 21 2 5 0 1 22 2 10 1 1 11 24 41 22 21 2 5 0 1 21 1 10 0 1 11 26 61 22 21 2 5 0 1 22 2 10 0 1 11 25 51 22 21 2 2 0 1 12 1 2 0 1 11 33 101 2
Traitor's escape in 5 sec Tragic death in 6 sec Loser's death in 1 sec Happy end in 4 sec
Разные временные ветки имеют разные значения дивергенции.
Сообщения отправляются и прочитываются мгновенно.
В первой параллельной вселенной Окабэ в нулевую секунду должен отправить первый «D-mail» и переместиться в линию с Курису за $$$5$$$ секунд, однако та к этому моменту уже будет мертва, поэтому спасти он её не успеет, при этом он может остаться в этой линии, т.к. она уже безопасна.
Во второй параллельной вселенной Окабэ, отправив первый «D-mail» в нулевую секунду, успеет освободить Курису, но больше переместится они никуда не смогут, поэтому смерть их настигнет в $$$6$$$ секунду. Заметим, что Окабэ также мог оставаться в исходной временной линии сколь угодно долго, отправив второй «D-mail» в нулевую секунду, однако это для него менее предпочтительно.
В третьей вселенной Окабэ не успеет добраться до Курису до её смерти и не сможет добраться до уже безопасной линии, поэтому умрёт через секунду, после начала операции в исходной временной линии. Отметим, что он не станет перемещаться, т.к. иначе умрёт сразу же после перемещения, а не хотя бы через секунду, как он того хочет.
В четвёртой вселенной Окабэ отправляет первый «D-mail» в нулевую секунду, спасает Курису во вторую и сразу же отправляет второй «D-mail». Таким образом, они вдвоём оказываются в исходной временной линии в $$$4$$$ секунду, а она к тому моменту уже станет безопасной.