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 \leq x \leq 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 \le n \le 1,000;\ 1 \le m \le 5,000;\ 1 \le k \le 10^9)$. The second line of input contains two space-separated integers $s$ and $t$ $(1 \le s, t \le n;\ s \ne t)$. Each of the next $m$ lines contains four space-separated integers $a_i$, $b_i$, $c_i$, and $d_i$ $(1 \le a_i, b_i \le n;\ 1 \le c_i \le d_i \le k;\ a_i \ne 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$.

2017 Pacific Northwest Region Programming Contest