DSU Theo Cây Phiên Bản

Có $n$ đỉnh đánh số từ $0$ đến $n-1$. Phiên bản ban đầu, ký hiệu $-1$, chưa có cạnh.

Có $q$ thao tác, đánh số từ $0$ đến $q-1$. Thao tác thứ $i$ chọn một phiên bản $k$ với $-1\le k<i$, tạo phiên bản mới $i$, rồi thực hiện một trong hai loại:

• $0$ $k$ $u$ $v$: phiên bản $i$ bằng phiên bản $k$ sau khi hợp thành phần chứa $u$ và $v$.
• $1$ $k$ $u$ $v$: phiên bản $i$ giữ nguyên như phiên bản $k$; in $1$ nếu $u$ và $v$ cùng thành phần trong phiên bản đó, ngược lại in $0$.

Vì mỗi phiên bản chọn đúng một phiên bản cũ làm cha, tất cả phiên bản tạo thành một cây gốc tại phiên bản $-1$.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Mỗi trong $q$ dòng tiếp theo chứa bốn số nguyên $t$ $k$ $u$ $v$ mô tả thao tác thứ tự từ $0$.

Output

• Với mỗi thao tác có $t=1$, in $1$ hoặc $0$ trên một dòng riêng.

Constraints

• $1\le n,q\le 2\cdot 10^5$.
• $t$ bằng $0$ hoặc $1$.
• Ở thao tác thứ $i,-1\le k<i$.
• $0\le u,v<n$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4 7
0 -1 0 1
0 0 1 2
1 1 0 2
1 0 0 2
0 -1 2 3
1 4 2 3
1 1 0 3

1
0
1
0