Description

Shenben has a graph with $n$ nodes.

Because Shenben is Shenben, within time $k$, there will be $m$ edges that appear and then disappear.

Shenben asks you to determine whether the graph is a bipartite graph in each time period.

Such an easy problem is of course no problem for Shenben, so he wants to test you.

Originally BZOJ4025.

Input Format

The first line contains three integers $n,m,k$.

In the next $m$ lines, each line contains four integers $x,y,l,r$, meaning there is an edge connecting $x,y$ that appears at time $l$ and disappears at time $r$.

Output Format

Output $k$ lines. The $i$-th line contains a string Yes or No, indicating whether the graph is bipartite in the $i$-th time period.

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

Yes
No
Yes

Hint

Sample Explanation

At time $0$, two edges $(1,2)$ and $(2,3)$ appear.

In the $1$st time period, this graph is bipartite, so output Yes.

At time $1$, an edge $(1,3)$ appears.

In the $2$nd time period, this graph is not bipartite, so output No.

At time $2$, the two edges $(1,2)$ and $(1,3)$ disappear.

In the $3$rd time period, there is only one edge $(2,3)$, and this graph is bipartite, so output Yes.

Constraints

$n,k = 10^5$, $m = 2\times 10^5$. $1 \le x,y \le n$, $0 \le l \le r \le k$.

Notes

This problem has hack testdata (Subtask $2$), worth $0$ points, but if you do not pass the hack testdata, it will not be considered accepted.

Translated by ChatGPT 5