Bài tập

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.

Cho một mảng số nguyên \(A\) gồm \(N\) phần tử, đánh số từ \(1\) đến \(N\).
Bạn cần thực hiện \(Q\) truy vấn. Mỗi truy vấn có dạng \((l, r, x, y)\) và được hiểu như sau:

Với mọi chỉ số \(i\) thỏa \(l \le i \le r\):

• nếu \(A[i] = x\) thì gán \(A[i] := y\),
• nếu \(A[i] \ne x\) thì giữ nguyên.

Sau khi thực hiện lần lượt tất cả \(Q\) truy vấn theo đúng thứ tự đã cho, hãy in ra mảng \(A\) cuối cùng.

\InputFile

• Dòng 1 gồm hai số nguyên \(N, Q\) (\(1 \le N, Q \le 2 \cdot 10^5\)).

• Dòng 2 gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 100\)).

• \(Q\) dòng tiếp theo, mỗi dòng gồm 4 số nguyên \(l, r, x, y\) (\(1 \le l \le r \le N\), \(1 \le x, y \le 100\)).

\OutputFile
In ra \(N\) số nguyên là các phần tử của mảng \(A\) sau khi thực hiện tất cả truy vấn, cách nhau bởi dấu cách.

Example

7 3
1 2 3 2 1 2 3
1 7 2 5
3 6 1 3
1 3 3 2

1 5 2 5 3 5 3 

Sau nhiều năm chinh chiến trong lĩnh vực lập trình, Vinko quyết định rẽ hướng sang nghề làm gốm sứ. Ngay trong ngày đầu tiên, anh nhận được một nhiệm vụ vô cùng thử thách: lát sàn một hội trường lớn bằng những viên gạch gốm hình vuông.

Tuy nhiên, thay vì đặt các viên gạch sao cho các cạnh của chúng song song với các bức tường, Vinko lại xoay chúng đi một góc \(45^\circ\), sao cho các đường chéo của viên gạch song song với các cạnh của hội trường. Do đó, hình dạng lát nền sẽ trông như các viên gạch hình thoi được xếp chồng khít nhau.

Sàn của hội trường có dạng hình vuông với kích thước \(10^7 \times 10^7\) (tính theo milimét). Vinko chưa quyết định kích thước cụ thể của các viên gạch, nhưng có một số quy định: \begin itemize

• Tất cả các viên gạch đều là hình vuông, có cùng kích thước.
• Độ dài đường chéo của mỗi viên gạch là một số nguyên dương chẵn
• Viên gạch đầu tiên được đặt sao cho chạm vào tường dưới và tường bên trái.
• Các viên gạch tiếp theo được đặt sao cho cạnh của chúng khớp hoàn toàn với một cạnh của viên gạch đã đặt trước đó.
• Quá trình lát gạch tiếp tục cho đến khi phủ toàn bộ sàn nhà.

\end itemize

\begincenter

Ở hình ví dụ bên trái, điểm có tọa độ \((2,4)\) là điểm trùng với một góc của các viên gạch, nhưng hai điểm còn lại thì không. Tương tự ở hình bên phải có điểm \((4, 3)\) trùng với góc của viên gạch.
\endcenter

Vinko, ngoài tài năng làm gốm, còn là một nhạc sĩ. Anh biết rằng có một số điểm trên sàn hội trường rất quan trọng đối với âm học -- nếu tại một góc của viên gạch trùng với một trong các điểm này thì âm thanh trong hội trường sẽ được cải thiện rõ rệt.

Bạn được cung cấp \(n\) điểm trên mặt sàn (gọi là các điểm âm học). Với mỗi điểm này, hãy xác định có bao nhiêu cách chọn độ dài đường chéo (tức là bao nhiêu kích thước viên gạch hợp lệ) sao cho điểm đó sẽ trùng đúng một góc của viên gạch nào đó khi sàn được lát xong.

Input

\begin itemize

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 10^6)\) -- số lượng điểm âm học.

• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i, y_i\) \((0 \leq x_i, y_i \leq 10^7)\) -- tọa độ (theo milimét) của điểm thứ \(i\) tính từ tường bên trái và tường dưới.

Output

• Gồm \(n\) dòng, mỗi dòng in ra số cách chọn độ dài đường chéo (là số nguyên dương chẵn) sao cho điểm tương ứng nằm đúng tại một góc của viên gạch trong phương án lát sàn tương ứng.

Example

3
1 4
0 0
0 9

1
0
3

3
5 1
4 3
2 4

0
1
1

Scoring

• Subtask 1 (25 điểm): \(1 \leq n \leq 10^4\), \(0 \leq x_i, y_i \leq 100\)
• Subtask 2 (45 điểm): \(1 \leq n \leq 10^4\)
• Subtask 3 (30 điểm): Không có ràng buộc bổ sung.

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