Bài tập

Nhà phân phối ABC chuyên phân phối các dòng sản phẩm nổi tiếng, hiện trong kho hàng còn \(n\) sản phẩm chưa phân phối, mỗi loại sản phẩm đưuọc đánh dấu bằng một kí hiệu là một số nguyên dương (hai loại sản phẩm bất kì khác nhau thì có kí hiệu khác nhau, hai sản phẩm cùng loại thì có kí hiệu giống nhau).

Em hãy giúp nhà phân phối thống kê xem trong kho còn lại những sản phẩm nào và có bao nhiêu loại sản phẩm khác nhau.

Input

Dữ liệu vào: Từ tệp TK.INP:

• Dòng đầu ghi số nguyên dương \(n\) (\(1 \le n \le 10^6\)) --- số sản phẩm còn lại trong kho.
• Dòng thứ hai ghi \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^6\)) là kí hiệu của từng sản phẩm (cách nhau một dấu cách).

Output

Dữ liệu ra: Ghi vào tệp TK.OUT theo cấu trúc:

• Dòng đầu ghi kí hiệu các oloaij sản phẩm còn lại trong kho, ghi theo thứ tự xuất hiện trong tệp đầu vào, các số ghi cách nhau một dấu cách trống.
• Dòng thứ hai ghi một số duy nhất --- số loại sản phẩm khác nhau tìm được.

Example

8
2 3 2 1 6 3 1 2

2 3 1 6 
4

Scoring

• Có \(50\%\) số test tương ứng với \(50\%\) số điểm có \(n \leq 10^3\).
• Có \(50\%\) số test còn lại ứng với \(50\%\) số điểm của bài tương ứng với các trường hợp còn lại.

Cho một bảng số nguyên kích thước \(N \times M\) gồm các phần tử \(A_{i,j}\).
Bạn cần xử lý \(Q\) truy vấn thuộc một trong hai loại sau:

• Loại 1: 1 x1 y1 x2 y2 v.
  Tăng giá trị của mọi ô \((x,y)\) với \(x_1 \le x \le x_2\) và \(y_1 \le y \le y_2\) lên \(v\).
• Loại 2: 2 x1 y1 x2 y2 .
  Hỏi tổng các giá trị của các ô \((x,y)\) với \(x_1 \le x \le x_2\) và \(y_1 \le y \le y_2\).

Chỉ số hàng và cột được đánh số từ \(1\).

\InputFile

• Dòng đầu chứa ba số nguyên \(N, M, Q\) \((1 \le N,M \le 1000,\; 1 \le Q \le 100000)\).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên mô tả bảng \(A\).
• \(Q\) dòng tiếp theo mô tả các truy vấn theo định dạng như trên.

\OutputFile
Với mỗi truy vấn loại \(2\), in ra một dòng là tổng cần tìm.

Ràng buộc:
\begin itemize

• \(|a[i]| \le 1000\).
• Trong tất cả các truy vấn \(|v| \le 1000\).
  \end itemize

Example

3 4 4
1 2 3 4
5 6 7 8
9 10 11 12
2 1 1 3 4
1 2 2 3 4 5
2 2 1 3 3
2 1 3 2 4

78
68
32

Cho một cây gồm \(n\) đỉnh. Với mỗi đỉnh \(i\), ta biết hai giá trị:

• \(c_i\): giá trị của đỉnh nếu được tô màu đỏ;
• \(p_i\): giá trị của đỉnh nếu được tô màu xanh.

Xét đường đi ngắn nhất từ một đỉnh \(A\) đến một đỉnh \(B\) trên cây. Khi duyệt theo thứ tự các đỉnh trên đường đi, mỗi đỉnh được chọn một trong hai màu: đỏ hoặc xanh.

Một đường đi được gọi là hài hòa nếu trong suốt quá trình duyệt đường đi, tại mọi thời điểm, không màu nào "áp đảo" màu còn lại. Cụ thể, màu đỏ hoặc xanh được coi là áp đảo nếu nó xuất hiện ít nhất 3 lần nhiều hơn màu còn lại.

Giá trị của đường đi là tổng các giá trị nhận được từ các đỉnh theo màu được chọn.

Với mỗi truy vấn gồm hai đỉnh \(u\) và \(v\), hãy tìm giá trị lớn nhất có thể của một đường đi hài hòa từ \(u\) đến \(v\). Đảm bảo rằng luôn tồn tại ít nhất một cách tô hợp lệ.

