연쇄 반응

마법 기술이 왜 이렇게 효율적인지 아는 사람은 많지 않다. 어떤 마법 크리스털이든 $n$개의 노드와 노드 사이를 잇는 $m$개의 양방향 연결로 나타낼 수 있다. 때때로 일부 노드에서 에너지 불꽃이 튀고, 에너지는 인접한 노드로 퍼지며, 다시 그 노드의 이웃으로 계속 퍼진다.

헤이머딩거가 이끄는 필트오버 아카데미의 연구진이 마법 크리스털을 특히 강하게 만드는 원인을 밝혀냈다. 연결 중 일부는 축적형이다. 축적형 연결은 정해진 기간에만 에너지를 통과시킨다. 그 밖의 기간에는 에너지가 연결의 양 끝에 쌓여 머문다.

각 연결마다 에너지가 한쪽 끝에서 다른 쪽 끝까지 이동하는 데 걸리는 시간이 주어진다. 모든 축적형 연결은 같은 시간 구간에 에너지를 통과시킨다. 구간은 시각 쌍 $(x_i, y_i)$의 목록으로 주어지며, 모든 축적형 연결은 $x_i$부터 $y_i$까지(양 끝 포함) 열려 에너지를 통과시킨다. 그 밖의 시각에는 축적형 연결이 닫혀 있고, 에너지는 연결의 양 끝에서 기다린다.

에너지가 축적형 연결을 따라 이동하는 도중에 연결이 닫히더라도, 에너지는 원래 가던 방향으로 계속 이동한다. 즉 길이가 $w$인 연결이 시각 $t$에 열려 있고, 같은 시각 $t$에 에너지 불꽃이 연결의 한쪽 끝에 도착하면, 그 사이에 연결이 닫히더라도 불꽃은 시각 $t + w$에 반대쪽 끝에 도착한다.

새로운 마법 무기를 만들려면, 노드 $u$에서 시각 $t_0$에 불꽃이 생겼을 때 에너지가 처음으로 노드 $v$에 도달하는 데 걸리는 최소 시간을 $t_0$부터 세어 구해야 한다. 에너지가 $v$에 도달하지 못하는 경우도 있다.

첫 줄에 세 정수 $n$, $m$, $k$가 주어진다. 각각 노드의 수, 연결의 수, 축적형 연결이 열려 있는 시각 쌍의 수이다 ($2 \le n \le 10^5$; $1 \le m \le 10^6$, $1 \le k \le 10^5$).

다음 $m$개의 줄에는 공백으로 구분된 네 정수 $a_i$, $b_i$, $w_i$, $f_i$가 주어진다. $a_i$와 $b_i$는 $i$번째 연결이 잇는 노드 번호이다 ($1 \le a_i, b_i \le n$; $a_i \ne b_i$). $w_i$는 에너지가 연결의 양 끝 사이를 이동하는 데 걸리는 시간이다 ($1 \le w_i \le 10^9$). $f_i$는 $i$번째 연결이 축적형이면 1, 아니면 0이다.

다음 $k$개의 줄에는 두 정수 $x_i$, $y_i$가 주어진다. 모든 축적형 연결은 $x_i$부터 $y_i$까지(양 끝 포함) 열려 있어 에너지를 통과시킬 수 있다 ($1 \le x_i \le y_i \le 10^{18}$; $y_{i-1} < x_i$).

마지막 줄에는 세 정수 $u$, $v$, $t_0$가 주어진다. 각각 시작 노드, 도착 노드, 시작 노드에서 불꽃이 생기는 시각이다 ($1 \le u, v \le n$; $1 \le t_0 \le 10^{18}$).

정수 하나를 출력한다. 노드 $u$에서 시각 $t_0$에 출발한 에너지가 처음으로 노드 $v$에 도달하기까지 걸리는 최소 시간이다. 에너지가 $v$에 도달하지 못하면 -1을 출력한다.