Problem Description

There are $ N $ cities in the country where Takahashi lives, numbered from $ 1 $ to $ N $. However, there are no means of transportation between these cities yet. Therefore, the government decided to provide subsidies to build some roads connecting different pairs of cities. Each road has an individual length. The roads built allow movement in both directions between the connected cities.

By the way, Takahashi loves even numbers. Takahashi tries to move such that the total distance traveled is an even number, even if it involves detours or passing the same road multiple times. Also, Takahashi dislikes half-measures, so he will not turn back on the road he has come from.

Takahashi will occasionally ask you whether it is possible to travel between two specified cities with an even total distance. Note that since roads are being added, the possibility of traveling with an even distance may change depending on the timing of the question.

Movement within a city is not counted towards the total travel distance.

Given the information about road construction and Takahashi's questions in chronological order, create a program to answer Takahashi's questions.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ w_1 $ $ x_1 $ $ y_1 $ $ z_1 $ $ w_2 $ $ x_2 $ $ y_2 $ $ z_2 $ : $ w_Q $ $ x_Q $ $ y_Q $ $ z_Q $

• The first line contains the number of cities $N\ (1\ ≦\ N\ ≦\ 10^5)$ and the number of information entries $Q\ (1\ ≦\ Q\ ≦\ 10^5)$, separated by a space.
• The next $ Q $ lines, where the $ i $-th line contains integers $w_i,\ x_i,\ y_i,\ z_i$ separated by spaces, representing the $ i $-th information. Each variable satisfies the following constraints:
• $1\ ≦\ w_i\ ≦\ 2$
• $1\ ≦\ x_i,\ y_i\ ≦\ N$
• $x_i\ ≠\ y_i$
• $1\ ≦\ z_i\ ≦\ 10^5$
• When $w_i\ =\ 1$, it indicates building a road of length $ z_i $ meters between city $ x_i $ and city $ y_i $.
• When $w_i\ =\ 2$, it indicates Takahashi's question about whether it is possible to travel with an even distance between city $ x_i $ and city $ y_i $. In this case, $ z_i $ is always $ 1 $.
• Multiple roads can be built between the same pair of cities.
• At the time of Takahashi's question, all previous road constructions in the input are assumed to be completed.

Output Format

The output consists of multiple lines. For each question by Takahashi, output YES if it is possible to travel between city $ x_i $ and city $ y_i $ with an even distance, and NO if it is not possible, on a single line.

Sample Input and Output

Sample Input #1

5 9
1 1 2 3
1 1 3 2
1 3 5 5
2 1 5 1
2 2 5 1
1 2 4 4
1 1 4 6
2 1 5 1
2 3 5 1

Sample Output #1

NO
YES
YES
YES

Sample Input #2

5 7
1 1 2 3
1 2 4 4
1 5 3 1
2 1 3 1
2 5 3 1
1 3 1 2
2 3 4 1

Sample Output #2

NO
NO
NO

Sample Input #3

3 6
1 1 2 1
1 1 3 3
1 2 3 2
1 2 1 2
2 1 3 1
2 2 3 1

Sample Output #3

YES
YES

Notes/Hints

Partial Points

This problem has partial points:

• If you solve the dataset where $1\ ≦\ N\ ≦\ 3,000\ ,\ 1\ ≦\ Q\ ≦\ 3,000$, you get $ 30 $ points.
• If you solve the dataset where $1\ ≦\ N\ ≦\ 10^5\ ,\ 1\ ≦\ Q\ ≦\ 10^5$, you get an additional $ 70 $ points, totaling $ 100 $ points.

Sample Explanation 1

The state of cities and roads at each question point is as follows. The left is the state at the time of the 1st and 2nd questions, and the right is the state at the time of the 3rd and 4th questions.  For the 2nd question, traveling the roads in the order $2,\ 1,\ 3,\ 5$ results in a total distance of $ 10 $. For the 3rd question, traveling the roads in the order $1,\ 4,\ 2,\ 1,\ 3,\ 5$ results in a total distance of $ 20 $. For the 4th question, traveling the roads in the order $3,\ 1,\ 2,\ 4,\ 1,\ 3,\ 5$ results in a total distance of $ 22 $.

Sample Explanation 2

At the time of the 1st question, there is no way to travel from city $ 1 $ to city $ 3 $. Therefore, the answer is NO.

Sample Explanation 3

Note that multiple roads can be built between the same pair of cities.

见题面 Input 部分

见题面 Output 部分