Một quốc gia có ~n~ thành phố được đánh số từ ~0~ đến ~n - 1~. Thành phố thứ ~i~ có mức sản xuất là ~a_i~.

Có ~m~ công ty đường sắt được đánh số lần lượt từ ~0~ đến ~m - 1~. Mỗi công ty được phép xây dựng ở một số thành phố khác nhau. Công ty thứ ~i~ được xây dựng ở ~k_i~ thành phố ~s_{i_1}, s_{i_2}, ..., s_{i_{(k_i)}}~. Công ty thứ ~i~ đã xây dựng một tuyến đường sắt hai chiều nối hai thành phố ~x~ và ~y~ nếu và chỉ nếu được phép xây dựng ở cả hai thành phố.

Một vùng kinh tế là một nhóm các thành phố được nối với nhau bằng một hoặc nhiều tuyến đường sắt sao cho tồn tại một đường đi (trực tiếp hoặc qua một số thành phố trung gian) giữa hai thành phố bất kỳ trong nhóm. Sức mạnh của vùng kinh tế là tổng mức sản xuất của toàn bộ các thành phố trong vùng kinh tế đó.

Để xây dựng kế hoạch cho tương lai, chính phủ đã đề ra ~q~ kịch bản độc lập, trong đó mỗi kịch bản có thể thuộc một trong bốn loại sau:

• Loại 1: Cho phép công ty ~i~ xây dựng ở thành phố ~j~. Nếu công ty ~i~ đã được phép xây dựng ở thành phố ~j~ từ trước, kịch bản này không thay đổi gì. Ngược lại, công ty sẽ tiến hành xây dựng các tuyến đường sắt từ thành phố ~j~ đến các thành phố mà công ty được phép xây dựng từ trước đó.
• Loại 2: Không cho phép công ty ~i~ xây dựng ở thành phố ~j~. Nếu công ty ~i~ không được phép xây dựng ở thành phố ~j~ từ trước, kịch bản này không thay đổi gì. Ngược lại, các tuyến đường sắt của công ty ~i~ kết nối thành phố ~j~ sẽ bị phá bỏ.
• Loại 3: Công ty ~i~ bị phá sản và tất cả các tuyến đường sắt của công ty ~i~ bị phá bỏ.
• Loại 4: Thành phố ~i~ gặp thiên tai và tất cả các tuyến đường sắt kết nối thành phố ~i~ đều bị hỏng. Cần lưu ý rằng, kể cả trong trường hợp này, mức sản xuất của thành phố ~i~ vẫn được giữ nguyên.

Lưu ý rằng các kịch bản là độc lập và không ảnh hưởng đến các kịch bản trước và sau nó.

Yêu cầu: Tính sức mạnh của vùng kinh tế có sức mạnh lớn nhất trong quốc gia với trạng thái hiện tại và với mỗi kịch bản thay đổi trong tương lai.

Cài đặt

Thí sinh cần cài đặt các hàm sau:

long long init (int n, int m, int q, vector <int> a, vector <vector <int>> s)

Hàm này dùng để khởi tạo trạng thái hiện tại của quốc gia và được gọi trước tất cả các hàm khác. Hàm cần trả về sức mạnh của vùng kinh tế có sức mạnh lớn nhất với trạng thái quốc gia ban đầu.

Hàm này nhận vào các tham số sau:

• ~n~ - số lượng thành phố;
• ~m~ - số lượng công ty đường sắt;
• ~q~ - số lượng kịch bản thay đổi cần phải tính toán;
• ~a~ - danh sách mức sản xuất của các thành phố;
• ~s~ - danh sách các thành phố được xây dựng của các công ty đường sắt.

Giới hạn:

• ~1 \le n, m, q \le 10^5~
• ~1 \le a_i \le 10^9~
• ~1 \le |s_i| \le n~
• ~0 \le s_{i_1} < s_{i_2} < ... < s_{i_{|s_i|}} \le n - 1~
• ~|s_0| + |s_1| + ... + |s_{m - 1}| \le 5 \times 10^5~

với ~|s_i|~ là số phần tử của danh sách ~s_i~.

long long connect (int i, int j)

Hàm này cần phải trả về kết quả của kịch bản loại 1.

Hàm này nhận vào các tham số sau:

• ~i~ - chỉ số của công ty được phép xây dựng thêm;
• ~j~ - chỉ số của thành phố mà công ty ~i~ được phép xây dựng.

Giới hạn: ~0 \le i \le m - 1, 0 \le j \le n - 1~.

long long disconnect (int i, int j)

Hàm này cần phải trả về kết quả của kịch bản loại 2.

Hàm này nhận vào các tham số sau:

• ~i~ - chỉ số của công ty bị cấm xây dựng;
• ~j~ - chỉ số của thành phố mà công ty ~i~ bị cấm xây dựng.

Giới hạn: ~0 \le i \le m - 1, 0 \le j \le n - 1~.

long long bankrupt (int i)

Hàm này cần phải trả về kết quả của kịch bản loại 3.

Hàm này nhận vào tham số ~i~ - chỉ số của công ty bị phá sản.

Giới hạn: ~0 \le i \le m - 1~.

long long disaster (int i)

Hàm này cần phải trả về kết quả của kịch bản loại 4.

Hàm này nhận vào tham số ~i~ - chỉ số của thành phố bị thiên tai.

Giới hạn: ~0 \le i \le n - 1~.

