Дано орієнтований граф з \(N\) вершин. Необхідно опрацювати \(Q\) операцій настпуних типів:
1 U V W - додати ребро з вершини \(U\) в вершину \(V\) вагою \(W\)
2 U L R W - додати ребра з вершини \(U\) в кожну вершину з відрізка \([L..R]\) вагою \(W\)
3 U L R W - додати ребра з кожної вершини відрізка \([L..R]\) в вершину \(U\) вагою \(W\)

Після всіх операцій додавання ребер знайдіть найкоротший шлях з вершини \(S\) до усіх інших.

Формат вхідних даних

Перший рядок містить три цілих числа \(N,Q,S\) (\(1 \le N,Q \le 10^5\) , \(1 \le S \le N\))
Наступні \(Q\) рядків містять опис запитів.
(\(1 \le W \le 10^9\))

Формат вихідних даних

Виведіть \(N\) чисел через пробіл - найкоротшу відстань від вершини \(S\) до кожної з вершин (якщо шляху не існує, виведіть -1)

Приклад вхідних даних-1

3 5 1
2 3 2 3 17
2 3 2 2 16
2 2 2 3 3
3 3 1 1 12
1 3 3 17

Приклад вихідних даних-1

0 28 12

Приклад вхідних даних-2

4 3 1
3 4 1 3 12
2 2 3 4 10
1 2 4 16

Приклад вихідних даних-2

0 -1 -1 12