15110번 - Security Badge 다국어

문제

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 a_i to room b_i, but not the other way around. Additionally, each door has a security code that can be represented as a range of numbers [c_i, d_i].

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 c_i ≤ x ≤ d_i.

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 ≤ 10⁹).

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 a_i, b_i, c_i, and d_i (1 ≤ a_i, b_i ≤ n; 1 ≤ c_i ≤ d_i ≤ k; a_i ≠ b_i), 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.

제한

힌트