\InputFile
\begin itemize

• Dòng đầu chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\)).

• Dòng thứ hai chứa \(n\) số nguyên \(c_i\) (\(-10^9 \le c_i \le 10^9\)).

• Dòng thứ ba chứa \(n\) số nguyên \(p_i\) (\(-10^9 \le p_i \le 10^9\)).

• Tiếp theo là \(n-1\) dòng, mỗi dòng chứa hai số \(u\) và \(v\) biểu thị một cạnh của cây.

• Tiếp theo là \(q\) dòng, mỗi dòng chứa hai số \(u, v\) --- truy vấn cần trả lời.

\OutputFile

Với mỗi truy vấn, in ra giá trị lớn nhất có thể của một đường đi hài hòa từ \(u\) đến \(v\).

\Scoring

• Subtask 1 (15 điểm): \(n, q \le 15\).
• Subtask 2 (34 điểm): \(n, q \le 1000\).
• Subtask 3 (19 điểm): \(q \le 1000\).
• Subtask 4 (32 điểm): Không có ràng buộc bổ sung.

Example

5 3
2 -1 3 -1 2
-5 -4 -1 -5 -4
5 2
5 3
5 4
5 1
2 4
4 5
3 3

-3
1
3

5 3
-4 0 -5 -5 5
5 5 -4 2 2
1 5
2 3
3 4
1 3
5 4
2 5
2 4

8
10
2

Một vương quốc cổ đại được xây dựng trên những cây cầu. Cây cầu chính là xương sống của mọi kết nối trong vùng đất này, nối liền các thành phố cổ xưa lại với nhau qua những con đường cây xanh mát. Mỗi cây cầu đóng một vai trò thiết yếu trong việc duy trì sự cân bằng và bền vững của hệ thống giao thông của vương quốc.

Bạn được giao nhiệm vụ giải quyết một vấn đề liên quan đến cây cầu. Vương quốc có một cây bao gồm \(N\) đỉnh, tức là một đồ thị không có chu trình và nối liền tất cả các đỉnh. Cây này có \(M\) truy vấn, và mỗi truy vấn yêu cầu kiểm tra một loạt các cạnh mới có thể được thêm vào cây ban đầu. Nhiệm vụ của bạn là trả lời xem với mỗi truy vấn, nếu thêm các cạnh này vào cây, có bao nhiêu cạnh trong đồ thị mới sẽ trở thành cầu?

Một cạnh được gọi là cầu nếu khi loại bỏ nó, đồ thị trở nên không liên thông.

Hãy lưu ý rằng các truy vấn đều độc lập với nhau, và các cạnh thêm vào chỉ mang tính giả định, không thực sự thêm vào cây.

Input

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(2 \leq N \leq 100\,000\), \(1 \leq M \leq 100\,000\)) --- số lượng đỉnh của cây và số lượng truy vấn.

Dòng thứ hai chứa \(N-1\) số nguyên \(p_2, p_3, \ldots, p_N\) mô tả cấu trúc của cây. Cụ thể, cạnh thứ \(i\) nối đỉnh \(i+1\) với đỉnh \(p_i\).

Tiếp theo là \(M\) dòng, mỗi dòng chứa một truy vấn. Truy vấn thứ \(i\) bao gồm số nguyên đầu tiên \(K_i\) --- số cạnh sẽ thêm vào cây, tiếp theo là \(K_i\) cặp số nguyên \((x_{i,1}, y_{i,1}), (x_{i,2}, y_{i,2}), \dots, (x_{i,K_i}, y_{i,K_i})\). Mỗi cặp \((x_{i,j}, y_{i,j})\) mô tả một cạnh mới được thêm vào cây (\(1 \leq x_{i,j}, y_{i,j} \leq N\)). Tổng của \(K_i\) trong tất cả các truy vấn không vượt quá \(100\,000\).

Output

Với mỗi truy vấn, in ra một số nguyên duy nhất là số lượng cầu trong đồ thị sau khi thêm các cạnh của truy vấn vào cây.

Example

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

4
0
2
6
5
2
4
3

Scoring

• Subtask 1 (30% số điểm): \(N, M \leq 1000\).
• Subtask 2 (70% số điểm): không giới hạn gì thêm.