시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 14 10 9 69.231%

문제

You are in charge of the security for a large building, with n rooms and m doors between the rooms. The rooms and doors are conveniently numbered from 1 to n, and from 1 to m, respectively.

Door i opens from room ai to room bi, but not the other way around. Additionally, each door has a security code that can be represented as a range of numbers [ci, di].

There are k employees working in the building, each carrying a security badge with a unique, integer-valued badge ID between 1 and k. An employee is cleared to go through door i only when the badge ID x satisfies ci ≤ x ≤ di.

Your boss wants a quick check of the security of the building. Given s and t, how many employees can go from room s to room t?

입력

The first line of input contains three space-separated integers n, m, and k (2 ≤ n ≤ 1,000; 1 ≤ m ≤ 5,000; 1 ≤ k ≤ 109).

The second line of input contains two space-separated integers s and t (1 ≤ s, t ≤ n; s ≠ t).

Each of the next m lines contains four space-separated integers ai, bi, ci, and di (1 ≤ ai, bi ≤ n; 1 ≤ ci ≤ di ≤ k; ai ≠ bi), describing door i.

For any given pair of rooms a, b there will be at most one door from a to b (but there may be both a door from a to b and a door from b to a).

출력

Print, on a single line, the number of employees who can reach room t starting from room s.

예제 입력 1

4 5 10
3 2
1 2 4 7
3 1 1 6
3 4 7 10
2 4 3 5
4 2 8 9

예제 출력 1

5

예제 입력 2

4 5 9
1 4
1 2 3 5
1 3 6 7
1 4 2 3
2 4 4 6
3 4 7 9

예제 출력 2

5