Given a graph, support the following two operations:

Query(a_i, b_i, w_i): Does there exist a path from a_i to b_i using only edges with weight at least w_i?

Update(m_i, x_i): Update the weight of edge m_i to be x_i.

Constraints

For 2 marks, there will be no update operations.

For 3 additional marks, $M\le {10}^3$ and $Q\le {10}^3$.

Input Specification

The first line will contain two space-separated integers, $N$ $(1\le N\le {10}^3)$ and $M$ $(1\le M\le 5000)$, indicating respectively the number of vertices and the number of edges in the graph.

The next $M$ lines will contain three space-separated integers $u_i$ $(1\le u_i\le N)$, $v_i$ $(1\le v_i\le N,u_i\ne v_i)$ and $z_i$ $(1\le z_i\le {10}^9)$, indicating that edge $i$ is an undirected weighted edge between vertices $u_i$ and $v_i$ with weight $z_i$. There may be multiple edges between two vertices.

The next line will contain a single integer $Q$ $(1\le Q\le {10}^5)$, the number of operations to support.

Each of the next $Q$ lines will contain the description of either a query or an update.

An update operation, which can happen at most 2000 times, will take the form 1 m_i x_i $(1\le m_i\le M,1\le x_i\le {10}^9)$.

A query will take the form 2 a_i b_i w_i $(1\le a_i,b_i\le N,1\le w_i\le {10}^9,a_i\ne b_i)$.

Note that the operations happen in the order specified in the input.

Output Specification

For each query, print on a separate line 1 if the answer to the query is yes, and 0 otherwise.

Sample Input

3 4
1 2 3
2 3 3
2 1 1
1 2 1
6
2 1 2 4
2 2 3 2
1 1 4
2 1 2 4
1 2 1
2 2 3 2

Sample Output

0
1
1
0