The Ell See Kay Cup tournament has ~2n~ teams, numbered from ~1~ to ~2n~ in descending order of strength (with ~1~ being the strongest). Before the tournament begins, there are ~m~ pairs of teams that are considered brothers. During the tournament, some pairs of teams may form brotherhoods or end their brotherhoods. However, to prevent relationships from affecting the tournament, at any given time during the tournament, each team can have at most one brother.

The tournament consists of two groups: Baron and Dragon, each containing ~n~ teams. As the reigning world champion, team 1T, numbered ~1~, is automatically placed in the Baron group. Meanwhile, the reigning national champion, team ELH, numbered ~2~, is automatically placed in the Dragon group. After that, the groups take turns selecting teams, starting with the Baron group. Specifically:

• In each selection round, the most recently selected team in the group will select another new team.

• If the brother of this team has not been selected yet, they will select that brother.

• If not, they will select the strongest remaining team that has not been selected.

This process repeats until each group has exactly ~n~ teams.

There are ~q~ events that occur during the tournament. Each event can be:

• Two teams become brothers.

• Two teams end their brotherhood.

• The organizers want to know which group a specific team is currently competing in.

For each query from the organizers, determine which group that team is competing in.

Input

The first line contains an integer ~t~ (~1 \leq t \leq 100)~ — the number of test cases. Each test case has the following format:

The first line contains two integers ~n~, ~m~ (~2 \le n \le 10^5~, ~0 \le m \le n~) — the number of teams in each group and the number of initial brother pairs.

Each of the next ~m~ lines contains two integers ~x_i~, ~y_i~ (~1 \le x_i, y_i \le 2n~) — a pair of initial brothers.

The next line contains an integer ~q~ (~2 \le q \le 10^5~) — the number of events.

Each of the next ~q~ lines describes an event:

• ~\texttt{+} \; i \; j~: Teams ~i~ and ~j~ become brothers (~1 \le i, j \le 2n~, ~i \ne j~). It is guaranteed that before this query, team ~i~ has no brother team, and team ~j~ has no brother team.

• ~\texttt{-} \; i \; j~: Teams ~i~ and ~j~ are no longer brothers (~1 \leq i, j \le 2n~, ~i \ne j~). It is guaranteed that before this query, team ~i~ and ~j~ are brothers.

• ~\texttt{?} \; i~: Ask which group team ~i~ is currently competing in (~1 \le i \le 2n~).

It is guaranteed that the sum of ~n~, the sum of ~m~, and the sum of ~q~ across all test cases is at most ~10^5~.

Output

For each query of the form ~\mathtt{?} \; i~, print:

• ~\mathtt{0}~ if team ~i~ belongs to the Baron group.

• ~\mathtt{1}~ if team ~i~ belongs to the Dragon group.

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

In the first test case, the events occur as follows:

• Initially, the only brother pair is ~(1, 7)~.

• After the first query, the brother pairs are ~(1, 7), (4, 9)~.

• In the second query, the teams are arranged as follows, with pairs of brothers having the same color:

• Team ~1~ goes to the Baron group.

• Team ~2~ goes to the Dragon group.

• Since team ~1~ is the most recently added team in the Baron group, and team ~7~ is the brother of team ~1~, team ~7~ goes to the Baron group.

• Since team ~2~ is the most recently added team in the Dragon group, and team ~2~ has no brothers, the strongest remaining team that has not been selected, team ~3~, goes to the Dragon group.

• Since team ~7~ is the most recently added team in the Baron group, and team ~1~ (the brother of team ~7~) has already been placed in this group, the strongest remaining team that has not been selected, team ~4~, goes to the Baron group.

• Since team ~3~ is the most recently added team in the Dragon group, and team ~3~ has no brothers, the strongest remaining team that has not been selected, team ~5~, goes to the Dragon group.

• Since team ~4~ is the most recently added team in the Baron group, and team ~9~ is the brother of team ~4~, team ~9~ goes to the Baron group.

• Since team ~5~ is the most recently added team in the Dragon group, and team ~5~ has no brothers, the strongest remaining team that has not been selected, team ~6~, goes to the Dragon group.

• Team ~8~ goes to the Baron group.

• Team ~10~ goes to the Dragon group.

  Thus, for the query ~\mathtt{?} \; 3~, we output ~\mathtt{1}~ because team ~3~ is in the Dragon group.

  • After the third query, the brother pairs are ~(1, 7), (4, 9), (6, 5)~.

  • After the fourth query, the brother pairs are ~(1, 7), (6, 5)~.

  • After the fifth query, the brother pairs are ~(6, 5)~.

  • In the sixth and seventh queries, the teams are arranged as follows:

• Team ~1~ goes to the Baron group.

• Team ~2~ goes to the Dragon group.

• Team ~3~ goes to the Baron group.

• Team ~4~ goes to the Dragon group.

• Team ~5~ goes to the Baron group.

• Since team ~4~ is the most recently added team in the Dragon group, and team ~4~ has no brothers, the strongest remaining team that has not been selected, team ~6~, goes to the Dragon group.

• Team ~5~ is the most recently added team in the Baron group. However, team ~6~, the brother of team ~5~, has already been selected in the Dragon group. Therefore, the strongest remaining team that has not been selected, team ~7~, goes to the Baron group.

• Team ~8~ goes to the Dragon group.

• Team ~9~ goes to the Baron group.

• Team ~10~ goes to the Dragon group.

  Thus, for the sixth query, we output ~\mathtt{0}~ because team ~5~ is in the Baron group; for the seventh query, we output ~\mathtt{1}~ because team ~6~ is in the Dragon group.