题号：NC212977
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
有𝑛个办公室(编号为1 − 𝑛)，𝑚个通道(编号为1 − 𝑚)，𝑘名实验室成员(编号为1 − 𝑘) 编号为𝑖的通道可以从编号为𝑎𝑖的办公室单向到达编号为𝑏𝑖的办公室，且只有编号 在[𝑐𝑖, 𝑑𝑖]的实验室成员才可以经过这条通道。
现在给出𝑠，𝑡，求有多少个实验室成员可以从𝑠到达t。
输入描述:
输入第一行包含三个整数𝑛, 𝑚, 𝑘(2 ≤ 𝑛 ≤ 1000,1 ≤ 𝑚 ≤ 5000,1 ≤ 𝑘 ≤ 10^9
)
第二行包含两个整数𝑠,𝑡(1 ≤ 𝑠,𝑡 ≤ 𝑛, 𝑠 ≠ 𝑡)
接下来𝑚行，每行4个整数𝑎𝑖, 𝑏𝑖, 𝑐𝑖, 𝑑𝑖编号为𝑖的通道
(1 ≤ 𝑎𝑖, 𝑏𝑖 ≤ 𝑛, 1 ≤ 𝑐𝑖 ≤ 𝑑𝑖 ≤ 𝑘, 𝑎𝑖 ≠ 𝑏𝑖)
输出描述:
输出一个整数表示答案
示例1
输入
复制
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