Trở lại với chuyện tình của  ĐB và TN, dù còn khá lâu mới đến Noel nhưng ĐB đã quyết định lên kế hoạch từ bây giờ để tặng cho TN một món quà giáng sinh thật tuyệt vời.

Thành phố nơi 2 người đang ở có n nút giao thông đánh số từ 1 đến n, giữa chúng có một số các đường đi trực tiếp. Đêm Noel, TN đứng chờ ở nút giao thông t, ĐB sẽ đi từ nhà (ở nút giao thông s) qua một số con đường nào đó để đến điểm hẹn.

Tất nhiên ĐB không muốn TN phải chờ lâu, nên cậu sẽ chọn đường đi ngắn nhất có thể để đến nơi. Cậu cũng muốn biết có thể đến được đó bằng bao nhiêu con đường ngắn nhất khác nhau, để đề phòng trường hợp kẹt xe, đường hỏng,… Biết rằng có ít nhất một con đường từ s tới t

Do số lượng các nút giao thông quá lớn, ĐB không tài nào tự tính toán được nên quyết định nhờ các bạn giúp. Hãy giúp ĐB không phải quay lại kiếp FA lần nữa nhé =))).

Input

-       Dòng thứ nhất : 3 số nguyên dương n, s, t (2 ≤ n ≤ 10⁵, 1 ≤ s, t ≤ n, s ≠ t)

-       n dòng sau, dòng thứ i gồm 3 số nguyên dương l, r, w, có nghĩa là có các đường đi một chiều từ i đến l, i đến l + 1, ..., i đến r, mỗi con đường đó có độ dài là w (1 ≤ l ≤ r ≤ n, 1 ≤ w ≤ 10⁶)

Output

-       Hai số nguyên dương : độ dài của đường đi ngắn nhất và số lượng đường đi ngắn nhất sau khi mod 10¹⁵, cách nhau một khoảng trắng

Ví dụ

Input:

	4 1 4

	2 3 3

	3 4 5

	2 4 5

	1 2 6

Output:
	8 2

Giải thích : Có 2 đường đi ngắn nhất với tổng độ dài là 8 : (1, 2, 4) và (1, 3, 4)