Giải đấu Eo Xi Cây có ~2n~ đội tuyển, được đánh số từ ~1~ đến ~2n~ theo thứ tự thực lực giảm dần (~1~ là mạnh nhất). Trước khi giải đấu bắt đầu, có ~m~ cặp đội tuyển là anh em. Trong thời gian diễn ra giải đấu, một số cặp đội tuyển có thể kết thân thành anh em hoặc chấm dứt mối quan hệ anh em của họ. Tuy nhiên, để tránh việc các mối quan hệ có thể ảnh hưởng đến giải đấu, tại một thời điểm bất kỳ trong giải đấu, mỗi đội tuyển chỉ có tối đa một anh em.

Giải đấu gồm hai bảng đấu Baron và Rồng, mỗi bảng bao gồm ~n~ đội. Với tư cách đương kim vô địch thế giới, đội Tê Đỏ được đánh số ~1~ mặc định vào bảng Baron. Trong khi đó, đương kim vô địch quốc nội, đội Hạt Lê được đánh số ~2~ mặc định vào bảng Rồng. Sau đó, các bảng lần lượt chọn đội tuyển, bắt đầu từ bảng Baron. Cụ thể:

• Ở mỗi lượt chọn, đội vừa được chọn gần nhất trong bảng sẽ chọn thêm một đội mới.

• Nếu đội anh em của đội này chưa được chọn, họ sẽ chọn đội anh em đó.

• Nếu không, họ sẽ chọn đội mạnh nhất còn lại chưa được chọn.

Quy trình lặp lại cho đến khi mỗi bảng có đúng ~n~ đội.

Có ~q~ sự kiện xảy ra trong giải đấu. Mỗi sự kiện có thể:

• Hai đội kết thân thành anh em.

• Hai đội chấm dứt quan hệ anh em.

• Ban tổ chức muốn biết một đội bất kỳ đang thi đấu ở bảng nào.

Với mỗi câu hỏi của ban tổ chức, hãy tìm ra bảng mà đội đó đang thi đấu.

Input

Dòng đầu tiên chứa một số nguyên ~t~ (~1 \leq t \leq 100)~ — số bộ test. Mỗi bộ test có dạng như sau:

Dòng đầu tiên chứa hai số nguyên ~n~, ~m~ (~2 \le n \le 10^5~, ~0 \le m \le n~) — số đội mỗi bảng và số cặp anh em ban đầu.

Mỗi trong ~m~ dòng tiếp theo chứa hai số nguyên ~x_i~, ~y_i~ (~1 \le x_i, y_i \le 2n~) — một cặp anh em ban đầu.

Dòng tiếp theo chứa một số nguyên ~q~ (~2 \le q \le 10^5~) — số sự kiện.

Mỗi trong ~q~ dòng tiếp theo mô tả một sự kiện:

• ~\texttt{+} \; i \; j~: Hai đội ~i~ và ~j~ trở thành anh em (~1 \le i, j \le 2n~, ~i \ne j~). Đảm bảo rằng trước truy vấn này, đội ~i~ không có đội anh em, và đội ~j~ không có đội anh em.

• ~\texttt{-} \; i \; j~: Hai đội ~i~ và ~j~ không còn là anh em (~1 \leq i, j \le 2n~, ~i \ne j~). Đảm bảo rằng trước truy vấn này, hai đội ~i~ và ~j~ đang là anh em.

• ~\texttt{?} \; i~: Hỏi hiện tại đội ~i~ đang thi đấu cho bảng nào (~1 \le i \le 2n~).

Đảm bảo rằng tổng của ~n~, tổng của ~m~, và tổng của ~q~ qua mọi test case không vượt quá ~10^5~.

Output

Với mỗi truy vấn dạng ~\mathtt{?} \; i~, in ra:

• ~\mathtt{0}~ nếu đội ~i~ thuộc bảng Baron.

• ~\mathtt{1}~ nếu đội ~i~ thuộc bảng Rồng.

Scoring

Sample Input 1

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

Sample Output 1

1
0
1
0
0

Notes

Ở test case thứ nhất, các sự kiện diễn ra như sau.

• Ban đầu, cặp anh em duy nhất là ~(1, 7)~.

• Sau truy vấn thứ nhất, các cặp anh em là ~(1, 7), (4, 9)~.

• Ở truy vấn thứ hai, các đội được sắp xếp như sau, với cặp đội anh em có cùng màu:

• Đội ~1~ vào bảng Baron.

• Đội ~2~ vào bảng Rồng.

• Vì đội ~1~ là đội gần nhất vào bảng Baron, và đội ~7~ là anh em của đội ~1~, đội ~7~ vào bảng Baron.

• Vì đội ~2~ là đội gần nhất vào bảng Rồng, và đội ~2~ không là anh em với đội nào, đội mạnh nhất chưa được chọn là đội ~3~ vào bảng Rồng.

• Vì đội ~7~ là đội gần nhất vào bảng Baron, và đội ~1~ là anh em của đội ~7~ đã thuộc bảng này, đội mạnh chưa được chọn là đội ~4~ vào bảng Baron.

• Vì đội ~3~ là đội gần nhất vào bảng Rồng, và đội ~3~ không là anh em với đội nào, đội mạnh nhất chưa được chọn là đội ~5~ vào bảng Rồng.

• Vì đội ~4~ là đội gần nhất vào bảng Baron, và đội ~9~ là anh em của đội ~4~, đội ~9~ vào bảng Baron.

• Vì đội ~5~ là đội gần nhất vào bảng Rồng, và đội ~5~ không là anh em với đội nào, đội mạnh nhất chưa được chọn là đội ~6~ vào bảng Rồng.

• Đội ~8~ vào bảng Baron.

• Đội ~10~ vào bảng Rồng.

  Vì thế, với truy vấn ~\mathtt{?} \; 3~, ta in ra ~\mathtt{1}~ vì đội ~3~ thuộc bảng Rồng.

  • Sau truy vấn thứ ba, các cặp anh em là ~(1, 7), (4, 9), (6, 5)~.

  • Sau truy vấn thứ tư, các cặp anh em là ~(1, 7), (6, 5)~.

  • Sau truy vấn thứ năm, các cặp anh em là ~(6, 5)~.

  • Ở truy vấn thứ sáu và bảy, các đội được sắp xếp như sau:

• Đội ~1~ vào bảng Baron.

• Đội ~2~ vào bảng Rồng.

• Đội ~3~ vào bảng Baron.

• Đội ~4~ vào bảng Rồng.

• Đội ~5~ vào bảng Baron.

• Vì đội ~4~ là đội gần nhất vào bảng Rồng, và đội ~4~ không là anh em với đội nào, đội mạnh nhất chưa được chọn là đội ~6~ vào bảng Rồng.

• Đội ~5~ là đội gần nhất vào bảng Baron. Tuy nhiên, đội anh em của đội ~5~, là đội ~6~, đã được chọn vào bảng Rồng. Vì thế, đội mạnh nhất chưa được chọn là đội ~7~ vào bảng Baron.

• Đội ~8~ vào bảng Rồng.

• Đội ~9~ vào bảng Baron.

• Đội ~10~ vào bảng Rồng.

  Vì thế, với truy vấn thứ sáu, ta in ra ~\mathtt{0}~ vì đội ~5~ thuộc bảng Baron; với truy vấn thứ bảy, ta in ra ~\mathtt{1}~ vì đội ~6~ thuộc bảng Rồng.