AT_agc031_f [AGC031F] Walk on Graph

[problemUrl]: https://atcoder.jp/contests/agc031/tasks/agc031_f $ N $ 頂点 $ M $ 辺の連結なグラフが与えられます．各頂点には $ 1,\ 2,...,N $ と番号がついています． $ i(1\ \leq\ i\ \leq\ M) $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を繋ぐ長さ $ C_i $ の無向辺です． また，奇数 $ MOD $ が与えられます． $ Q $ 個のクエリが与えられるので，処理してください．クエリの形式は以下の通りです． - $ i $ 番目のクエリでは，$ S_i,T_i,R_i $ が与えられる．頂点 $ S_i $ から頂点 $ T_i $ へ至る経路であって，長さを $ MOD $ で割った余りが $ R_i $ になるようなものが存在する場合は `YES` を，存在しない場合は `NO` を出力する．ただし同じ辺を複数回通っても，来た辺をすぐ戻ってもよい． ただし，この問題においての経路の長さは辺の長さの単純な和**ではなく**，$ 1 $ 本目に使う辺の長さを $ 1 $ 倍，$ 2 $ 本目に使う辺の長さを $ 2 $ 倍，$ 3 $ 本目に使う辺の長さを $ 4 $ 倍，$ ... $ したものの和とします． (より厳密には，長さ $ L_1,...,L_k $ の辺をこの順に使ったとすると，その経路の長さは $ L_i\ \times\ 2^{i-1} $ の和です．)

N/A

N/A

### 制約 - $ 1\ \leq\ N,M,Q\ \leq\ 50000 $ - $ 3\ \leq\ MOD\ \leq\ 10^{6} $ - $ MOD $ は奇数 - $ 1\ \leq\ A_i,B_i\leq\ N $ - $ 0\ \leq\ C_i\ \leq\ MOD-1 $ - $ 1\ \leq\ S_i,T_i\ \leq\ N $ - $ 0\ \leq\ R_i\ \leq\ MOD-1 $ - 与えられるグラフは連結 (ただし自己辺や多重辺を含むことがある) ### Sample Explanation 1 各クエリに対する答えは以下のようになります． - $ 1 $ 番目のクエリ: 頂点 $ 1,2,3 $ の順に進むと経路の長さは $ 1\ \times\ 2^0\ +\ 2\ \times\ 2^1\ =\ 5 $ となり，長さを $ 2019 $ で割った余りが $ 5 $ になる経路は存在するので，答えは `YES` である． - $ 2 $ 番目のクエリ: どのように頂点 $ 1 $ から頂点 $ 3 $ まで進んでも経路の長さを $ 2019 $ で割った余りが $ 4 $ となることはないので，答えは `NO` である．