Cho đồ thị \(N\) đỉnh ban đầu có \(M\) cạnh hai chiều, thực hiện \(Q\) truy vấn trong hai loại sau:

• + \(u\) \(v\): thêm cạnh giữa hai đỉnh \(u\) và \(v\)
• ? \(u\) \(v\): hỏi hai đỉnh \(u\) và \(v\) có cận kề với nhau không, hai đỉnh gọi là cận kề nếu tồn tại một đỉnh \(w\) mà có cạnh \((u, w)\) và \((w, v)\).

Input

• Dòng đầu chứa số \(N, M, Q\) (\(1\le N, M, Q \le 10^5\))

• \(M\) dòng tiếp theo mỗi dòng chứa hai số \(u, v\) mô tả các cạnh ban đầu của đồ thị

• \(Q\) dòng tiếp theo mô tả các truy vấn.

Output

• Đưa ra xâu 01 mô tả kết quả của truy vấn loại "?", 0 là không cận kề, 1 là ngược lại.

Example

8 9 9
5 8
3 1
4 8
7 5
6 2
4 3
2 3
6 1
3 8
? 6 2

+ 1 2
? 6 2
? 5 4
? 6 4
+ 8 6
? 6 4
? 4 8
? 5 2

0110110