Bài tập

Tại trung tâm lưu trữ dữ liệu quốc gia của quốc gia LQD, giáo sư Q vừa khánh thành một hệ thống vận chuyển tài liệu tự động sử dụng các robot điện siêu nhỏ mang tên Alset. Để tối ưu hóa quy trình, các nhà đầu tư cần mô phỏng khả năng di chuyển của robot giữa các kho lưu trữ.

Hệ thống kho lưu trữ được đơn giản hóa thành một lưới ô vuông vô tận trên hệ trục tọa độ \(Oxy\). Tại mỗi điểm có tọa độ nguyên \((x, y)\) đều có một điểm giao nhận tài liệu. Các con đường vận chuyển chỉ chạy dọc theo các trục tọa độ, nối các điểm \((x, y)\) với \((x, y+1)\) và \((x+1, y)\).

Robot Alset di chuyển từ một điểm giao nhận này sang một điểm giao nhận liền kề mất đúng \(1\) đơn vị năng lượng (tương ứng với khoảng cách Manhattan là \(1\)). Cụ thể, xe tiêu tốn \(|x-u| + |y-v|\) đơn vị năng lượng để đi giữa hai điểm \((x, y)\) và \((u, v)\).

Trung tâm có \(n\) trạm nạp năng lượng đặc biệt, trạm thứ \(i\) được đặt tại tọa độ \((x_i, y_i)\). Mỗi khi dừng tại một trạm nạp, robot sẽ được sạc đầy năng lượng lên mức \(w\) (với \(w\) là dung lượng tối đa của pin). Một robot chỉ có thể di chuyển giữa hai điểm nếu năng lượng cần thiết không vượt quá dung lượng pin hiện có. Trong quá trình di chuyển từ trạm \(s\) đến trạm \(t\), robot có thể ghé thăm bất kỳ trạm sạc nào khác trên đường đi để nạp lại năng lượng.

Hệ thống cần xử lý \(q\) yêu cầu mô phỏng. Với mỗi yêu cầu thứ \(j\), bạn cần xác định dung lượng pin tối thiểu \(w\) mà robot cần có để có thể di chuyển thành công từ trạm sạc \(s_j\) đến trạm sạc \(t_j\).

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)) --- số lượng trạm sạc và số lượng yêu cầu mô phỏng.

Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\) (\(|x_i|, |y_i| \le 10^9\)) --- tọa độ của trạm sạc thứ \(i\).

