AT_arc196_d [ARC196D] Roadway

There are $ N $ towns, numbered $ 1,2,\ldots,N $ , arranged in a line in this order. There are $ N-1 $ roads connecting adjacent towns: road $ j\,(1 \leq j \leq N-1) $ connects towns $ j $ and $ j+1 $ . For each road $ j $ , you can set a **strength** $ w_j $ (an integer that may be negative). When a person travels along a road, their **stamina** changes. Specifically, if a person with stamina $ x $ travels along road $ j $ , their stamina becomes $ x + w_j $ . There are $ M $ people who will now move between these towns. Person $ i\,(1 \le i \le M) $ starts with stamina $ 0 $ at town $ S_i $ and travels to town $ T_i $ via the shortest path. It is guaranteed that $ |S_i - T_i| > 1 $ . Also, $ (S_i, T_i) \neq (S_j, T_j) $ if $ i \neq j $ . Person $ i $ ’s requirement is as follows: > When departing Town $ S_i $ and when arriving at Town $ T_i $ , their stamina should be exactly $ 0 $ . At every other town, their stamina should always be a positive integer. Assume that there are no changes to stamina other than those due to traveling along roads as described above. Process $ Q $ queries. For the $ k $ -th query $ (1 \le k \le Q) $ , if it is possible to set the strengths of the roads so that the requirements of all people $ L_k, L_k + 1, \ldots, R_k $ are satisfied, print `Yes`; otherwise, print `No`.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ Q $ $ S_1 $ $ T_1 $ $ S_2 $ $ T_2 $ $ \vdots $ $ S_M $ $ T_M $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

Print $ Q $ lines. The $ k $ -th line should contain `Yes` if there is a way to set the strengths of the roads so that the requirements of all people $ L_k, L_k + 1, \ldots, R_k $ are satisfied, and `No` otherwise.

### Sample Explanation 1 For the first query, consider setting the strengths of roads $ 1, 2, 3, 4 $ to $ 1, -1, 1, -1 $ , respectively. - Person $ 1 $ starts at town $ 4 $ with stamina $ 0 $ , visits town $ 3 $ with stamina $ 1 $ , and arrives at town $ 2 $ with stamina $ 0 $ . - Person $ 2 $ starts at town $ 1 $ with stamina $ 0 $ , visits town $ 2 $ with stamina $ 1 $ , and arrives at town $ 3 $ with stamina $ 0 $ . - Person $ 3 $ starts at town $ 3 $ with stamina $ 0 $ , visits town $ 4 $ with stamina $ 1 $ , and arrives at town $ 5 $ with stamina $ 0 $ . Thus, this configuration satisfies the requirements of persons $ 1,2,3 $ , so print `Yes` on the first line. For the second query, it is impossible to satisfy the requirements of persons $ 2,3,4 $ simultaneously, so print `No`. ### Constraints - $ 3 \le N \le 4 \times 10^5 $ - $ 1 \le M \le 2 \times 10^5 $ - $ 1 \le Q \le 2 \times 10^5 $ - $ 1 \le S_i, T_i \le N $ - $ |S_i - T_i| > 1 $ - $ (S_i, T_i) \neq (S_j, T_j)\,(i \neq j) $ - $ 1 \le L_k \le R_k \le M $ - All input values are integers.