Цепная реакция

Мало кто знает, почему магическая технология такая эффективная. На самом деле любой магический кристалл можно представить в виде $n$ узлов и $m$ двухсторонних связей между ними. Иногда в некоторых узлах вспыхивают искры энергии, которые затем распространяются в соседние узлы, из них --- в соседние с ними, и так далее.

Недавно исследователи академии Пилтовера во главе с Хеймердингером выяснили, что делает магические кристаллы особенно сильными. Некоторые из связей между узлами являются накопительными. Это означает, что энергия может проходить через них только в определенные периоды времени, а вне этих периодов скапливается в концах этих связей и сохраняется в них.

Для каждой связи известно, сколько времени уходит на перемещение энергии из одного ее конца в другой. Также, для всех накопительных связей известно, что они пропускают энергию в одни и те же интервалы времени. Эти интервалы задаются списком пар моментов времени $(x\_i, y\_i)$, означающими, что между моментами времени $x\_i$ и $y\_i$ включительно каждая связь открыта и пропускает энергию. В остальные моменты времени они закрыты, и энергия <<задерживается>> в их концах.

Важно отметить, что если накопительная связь закрывается в тот момент, когда энергия перемещается по ней, энергия продолжает двигаться в ту сторону, в которую двигалась. Иными словами, если в момент $t$ связь длиной $w$ открыта, и в этот же момент $t$ к одному ее концу приходит искра энергии, то в момент $t + w$ она доберется до второго конца, даже если связь закроется к этому времени.

Для создания нового магического оружия необходимо определить, в какой момент времени энергия впервые дойдет до узла $v$, если искра зародится в узле $u$ в момент времени $t\_0$, или что энергия не дойдет до узла $v$ вообще.

В первой строке ввода даны три целых числа $n$, $m$, $k$ --- количество узлов кристалла и связей между ними, а также количество пар моментов времени, между которыми все накопительные связи открыты ($2 \leqslant n \leqslant 10^{5}$; $1 \leqslant m \leqslant 10^{6}$, $1 \leqslant k \leqslant 10^{5}$).

В $i$-й из следующих $m$ строк через пробел даны четыре целых числа $a\_i$, $b\_i$, $w\_i$ и $f\_i$. Первые два числа $a\_i$ и $b\_i$ --- номера узлов, которые соединяет $i$-я связь ($1 \leqslant a\_i, b\_i \leqslant n$; $a\_i \neq b\_i$). Число $w\_i$ --- время, за которое энергия перемещается между концами связи ($1 \leqslant w\_i \leqslant 10^{9}$). Число $f\_i$ задает, является ли $i$-я связь накопительной. Он равен $1$, если является, и $0$ иначе.

В каждой из следующих $k$ строк записаны по два целых числа $x\_i$, $y\_i$ --- моменты времени, между которыми (включительно) каждая накопительная связь открыта и может перемещать энергию ($1 \leqslant x\_i \leqslant y\_i \leqslant 10^{18}$; $y\_{i-1} < x\_{i}$ для всех $i$).

В последней строке ввода даны три целых числа $u$, $v$ и $t\_0$ --- номера стартового и конечного узла, а также время зарождения искры энергии в стартовом узле ($1 \leqslant u, v \leqslant n$; $1 \leqslant t\_0 \leqslant 10^{18}$).

Выведите одно целое число --- через какое минимальное время энергия впервые дойдет от узла $u$ до узла $v$, начав движение в момент времени $t\_0$. Если она не дойдет до $v$ никогда, выведите <<-1>> (без кавычек).