Có một khu rừng gồm $N$ đỉnh. Các đỉnh được đánh số từ $1$ đến $N$, và không có cạnh nào. Mỗi đỉnh $v$ có một giá trị nguyên $X_v$, ban đầu $X_v = 1$.
Hãy viết chương trình thực hiện các truy vấn dưới đây.
- 1 $a$ $b$ $c$: Nối đỉnh $a$ và $b$ bằng một cạnh có trọng số $c$. Dữ liệu vào đảm bảo kết quả của truy vấn vẫn là một khu rừng.
- 2 $a$ $b$: Loại bỏ cạnh nối giữa hai đỉnh $a$ và $b$. Dữ liệu vào đảm bảo tồn tại cạnh giữa hai đỉnh.
- 3 $a$: Đổi $X_a$ thành $1-X_a$. Sau đó, với cây chứa $a$, hãy tính giá trị sau:
- Gọi các đỉnh của cây là $v_1, v_2, \dots, v_k$. Tính $\min_{1 \le i \le k}{\left\{ \sum_{1 \le j \le k}{dist(v_i, v_j) \times X_{v_j}} \right\}}$ và in ra. $dist(v_i, v_j)$ là tổng trọng số các cạnh trên đường đi từ $v_i$ đến $v_j$.
Dữ liệu vào
Dòng đầu tiên gồm hai số nguyên $N$, $Q$ – số đỉnh và số truy vấn. $Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn.
Các số hiệu đỉnh trong các truy vấn ($a$, $b$ trong truy vấn loại 1, 2 và $a$ trong truy vấn loại 3) được mã hóa và cần được giải mã trước khi thực hiện truy vấn. Với số hiệu đỉnh cho trước là $x$, và $S$ là giá trị thu được từ truy vấn loại 3 liền trước, số hiệu đỉnh sau khi giải mã là $(x-1+S) \bmod {n} + 1$.
Dữ liệu ra
Với mỗi truy vấn loại 3, in ra giá trị tính được trên một dòng, theo thứ tự truy vấn.
Giới hạn
- $1 \le N \le 10^5$
- $1 \le Q \le 3 \times 10^5$
- $1 \le a, b \le N$
- $a \ne b$
- $1 \le c \le 10^8$
Ví dụ
Dữ liệu vào 1
3 7 1 1 2 3 1 3 1 1 3 1 2 1 3 3 1 1 2 1 2 3 2
Dữ liệu ra 1
4 0 0
Dữ liệu vào 2
5 17 1 1 5 10 1 3 1 7 1 5 2 5 1 3 4 2 2 3 1 1 4 1 6 2 5 2 3 1 3 2 3 2 1 2 1 2 3 4 2 5 1 1 4 5 2 2 3 4 1 3 5 9 3 5
Dữ liệu ra 2
18 2 0 0 9
Dữ liệu vào 3
10 37 1 2 3 6428496 1 7 10 41603701 1 2 7 61903527 1 1 6 57606292 1 2 1 43682226 1 8 2 59090781 3 6 3 10 1 10 7 15269842 3 6 3 7 1 3 10 39799671 1 3 5 28501778 3 5 2 1 10 1 6 10 37641690 2 9 6 3 8 1 6 8 89420938 3 9 2 6 3 1 9 6 17757145 2 9 3 1 1 9 26575112 2 3 8 1 2 1 19670627 2 3 5 1 1 5 12760556 2 3 4 1 4 1 36949637 3 7 2 6 9 1 6 8 74850387 2 3 8 3 3 1 7 3 77007154 3 3
Dữ liệu ra 3
274612258 215521477 187109093 171839251 211638922 68332023 151324465 224010174 0 223740409