Hàm init được gọi duy nhất một lần cho mỗi test trước khi bất cứ hàm nào khác được gọi. Các hàm connect, disconnect, bankrupt, disaster được gọi tổng cộng chính xác ~q~ lần trong mỗi test.

Chương trình của thí sinh cần phải gọi thư viện railwaylib.h (bằng lệnh #include "railwaylib.h") trước khi thực hiện bất cứ thao tác nào khác. Chương trình của thí sinh không được phép tương tác với luồng input và output chuẩn. Thí sinh được phép khai báo thểm hàm và biến bên ngoài, nhưng không được phép khai báo hàm có tên là main.

Ví dụ

Trong một test, chương trình của Ban tổ chức có thể gọi lần lượt các hàm như sau:

init (4, 2, 4, [15, 5, 20, 25], [[0, 2], [0, 1]]);

Lần gọi này yêu cầu chương trình của bạn khởi tạo trạng thái của quốc gia như sau:

• Có ~4~ thành phố và ~2~ công ty đường sắt. Bạn cần tính toán ~4~ kịch bản thay đổi.
• Mức sản xuất của các thành phố lần lượt là ~(15, 5, 20, 25)~.
• Công ty đường sắt ~0~ được phép xây dựng ở các thành phố ~0~ và ~2~.
• Công ty đường sắt ~1~ được phép xây dựng ở các thành phố ~0~ và ~1~.

Với trạng thái ban đầu, các thành phố ~0, 1, 2~ là một vùng kinh tế, và thành phố ~3~ là một vùng kinh tế khác. Sức mạnh lớn nhất là ~max (15 + 5 + 20, 25) = 40~. Do đó, hàm cần trả về ~40~.

connect (1, 3);

Lần gọi này yêu cầu chương trình của bạn tính toán cho kịch bản: công ty ~1~ được phép xây dựng ở thành phố ~3~. Khi này, tất cả các thành phố đều thuộc cùng một vùng kinh tế. Tổng sức mạnh của cả vùng là ~15 + 5 + 20 + 25 = 65~. Do đó, hàm cần trả về ~65~.

disaster (1);

Lần gọi này yêu cầu chương trình của bạn tính toán cho kịch bản: thành phố ~1~ bị thiên tai. Khi này, các đường sắt nối thành phố ~1~ đều bị hỏng. Do đó, các thành phố ~0, 2~ tạo thành một vùng kinh tế; thành phố ~1~ và ~3~, mỗi thành phố là một vùng kinh tế. Tổng sức mạnh lớn nhất là ~max (15 + 20, 5, 25) = 35~ nên hàm cần trả về ~35~.

disconnect (0, 0);

Lần gọi này yêu cầu chương trình của bạn tính toán cho kịch bản: công ty ~0~ không được phép xây dựng ở thành phố ~0~. Các tuyến đường sắt nối thành phố ~0~ của công ty ~0~ bị phá bỏ. Lúc này, các thành phố ~0, 1~ tạo thành một vùng kinh tế, trong khi hai thành phố ~2~ và ~3~ mỗi thành phố tạo thành một vùng kinh tế. Tổng sức mạnh lớn nhất là ~max (15 + 5, 20, 25) = 25~ nên hàm cần trả về ~25~.

bankrupt (1);

Lần gọi này yêu cầu chương trình của bạn tính toán cho kịch bản: công ty ~1~ bị phá sản. Các đường sắt của công ty ~1~ bị phá bỏ. Khi này, các thành phố được kết nối tương tự như kịch bàn trong lần gọi thứ hai. Hàm cần trả về ~35~.

Subtask

Trình chấm mẫu

Trình chấm mẫu sẽ đọc dữ liệu từ luồng nhập chuẩn (stdin) theo định dang sau:

• Dòng ~1~: ~n~ ~m~ ~q~
• Dòng ~2 + i~ ~(0 \le i \le m - 1)~: ~k_i~ ~s_{i_1}~ ~s_{i_2}~ ... ~s_{i_{k_i}}~
• Dòng ~1 + m + j~ ~(1 \le j \le q)~: thuộc một trong bốn định dạng sau:
  • ~1~ ~i~ ~j~: kịch bản loại 1, tương ứng với việc gọi hàm connect (i, j).
  • ~2~ ~i~ ~j~: kịch bản loại 2, tương ứng với việc gọi hàm disconnect (i, j).
  • ~3~ ~i~: kịch bản loại 3, tương ứng với việc gọi hàm bankrupt (i).
  • ~4~ ~i~: kịch bản loại 4, tương ứng với việc gọi hàm disaster (i).

Trình chấm mẫu sẽ ghi kết quả ra luồng xuất chuẩn (stdout) theo định dạng sau:

• Dòng ~1~: kết quả trả về khi gọi hàm init.
• Dòng ~1 + j~ ~(1 \le j \le q)~: kết quả của kịch bản thứ ~j~.

Để có được thứ tự gọi các hàm tương tự như ví dụ trên, trình chấm mẫu sẽ đọc dữ liệu sau từ luồng nhập chuẩn:

4 2 4
15 5 20 25
2 0 2
2 0 1
1 1 3
4 1
2 0 0
3 1

Nếu các hàm chạy chính xác, trình chấm mẫu sẽ ghi kết quả sau ra luồng xuất chuẩn:

40
65
35
25
35

Các bạn có thể tải trình chấm và chương trình mẫu ở đây.