Problem Description

There are $n$ subway stations and $m$ subway lines in a city. The stations are numbered $1,2,\ldots,n$ in order.

For the $i$-th subway line ($1\le i\le m$), trains run in one direction from station $u_i$ to station $v_i$. The latest departure time is minute $l_i$, and the travel time is $t_i$ minutes. From minute $0$ to minute $l_i$, there is a train departing from station $u_i$ every minute. A train that departs at minute $x$ ($0\le x\le l_i$) will arrive at station $v_i$ at minute $x+t_i$. Passengers on this train may transfer to any train of any line departing from station $v_i$ at minute $x+t_i$ or later.

Now there are $q$ queries. The $i$-th query ($1\le i\le q$) gives the starting station $x_i$, the destination station $y_i$, and the departure time $s_i$. You need to determine whether it is possible to reach station $y_i$ when departing from station $x_i$ at minute $s_i$. Departing from station $x_i$ at minute $s_i$ means you may take any train on any line that departs from station $x_i$ at minute $s_i$ or later.

Input Format

The first line contains three positive integers $n,m,q$, representing the number of stations, the number of subway lines, and the number of queries.

The next $m$ lines each contain four integers $u_i,v_i,l_i,t_i$, representing the starting station, the ending station, the latest departure time, and the required travel time of the line.

The next $q$ lines each contain three integers $x_i,y_i,s_i$, representing the trip start, the trip destination, and the departure time.

Output Format

Output $q$ lines in total. For each query, if it is possible to reach station $y_i$ when departing from station $x_i$ at minute $s_i$, output Yes; otherwise output No. Note that the output is case-sensitive.

3 4 5
1 2 3 3
2 3 5 2
3 1 4 1
1 3 0 6
1 3 2
2 1 2
2 1 3
3 2 2
3 2 3

Yes
Yes
No
Yes
No

Hint

For $40\%$ of the test points, it is guaranteed that $q\le 100$.

For all test points, it is guaranteed that:

• $1\le n\le 500$
• $1\le m\le 1000$
• $1\le q\le 5\times 10^5$
• $1\le u_i,v_i,x_i,y_i\le n$
• $0\le l_i,s_i\le 10^5$
• $1\le t_i\le 10^4$

Translated by ChatGPT 5