Có \(N\) thị trấn và \(M\) tuyến xe buýt một chiều chạy thẳng giữa các thị trấn. Các thị trấn được đánh số từ \(1\) đến \(N\). Một hành khách ở thị trấn \(1\) tại thời điểm \(0\) cần đến thị trấn \(P\). Người ấy sẽ được đón tại bến xe của thị trấn \(P\) đúng thời điểm \(T\); nếu đến sớm thì phải chờ.

Với tuyến \(i\), biết thị trấn xuất phát \(s_i\), thị trấn đến \(t_i\) và các khoảng thời gian gần đúng. Xe rời \(s_i\) tại một thời điểm thuộc \([a_i,b_i]\) và đến \(t_i\) tại một thời điểm thuộc \([c_i,d_i]\); hai đầu mút đều được tính.

Hành khách muốn chọn một hành trình làm nhỏ nhất tổng thời gian chờ lớn nhất có thể, đồng thời bảo đảm không lỡ bất kỳ chuyến nối tiếp nào. Vì vậy, khi đổi xe, thời điểm đến muộn nhất của chuyến trước không được sau thời điểm khởi hành sớm nhất của chuyến sau.

Khi tính thời gian chờ trong trường hợp xấu nhất, giả sử mỗi lần đến là sớm nhất có thể và mỗi lần khởi hành là muộn nhất có thể. Thời gian chờ trước chuyến đầu, giữa các chuyến và từ khi đến \(P\) đến \(T\) đều được tính.

Dữ liệu vào

Dòng đầu gồm \(N,M,P,T\) (\(1 \le N \le 50\,000\), \(1 \le M \le 100\,000\), \(1 \le P \le N\), \(0 \le T \le 10^9\)).

Mỗi dòng trong \(M\) dòng tiếp theo gồm \(s_i,t_i,a_i,b_i,c_i,d_i\), trong đó \(1 \le s_i,t_i \le N\) và

Dữ liệu ra

In tổng thời gian chờ lớn nhất của hành trình tối ưu. Nếu không thể bảo đảm đến thị trấn \(P\) không muộn hơn \(T\), in -1.

Ví dụ

3 6 2 100
1 3 10 20 30 40
3 2 32 35 95 95
1 1 1 1 7 8
1 3 8 8 9 9
2 2 98 98 99 99
1 2 0 0 99 101

32

3 2 2 100
1 3 0 0 49 51
3 2 50 51 100 100

-1