Bài tập

Trong một vùng không gian nào đó trong vũ trụ, các tín hiệu năng lượng thu thập từ dãy vệ tinh \(A_1, A_2, \dots, A_N\) được lưu trữ như một chuỗi năng lượng.

Chuỗi này đang được theo dõi để xác định chuỗi con năng lượng tăng ổn định nhất --- chính là chuỗi con dài nhất mà mỗi phần tử đều có năng lượng lớn hơn phần tử trước nó. Ta gọi đó là chuỗi năng lượng tăng. Nói một cách cụ thể hơn, một chuỗi con \(A_{i_1}, A_{i_2}, A_{i_3}, ..., A_{i_k}\) với \(i_1 < i_2 < i_3 < ... < i_k\) được gọi là chuỗi năng lượng tăng khi \(A_{i_1} < A_{i_2} < A_{i_3} < ... < A_{i_k}\).

Tuy nhiên, do tác động của các hố đen không ổn định, trạm điều khiển không gian thực hiện \(Q\) dự đoán, mỗi dự đoán là một mô phỏng việc thay đổi năng lượng tại vị trí \(p_i\) bằng giá trị mới \(x_i\) (một năng lượng giả định từ mô hình AI dự báo) hay gán \(A_{p_i} = x_i\). Nhiệm vụ của bạn là:

Với mỗi dự đoán, giả sử giá trị tại \(A_{p_i}\) bị thay đổi thành \(x_i\), hãy tính lại độ dài chuỗi năng lượng tăng dài nhất (LIS) mới. Lưu ý, mỗi dự đoán là độc lập, sau khi xử lí mỗi dự đoán, chuỗi \(A\) sẽ trở lại chuỗi ban đầu (các phần tử đều không bị thay đổi). Tuy nhiên, nếu trạm điều khiển không gian không đưa ra dự đoán nào (hay \(Q = 0\)), bạn cần phải in ra một dòng duy nhất chính là độ dài lớn nhất của chuỗi năng lượng tăng của chuỗi năng lượng \(A\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N, Q\) \((1 \leq N \leq 3 \times 10^5, 0 \leq Q \leq 3 \times 10^5)\) --- số vệ tinh và số truy vấn.
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) \((1 \leq a_i \leq 10^9)\) --- tín hiệu năng lượng ban đầu từ các vệ tinh.
• \(Q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(p_i, x_i\) \((1 \leq p_i \leq N,\ 1 \leq x_i \leq 10^9)\) --- mô tả truy vấn: giả định thay đổi \(a_{p_i} = x_i\).

Output

In ra \(Q\) dòng tương ứng với yêu cầu bài toán.

Example

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

3
3
4

Scoring

• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(Q = 0, N \leq 20\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(Q = 0, N \leq 1000\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(Q = 0, N \leq 3 \times 10^5\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(Q \leq 20, N \leq 3 \times 10^5\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm còn lại không có ràng buộc gì thêm.

Giáo sư 3M vừa mới phát hiện ra sinh vật mới chưa từng xuất hiện trước đây. Sinh vật này rất
kì lạ khi có thể thay đổi mã gen của mình. Mã gen của sinh vật được biển diễn dưới dạng một
dãy các phần tử số nguyên. Được biết trong vòng đời của sinh vật có thể biến đổi duy nhất \(1\)
lần trong đoạn gen từ \(L\) đến \(R\) bằng cách thay đổi các số nguyên trong trên dãy thành \(a_L\).
Giáo sư muốn biết với mã gen đã cho sinh vật này có thể biến đổi thành bao nhiêu mã gen
khác nhau. Các bạn hãy giúp giáo sư 3M nhé.

Input

Vào từ file văn bản GCC.INP:

• Dòng đầu ghi số nguyên dương \(n\) \((1 \leq n \leq 10^6)\)
• Dòng thứ \(2\) ghi \(n\) số nguyên \(a_i\) \((1 \leq |a_i| \leq 10^6)\).

Output

Ghi ra file văn bản GCC.OUT:

• Gồm một số nguyên dương duy nhất là số mã gen khác nhau có thể.

Example

4 1
1 2 3

4

Scoring

• \(10\%\) số test tương ứng với \(10\%\) số điểm của \(n \leq 500\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm của \(n \leq 10^3\), \(1 \leq a_i \leq 9\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm có các phần tử \(a_i\) phân biệt.
• \(20\%\) số test tương ứng với \(20\%\) số điểm của \(n \leq 10000\).
• \(30\%\) số test còn lại tương ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm

Để chuẩn bị cho ngày lễ kỷ niệm của trường, các bạn trong lớp được giao nhiệm vụ trang trí hai bên tường lớp học bằng các dải màu. Mỗi bên tường sẽ được trang trí theo một quy luật riêng, lặp lại tuần hoàn vô hạn.

Cụ thể:

• Bên trái lớp học được trang trí theo một dãy màu \(a_1, a_2, \dots, a_n\), và dãy này sẽ lặp lại vô hạn: \(a_i = a_{i+n}\) với mọi \(i\).
• Bên phải lớp học được trang trí theo một dãy màu \(b_1, b_2, \dots, b_m\), và cũng lặp lại vô hạn: \(b_i = b_{i+m}\) với mọi \(i\).

Bạn Kino là người rất tinh mắt, muốn kiểm tra mức độ khác biệt giữa hai bên tường. Cụ thể, Kino chọn ra \(k\) vị trí đầu tiên (tính từ trái sang phải) và đo độ khác biệt màu sắc giữa hai bên tường ở mỗi vị trí. Độ khác biệt giữa hai màu \(a_i\) và \(b_i\) tại cùng vị trí được xác định bằng phép toán XOR bitwise: \(a_i \oplus b_i\).

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, k\) \((1 \leq n, m \leq 10^5,\ 1 \leq k \leq 10^{18})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((0 \leq a_i \leq 10^{18})\).
• Dòng thứ ba chứa \(m\) số nguyên \(b_1, b_2, \dots, b_m\) \((0 \leq b_i \leq 10^{18})\).

Output

In ra một số nguyên duy nhất --- tổng độ khác biệt ở \(k\) vị trí đầu tiên, chia dư cho \(10^9 + 7\).

Example

10 5 30
5 16 2 10 7 2 4 20 5 12
4 11 14 23 5

435

3 2 10
1 6 4
5 2

33

Scoring

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

\hline
1 & 18 & \(k \leq 2 \cdot 10^5\)

2 & 13 & \(n\) \(mod\) \(m = 0\)

3 & 30 & \(k \le 10^9\)

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

\hline
\endtabular

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.