#50 origami

Statement

다다스는 빨간색과 파란색 간선으로 이루어진 트리를 접는 놀이를 하고 있다.

정점이 $N$ 개인 두 트리 $T_1, T_2$ 가 주어진다. 각 간선은 빨간색 또는 파란색으로 칠해져 있다. 색은 입력에서 $0$ 또는 $1$ 로 주어진다.

하나의 트리에서 다음 연산을 접기 연산이라고 한다.

어떤 정점 $a$ 에 대해, 간선 $(a,b)$ 와 $(a,c)$ 가 모두 존재하고 두 간선의 색이 같다면, 정점 $b$ 와 정점 $c$ 를 하나의 정점으로 병합할 수 있다. 병합 후 중복 간선은 하나로 합쳐진다.

두 트리 $X,Y$ 가 닮았다는 것은 다음 조건을 만족한다는 뜻이다.

$X$ 에 접기 연산을 $0$ 번 이상 적용하여 $X'$ 를 만들고, $Y$ 에 접기 연산을 $0$ 번 이상 적용하여 $Y'$ 를 만들었을 때, $X'$ 와 $Y'$ 가 완전히 같아지도록 만들 수 있다. 단, 한쪽 트리의 모든 간선 색을 반전한 뒤 같아지는 경우도 같다고 본다 (정점 번호는 무시함에 주의하라).

트리 $T$ 와 정수 $l,r$ $(1 \le l \le r \le N)$ 에 대해, $T[l \dots r]$ 을 정점 $l,l+1,\ldots,r$ 을 모두 포함하는 $T$ 의 최소 연결 부분트리라고 하자.

$Q$ 개의 쿼리가 주어진다. 각 쿼리는 네 정수 $l_1,r_1,l_2,r_2$ 로 이루어진다.

각 쿼리에 대해, $T_1[l_1 \dots r_1]$ 과 $T_2[l_2 \dots r_2]$ 가 닮았는지 판별하라.

Input

입력은 다음과 같은 형식으로 주어진다.

$N \ Q$ $U_1 \ V_1 \ W_1$ $U_2 \ V_1 \ W_1$ $\vdots$ $U_{N-1} \ V_{N-1} \ W_{N-1}$ $X_1 \ Y_1 \ Z_1$ $X_2 \ Y_2 \ Z_2$ $\vdots$ $X_{N-1} \ Y_{N-1} \ Z_{N-1}$ $\text{query}_1$ $\text{query}_2$ $\vdots$

$\text{query}_Q$

이는 각 $i \ (1 \leq i \leq N-1)$ 에 대해 $T_1$ 에 $U_i$ 와 $V_i$ 를 잇는 색 $W_i$ 의 간선이 존재하고, $T_2$ 에 $X_i$ 와 $Y_i$ 를 잇는 색 $Z_i$ 의 간선이 존재함을 의미한다. 색은 $0$ 이면 빨간색, $1$ 이면 파란색이다.

각각의 $\text{query}_i$ ( $1 \leq i \leq Q$ )의 형식은 다음과 같다.

$l_1 \ r_1 \ l_2 \ r_2$

Output

각각의 쿼리마다, 두 부분트리가 닮았다면 YES, 아니라면 NO를 한 줄에 하나씩 출력한다.

Constraints

$1 \leq N \leq 200 \ 000$ .
$1 \leq Q \leq 200 \ 000$ .
$1 \leq U_i \leq N$ ( $1 \leq i \leq N-1$ ).
$1 \leq V_i \leq N$ ( $1 \leq i \leq N-1$ ).
$U_i \neq V_i$ ( $1 \leq i \leq N-1$ ).
$W_i \in \{0, 1\}$ ( $1 \leq i \leq N-1$ ).
$1 \leq X_i \leq N$ ( $1 \leq i \leq N-1$ ).
$1 \leq Y_i \leq N$ ( $1 \leq i \leq N-1$ ).
$X_i \neq Y_i$ ( $1 \leq i \leq N-1$ ).
$Z_i \in \{0, 1\}$ ( $1 \leq i \leq N-1$ ).
각 간선은 트리를 이룸이 보장된다.

모든 쿼리는 다음 조건을 만족한다.

$1 \leq l_1 \leq N$ .
$1 \leq r_1 \leq N$ .
$l_1 \leq r_1$ .
$1 \leq l_2 \leq N$ .
$1 \leq r_2 \leq N$ .
$l_2 \leq r_2$ .

Subtasks

#	Score	Constraints
1	7	모든 $i \ (1 \leq i \leq N-1)$ 에 대하여 $U_i = X_i = i, V_i = Y_i = i+1$ . $W_1 = W_2 = \cdots = W_{N-1}, \ Z_1 = Z_2 = \cdots = Z_{N-1}$ .
2	10	$N \leq 2\ 000$ . 모든 $i \ (1 \leq i \leq N-1)$ 에 대하여 $U_i = X_i = i, V_i = Y_i = i+1$ .
3	16	모든 $i \ (1 \leq i \leq N-1)$ 에 대하여 $U_i = X_i = i, V_i = Y_i = i+1$ .
4	12	$W_1 = W_2 = \cdots = W_{N-1}, \ Z_1 = Z_2 = \cdots = Z_{N-1}$ .
5	15	$N \leq 2 \ 000$ .
6	40	추가적인 제약조건이 없다.

Samples

Sample 1

Input

Output

YES
NO
YES
YES

이 예제는 서브태스크 4, 5, 6의 조건을 만족한다.

Sample 2

Input

Output

YES
YES
NO
NO
YES

위 예제는 서브태스크 2, 3의 조건을 만족한다.

Sample 3

Input

Output

NO
YES
NO
NO
NO

위 예제는 서브태스크 5, 6의 조건을 만족한다.

트리 접기

Statement

Input

Output

Constraints

Subtasks

Samples