평범한 그래프와 이상한 쿼리

이 문제는 $w\_i$의 제한을 제외하면 단순한 그래프와 이상한 쿼리 문제와 같은 문제이다.

정점 $N$개와 간선 $M$개로 이루어진 평범한 무향 가중치 그래프 $G$가 주어진다. 정점은 1번부터 $N$번까지 번호가 매겨져 있고, 각 간선의 가중치는 양의 정수이다. 다음과 같은 쿼리가 $Q$개 주어진다.

• a b k: $a$번 정점에서 시작해 $b$번 정점에서 끝나는 경로 중 길이가 $k$의 배수인 경로가 존재하면 Yes를, 없으면 No를 출력한다.

경로에는 같은 정점이나 같은 간선이 여러 번 포함될 수 있다. 경로의 길이는 경로에 포함된 간선 가중치의 합이다. 같은 간선이 여러 번 포함되면 그 간선의 가중치가 지나간 횟수만큼 길이에 더해진다. 주어진 쿼리를 올바르게 처리하라.

첫 번째 줄에 정점의 수 $N$, 간선의 수 $M$, 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. ($2\le N\le 100\ 000; 0\leq M\leq 200\, 000; 1 \leq Q \leq 100\ 000$)

두 번째 줄부터 $M$개의 줄에 걸쳐 각 간선의 정보를 나타내는 정수 $u\_i, v\_i, w\_i$가 공백으로 구분되어 주어진다. $i$번째 간선은 가중치 $w\_i$를 가지며 $u\_i$와 $v\_i$를 잇는다. 각 정점 쌍을 잇는 간선은 최대 1개임이 보장된다. ($1\leq u\_i,v\_i\leq N; u\_i\neq v\_i; 1\leq w\_i\leq 10^9$)

$M+2$번째 줄부터 $Q$개의 줄에 걸쳐 각 쿼리가 a b k의 형태로 주어진다. ($1\leq a,b\leq N; a\neq b; 1\leq k\leq 10^9$)

주어지는 수는 모두 정수이다.

각 쿼리마다 $a$번 정점에서 시작해 $b$번 정점에서 끝나는 길이가 $k$의 배수인 경로가 존재하면 Yes, 없으면 No를 한 줄에 하나씩 순서대로 출력한다.