Катеринка

Обмеження: 2 сек., 256 МіБ

Зеник та Марічка живуть в країні, яка має $n$ містечок та $m$ двосторонніх доріг між ними, причому дорога з номером $i$ з’єднує містечка з номерами $x_i$ та $y_i$ та має довжину $d_i$.

Зеник живе в містечку з номером $v$, а Марічка — в містечку з номером $u$. Зеник хоче приїхати в гості до Марічки. Проте, по дорозі він планує заїхати до Катеринки, яка живе в містечку з номером $c$ (не подумайте нічого поганого про Зеника, Катеринка — просто подруга).

Зеник та Марічка часто переїжджають, а Катеринка завжди живе в одному і тому ж містечку. Вам відомий номер містечка $c$, в якому проживає Катеринка, а також $k$ пар чисел $v_i$, $u_i$ — номери містечок де проживають, відповідно, Зеник та Марічка. Для кожної такої пари вам необхідно сказати, яку найменшу відстань Зенику необхідно подолати, щоб добратися зі свого дому (вершини $v_i$) спершу до Катеринки (вершини $c$), а потім до Марічки (вершини $u_i$). Зверніть увагу, що Зенику дозволено використовувати одну і ту ж дорогу декілька разів, а також заїжджати до якогось містечка більше одного разу.

Вхідні дані

У першому рядку задано чотири цілі числа $n$, $m$, $q$, $c$ — кількість вершин, кількість ребер, кількість запитів, а також номер містечка, в якому проживає Катеринка.

Наступні $m$ рядків містять опис ребер. Кожен з них містить три цілі числа $x_i$, $y_i$, $d_i$ — кінці ребра та його довжина.

Наступні $q$ рядків містять варіанти початкової та кінцевої вершин на шляху. Кожен з них містить два цілі числа $v_i$, $u_i$ — початкова і кінцева вершини.

Вихідні дані

Вам необхідно вивести $q$ рядків, в $i$-му з яких необхідно вивести одне ціле число — найменшу довжину шляху, який починається у вершині з номером $v_i$, закінчується у вершині з номером $u_i$, і проходить через вершину $c$.

Обмеження

$1 \le n, m, q \le 2 \cdot 10^5$,

$1 \le x_i, y_i, v_i, u_i, c \le n$,

$0 \le d_i \le 10^3$,

існує шлях між кожною парою вершин в графі.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 5 3 1 1 2 1 2 3 3 3 1 1 3 4 4 1 4 10 4 3 2 3 1 4	6 2 5