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