Di sản (Legacy)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ hành tinh đánh số từ $1$ đến $n$. Bạn bắt đầu tại hành tinh $s$.

Có $q$ loại gói cổng dịch chuyển một chiều:

1. 1 v u w: mở một cổng từ $v$ đến $u$ với chi phí $w$.
2. 2 v l r w: từ $v$ có thể mở cổng đến bất kỳ hành tinh $u\in[l,r]$, mỗi lần dùng gói tốn $w$.
3. 3 v l r w: từ bất kỳ hành tinh $u\in[l,r]$ có thể mở cổng đến $v$, mỗi lần dùng gói tốn $w$.

Mỗi lần mua một gói chỉ sử dụng được một lần, nhưng có thể mua lại cùng loại gói nhiều lần.

Với mỗi hành tinh, hãy tìm số tiền nhỏ nhất cần thiết để đi từ $s$ đến hành tinh đó.

Input

Dòng đầu chứa ba số nguyên $n,q,s$.

Trong $q$ dòng tiếp theo:

• nếu $t=1$, dòng có dạng 1 v u w;
• nếu $t=2$ hoặc $t=3$, dòng có dạng t v l r w.

Output

In $n$ số nguyên. Số thứ $i$ là chi phí nhỏ nhất để đi từ hành tinh $s$ đến hành tinh $i$, hoặc -1 nếu không thể đến.

Subtask

Trong tất cả các Subtask: $1\le n,q\le10^5$; $1\le s,v,u\le n$; $1\le l\le r\le n$; $1\le w\le10^9$.

• Subtask 1 — 10%: Chỉ có truy vấn loại $1$.
• Subtask 2 — 20%: Chỉ có truy vấn loại $1$ và loại $2$.
• Subtask 3 — 30%: $n\le2000$; $q\le2000$; có thể xuất hiện cả ba loại truy vấn.
• Subtask 4 — 40%: Không có điều kiện bổ sung.

Ví dụ

Input

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

Output

0 28 12

Giải thích

Từ hành tinh $1$, chi phí nhỏ nhất lần lượt đến các hành tinh $1,2,3$ là $0,28,12$, nên output là 0 28 12.