Trong \(q\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(s_j\) và \(t_j\) (\(1 \le s_j, t_j \le n\)) --- chỉ số của trạm bắt đầu và trạm kết thúc trong yêu cầu thứ \(j\).

Output

In ra \(q\) dòng, mỗi dòng chứa một số nguyên duy nhất là dung lượng pin tối thiểu \(w\) tìm được cho yêu cầu tương ứng.

Example

5 3
0 0
0 0
3 3
1 2
6 8
1 2
2 3
1 5

0
3
8

Scoring

• Subtask 1 (20% số điểm): \(n, q \le 100\).
• Subtask 2 (20% số điểm): \(n, q \le 1000\).
• Subtask 3 (20% số điểm): Tất cả các trạm sạc nằm trên trục tung (\(x_i = 0\)).
• Subtask 4 (20% số điểm): Các trạm sạc chỉ nằm trên hai đường thẳng dọc sát nhau (\(0 \le x_i \le 1\)).
• Subtask 5 (20% số điểm): Không có ràng buộc gì thêm.

Cho dãy số \(a\) gồm \(n\) số nguyên đánh số từ \(1\) đến \(n\). Ban đầu dãy \(a\) gồm toàn số \(0\). Cho \(q\) truy vấn, mỗi truy vấn được cho dưới dạng hai số nguyên \(i\) và \(k\) : tăng \(a_{i}\) lên \(k\) đơn vị, \(a_{i+1}\) lên \(k - 1\) đơn vị,... \(a_{i+k−1}\) lên \(1\) đơn vị.

Hãy in ra dãy \(a\) sau khi thực hiện \(q\) truy vấn này.

Input

Dòng đầu chứa hai số nguyên dương \(n\) và \(q\) \((n, q \leq 5 \times 10^5)\).

\(q\) dòng tiếp theo, mỗi dòng tương ứng với một truy vấn là hai số nguyên \(i\) và \(k\) \((1 \leq i \leq n; 1 \leq k \leq n-i+1)\).

Output

Một dòng duy nhất là dãy \(a_{1},a_{2},...,a_{n}\) sau khi thực hiện xong \(q\) truy vấn.

Example

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

12 10 8 6 6 3 2 

Scoring

\(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 1000\).

\(30\%\) số test tương ứng với \(30\%\) số điểm mọi \(k\) trong \(q\) truy vấn bằng nhau.

\(40\%\) số test tương ứng với \(30\%\) số điểm còn lại không có ràng buộc gì thêm.

Bạn đang chơi một trò chơi điện tử nổi tiếng của Marvel có tên là Dr. Strange. Trong trò chơi này, bạn nhập vai một siêu anh hùng đang giải cứu thế giới bằng cách hấp thụ sức mạnh của các quái vật.

Bạn được cung cấp danh sách \(N\) quái vật. Quái vật thứ \(i\) xuất hiện tại thời điểm \(L_i\) và tồn tại cho đến thời điểm \(R_i\) (bao gồm cả \(L_i\) và \(R_i\)). Mỗi quái vật có một cấp độ sức mạnh \(P_i\). Nhiều quái vật có thể xuất hiện cùng một lúc.

Để chiến đấu, bạn thực hiện \(M\) lần hấp thụ sức mạnh liên tiếp theo thứ tự. Trước lần hấp thụ đầu tiên, bạn bắt đầu với một giá trị sức mạnh đã hấp thụ ban đầu là \(\text{Power}_0 = 1\) (hấp thụ từ chính bản thân bạn).

Đối với mỗi lần hấp thụ \(j = 1, 2, \ldots, m\), năng lượng khả dụng \(E_j\) của bạn tại thời điểm đó được tính theo công thức:

Trong đó, \(D_j\) là hệ số độ bền (durability), \(A_j\) là hệ số nhanh nhẹn (agility), \(F_j\) là mức độ mệt mỏi (fatigue) ở lần hấp thụ \(j\), và \(\text{Power}_{j-1}\) là tổng sức mạnh quái vật đã hấp thụ được trong lần di chuyển trước đó (\(j-1\)).

Vì bạn là Dr. Strange, bạn có khả năng du hành thời gian. Tại thời điểm \(t_j\) của lần hấp thụ thứ \(j\), với năng lượng \(E_j\) này, bạn sẽ hấp thụ sức mạnh của \(E_j\) quái vật yếu nhất (những quái vật có cấp độ sức mạnh \(P\) nhỏ nhất) đang hiện diện. Nếu tại thời điểm đó có ít hơn \(E_j\) quái vật, bạn sẽ hấp thụ tất cả chúng. Việc hấp thụ sức mạnh của chúng chỉ ảnh hưởng đến năng lượng của bạn mà không làm yếu hay loại bỏ bất kỳ quái vật nào.

Gọi \(\text{Power}_j\) là tổng sức mạnh hấp thụ được trong lần di chuyển thứ \(j\). Nhiệm vụ của bạn là xác định giá trị của \(\text{Power}_1, \text{Power}_2, \ldots, \text{Power}_m\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N, M\) -- số lượng quái vật và số lần hấp thụ (\(1 \le N, M \le 10^5\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(L_i, R_i, P_i\) -- thời điểm xuất hiện, thời điểm biến mất, và cấp độ sức mạnh của quái vật thứ \(i\) (\(1 \le L_i \le R_i \le 10^5\), \(1 \le P_i \le 10^7\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(t_j, D_j, A_j, F_j\) -- thời điểm thực hiện lần hấp thụ \(j\) và các hệ số tính toán năng lượng. Lưu ý rằng tất cả các giá trị \(t_j\) là một hoán vị của các số từ \(1\) đến \(M\) (\(1 \le t_j \le M\), \(0 \le D_j, A_j \le 10^5\), \(1 \le F_j \le 10^5\)).

Output

In ra \(M\) dòng. Mỗi dòng chứa một số nguyên duy nhất là tổng sức mạnh hấp thụ được trong lần di chuyển thứ \(j\).

Example

3 3
1 2 10
2 3 20
1 3 5
1 2 2 2
3 3 1 3
2 1 1 5

5
25
15

Scoring

• Subtask \(1\) (\(20\%\) số điểm) : \(N, M \leq 100\).
• Subtask \(2\) (\(20\%\) số điểm) : \(N, M \leq 2000\).
• Subtask \(3\) (\(20\%\) số điểm) : \(M = 1\).
• Subtask \(4\) (\(20\%\) số điểm) : \(t_j < t_{j + 1}\) với mọi \(i = 1..M-1\).
• Subtask \(5\) (\(20\%\) số điểm) : không có ràng buộc gì thêm.

Minh Anh được mời để đưa ra một bài toán khó cho cuộc thi "coding ao làng" vừa được tổ chức gần đây. Phân vân với những ý tưởng của mình, cô ấy đang cân nhắc sử dụng bài toán sau.

Bạn được cho một cây không trọng số gồm \(N\) đỉnh, với gốc là đỉnh \(1\). Mỗi đỉnh \(i\) có một giá trị \(v_i\) đi kèm. Cấu trúc cây được mô tả bởi mảng \(p_1, p_2, \dots, p_{N-1}\), trong đó \(p_i\) là cha của đỉnh \(i+1\).

Một hàm \(f(y)\) được định nghĩa cho một đỉnh \(y\) trong cây như sau:

trong đó \(d(x, y)\) là khoảng cách giữa hai đỉnh \(x\) và \(y\), còn \(S_y\) là tập các đỉnh mà \(y\) là tổ tiên của chúng.

Bạn được cho \(Q\) truy vấn, mỗi truy vấn gồm hai đỉnh \(x\) và \(y\). Với mỗi truy vấn, cần mô phỏng các thao tác sau trên cây và tính giá trị \(f(y)\):

• Gắn tất cả các đỉnh mà cha của chúng là \(x\) sang cha của \(x\).
• Loại bỏ \(x\) khỏi cây.
• Chèn lại đỉnh \(x\) vào cây, giữa \(y\) và một hậu duệ của \(y\) thuộc cây con trước đó chứa \(x\).

Nếu \(y\) là cha của \(x\), cấu trúc cây không thay đổi. Luôn đảm bảo \(x\) thuộc cây con của \(y\). Sau mỗi truy vấn, giá trị \(f(y)\) được tính trên cây đã tạm thời thay đổi, sau đó cây trở về trạng thái ban đầu.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 5 \cdot 10^5\)) --- số đỉnh của cây và số truy vấn.
• Dòng thứ hai chứa \(N\) số nguyên \(v_1, v_2, \dots, v_N\) (\(1 \le v_i \le 10^6\)) --- giá trị của từng đỉnh.
• Dòng thứ ba chứa \(N-1\) số nguyên \(p_1, p_2, \dots, p_{N-1}\) (\(1 \le p_i \le i\)) --- \(p_i\) là cha của đỉnh \(i+1\).
• Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\) (\(1 \le x, y \le N\)) --- các đỉnh liên quan đến thao tác đã mô tả.

Output

• In ra \(Q\) dòng, mỗi dòng là giá trị của hàm \(f(y)\) trên cây sau khi thực hiện thao tác của truy vấn tương ứng.

Example

3 1
1 2 3
1 2
3 1

7

3 2
4 5 6
1 1
2 1
3 1

11
11

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

2
8
26

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 21 & \(1 \le N, Q \le 1000\)

2 & 27 & Cây là một dây chuyền, \(p_i = i\) với mọi \(i\) từ \(1\) đến \(N-1\)

3 & 22 & Mỗi đỉnh là cha của nhiều nhất \(20\) đỉnh con

4 & 30 & Không có ràng buộc bổ sung

\hline
\endtabular