Reachability in Company-Constructed DAG

You are given a directed acyclic graph (DAG) with $$N$$ nodes and $$M$$ edges. The nodes are numbered from $$1$$ to $$N$$. Each edge is directed from node $$A_i$$ to node $$B_i$$ (with $$A_i < B_i$$) and is built by one of $$P$$ companies (numbered from $$1$$ to $$P$$), where the $$i$$-th edge is built by company $$C_i$$.

There are $$Q$$ queries. Each query provides an initial company interval $$[L,R]$$ and an available budget $$X$$. You are allowed to change the interval at most once to some new interval $$[l', r']$$ (with $$1 \le l' \le r' \le P$$) at a cost of $$|L - l'| + |R - r'|$$. The cost must be at most $$X$$. When using only the edges built by companies in the chosen interval, check if it is possible to reach every node in the graph starting from node $$1$$.

Determine for each query whether there exists an interval $$[l', r']$$ (reachable by spending no more than $$X$$) such that the subgraph induced by companies in this interval makes every node reachable from node $$1$$.

Input Format:

• The first line contains four integers: $$N$$, $$M$$, $$P$$, and $$Q$$.
• Each of the next $$M$$ lines contains three integers: $$A_i$$, $$B_i$$, and $$C_i$$, describing an edge from $$A_i$$ to $$B_i$$ built by company $$C_i$$.
• Each of the next $$Q$$ lines contains three integers: $$L$$, $$R$$, and $$X$$.

Output Format:

• For each query, print a single line containing either "Yes" if there exists a valid interval making all nodes reachable from node $$1$$, or "No" otherwise.

Note: The interval adjustment (if needed) can be performed at most once, and the adjusted interval must satisfy the cost constraint $$|L - l'| + |R - r'| \le X$$.

inputFormat

The input begins with a line containing four integers $$N$$, $$M$$, $$P$$, $$Q$$. Then $$M$$ lines follow, each containing three integers $$A_i$$, $$B_i$$, $$C_i$$ (where $$A_i < B_i$$). Finally, $$Q$$ lines follow, each containing three integers $$L$$, $$R$$, and $$X$$.

outputFormat

For each query, output a single line with the word "Yes" if it is possible to find a valid adjusted interval, or "No" otherwise.

sample

3 3 3 2
1 2 1
2 3 2
1 3 3
1 1 1
2 2 0

Yes
No