Bài tập

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.

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

Giáo sư hải mã Plato đã giao cho các sinh viên lập trình của mình thực hiện một bài tập thực hành sau:

Các sinh viên phải xây dựng một cấu trúc dữ liệu hỗ trợ việc quản lý Bao lồi (Convex Hull) trên một tập hợp điểm \(S\) cho trước. Chương trình nhận \(q\) truy vấn thuộc hai loại:

• Thêm điểm: Thêm một điểm với tọa độ \((x, y)\) vào tập hợp \(S\). Lưu ý rằng trong trường hợp này, bao lồi của \(S\) có thể thay đổi hoặc giữ nguyên.
• Kiểm tra: Xác định xem một điểm với tọa độ \((x, y)\) có thuộc khu vực được giới hạn bởi bao lồi hay không, bao gồm cả biên (đường bao).

Tất cả các sinh viên đều hoàn thành nhiệm vụ. Còn bạn thì sao?

Input

• Dòng đầu tiên chứa một số nguyên \(q\) (\(4 \le q \le 10^5\)) --- số lượng truy vấn.
• Sau đó là \(q\) dòng theo định dạng: "\(t\) \(x\) \(y\)", trong đó \(t\) là loại truy vấn (1 hoặc 2), và \((x, y)\) là tọa độ của điểm (\(-10^6 \le x, y \le 10^6\), \(x\) và \(y\) là các số nguyên).

Output

Với mỗi truy vấn loại 2, in ra một chuỗi chứa "YES", nếu điểm nằm bên trong bao lồi hoặc trên biên của nó. Ngược lại, in ra "NO".

Example

8
1 0 0
1 2 0
1 2 2
2 1 0
1 0 2
2 1 1
2 2 1
2 20 -1

YES
YES
YES
NO

Scoring

• Subtask \(1\) (\(40\%\) số điểm) : \(q \leq 500\).
• Subtask \(2\) (\(30\%\) số điểm) : các thao tác loại \(1\) luôn xuất hiện trước các thao tác loại \(2\).
• Subtask \(3\) (\(30\%\) số điểm) : không có ràng buộc gì thêm.