P5787 [Template] Segment Tree Divide and Conquer / Bipartite Graph.

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.

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 $k$ lines. The $i$-th line contains a string `Yes` or `No`, indicating whether the graph is bipartite in the $i$-th time period.

### 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