St. Petersburg nằm trên \(n\) hòn đảo được kết nối bởi \(m\) cây cầu. Các hòn đảo được gán nhãn bởi các số nguyên từ \(1\) đến \(n\) và các cây cầu được gán nhãn từ \(1\) đến \(m\). Mỗi cây cầu nối hai hòn đảo khác nhau. Một số cây cầu được xây dựng trong thời đại Peter, và một số khác được xây dựng gần đây. Đó là lý do tại sao những cây cầu khác nhau có giới hạn trọng lượng khác nhau. Cụ thể, chỉ những chiếc xe có trọng lượng không vượt quá \(d_i\) mới có thể đi qua cây cầu \(i\). Đôi khi, một số cây cầu ở St. Petersburg đang được cải tạo, nhưng điều này không nhất thiết sẽ làm cho cây cầu chắc chắn hơn, vì vậy một số giá trị \(d_i\) có thể tăng hoặc giảm. Bạn phát triển một sản phẩm nhằm hỗ trợ cư dân và du khách của thành phố. Hiện tại, bạn phát triển một mô-đun phải thực hiện hai loại truy vấn:

1. Thay đổi giới hạn trọng lượng của cầu \(b_j\) thành \(r_j\).
2. Đếm số lượng hòn đảo có thể đi tới được từ đảo \(s_j\) bằng một chiếc xe có trọng lượng \(w_j\).

Hãy trả lời tất cả các truy vấn loại thứ hai.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) — số lượng hòn đảo và số cây cầu ở St. Petersburg (\(1\le n\le 50\,000\), \(0\le m\le 100\,000\)).

Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa ba số nguyên \(u_i\), \(v_i\) và \(d_i\), mô tả cây cầu nối hai hòn đảo \(u_i\) và \(v_i\), có giới hạn trọng lượng ban đầu là \(d_i\) (\(1\le u_i,v_i\le n\); \(u_i\ne v_i\); \(1\le d_i\le 10^9\)).

Dòng tiếp theo chứa một số nguyên \(q\) — số lượng truy vấn (\(1\le q\le 100\,000\)). Tiếp theo là \(q\) dòng chứa các truy vấn.

Mỗi truy vấn bắt đầu bằng một số nguyên \(t_j\) (\(t_j\in\{1,2\}\)).

Nếu \(t_j=1\), truy vấn là loại một, tiếp theo là hai số nguyên \(b_j\) và \(r_j\), nghĩa là giới hạn trọng lượng của cây cầu \(b_j\) sẽ thay đổi thành \(r_j\) (\(1\le b_j\le m\), \(1\le r_j\le 10^9\)).

Nếu \(t_j=2\), truy vấn là loại hai, tiếp theo là hai số nguyên \(s_j\) và \(w_j\), mô tả chiếc xe có trọng lượng \(w_j\) ở hòn đảo \(s_j\) (\(1\le s_j\le n\), \(1\le w_j\le 10^9\)).

Dữ liệu ra

Đối với mỗi truy vấn loại thứ hai, in câu trả lời trên một dòng riêng biệt.

Phân nhóm

Ví dụ

3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2

3
2
3

7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
12
2 1 6
1 1 1
2 1 2
1 2 3
2 2 2
1 5 2
1 3 1
2 2 4
2 4 2
1 8 1
2 1 1
2 1 3

1
7
7
5
7
7
4

Giải thích

Các đường màu xanh lá cây thể hiện những cây cầu mà chiếc xe ở truy vấn có thể đi qua. Các đỉnh màu xanh biểu diễn những hòn đảo có thể đi đến được bằng chiếc xe này. Mũi tên chỉ vào hòn đảo nơi chiếc xe được đặt ban đầu.

{{asset:apio19bridges/pic0.png}}

Truy vấn 1.

{{asset:apio19bridges/pic1.png}}

Truy vấn 3.

{{asset:apio19bridges/pic2.png}}

Truy vấn 5.

Hình ảnh cho ví dụ thứ nhất.

{{asset:apio19bridges/pic3.png}}

Truy vấn 1.

{{asset:apio19bridges/pic4.png}}

Truy vấn 3.

{{asset:apio19bridges/pic5.png}}

Truy vấn 5.

{{asset:apio19bridges/pic6.png}}

Truy vấn 8.

{{asset:apio19bridges/pic7.png}}

Truy vấn 9.

{{asset:apio19bridges/pic8.png}}

Truy vấn 11.

{{asset:apio19bridges/pic9.png}}

Truy vấn 12.

Hình ảnh cho ví dụ thứ hai.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2019, được lưu trong kho đề APIO.