Có ~N (1 \le N \le 10000)~ thùng nước được đánh số từ ~1~ đến ~N~, giữa ~2~ thùng bất kỳ đều có một ống nối có một van có thể khóa hoặc mở. Ở trạng thái ban đầu tất cả các van đều đóng.

Bạn được cho một số truy vấn, trong đó mỗi truy vấn có ~2~ dạng:

Dạng X Y 1 có ý nghĩa là bạn cần mở van nối giữa ~2~ thùng ~X~ và ~Y~.

Dạng X Y 2 có ý nghĩa là bạn cần cho biết với trạng thái các van đang mở/khóa như hiện tại thì ~2~ thùng ~X~ và ~Y~ có thuộc cùng một nhóm bình thông nhau hay không? Hai thùng được coi là thuộc cùng một nhóm bình thông nhau nếu nước từ bình nàycó thể chảy đến được bình kia qua một số ống có van đang mở.

Input

Dòng đầu tiên chứa số nguyên ~Q~ là số truy vấn thỏa ~1 \le Q \le 50000~.

~Q~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên dương ~X, Y, Z~ với ý nghĩa có yêu cầu loại ~Z~ với ~2~ thùng ~X~ và ~Y~.

Output

Với mỗi yêu cầu dạng X Y 2 (với ~Z = 2~) bạn cần ghi ra số ~0~ hoặc ~1~ trên một dòng tùy thuộc ~2~ thùng ~X~ và ~Y~ không thuộc hoặc thuộc cùng một nhóm bình.

Samples

Sample Input 1

9
1 2 2 
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2

Sample Output 1

0
0
1
0
1
0

REF: spoj