Christmas will come next month, so DB is planning to give TN a wonderful gift.

The city that DB and TN are living has n intersections. Each direct connections between 2 intersections has its length. In the Christmas night, TN will wait at the t-th intersection, and DB will start from the s-th intersection go through some connections, to the date place.

Of course DB doesn’t want to make TN wait for long time, so he will choose the shortest path. He also want to know how many different shortest paths from s to t (there is at least one path).

Because the number of intersections and connections are too large, DB can’t calculate these himself, so he need you help.

Input

• First line : 3 positive integers, n, s and t (2 ≤ n ≤ 10⁵, 1 ≤ s, t ≤ n, s ≠ t)
• n lines : the i-th line contains 3 positive integers l, r, w, means there are direct connections from i to l, i to l + 1, ... i to r, each has length w (1 ≤ l ≤ r ≤ n, w ≤ 10⁶)

Output

• Two positive integers, length of the shortest path, and number of the shortest paths (modulo 10¹⁵), separated by a space

Example

Input:
4 1 4
2 3 3
3 4 5
2 4 5
1 2 6

Output:
8 2

Detais: the two shortest paths are (1, 2, 4) and (1, 3, 4)