Series ℍ𝔾𝔹ℂ𝕡𝕡_'s - Tìm 𝓒𝓸𝓭𝓮𝓻 Tài năng nhất LQDOJ #03

Rồi khi em thấy anh trong tay cùng người khác ấy
Sao em quên được khoảnh khắc đấy?
Anh bên ai hạnh phúc như vậy
Thì thôi, buông đôi tay và để anh đi
Xem như ta lần đầu chia ly
Cũng là lần cuối nghĩ suy

Thì anh cứ đi đi, hãy cứ xa em và đừng ngẫm nghĩ
Hạnh phúc ra sao, yêu thương nhường nào chỉ thêm thời gian lãng phí
Ừ thì anh cứ đi đi và đừng nhớ nhung chi
Về đâu khi ta đã lạc mất nhau?
Mình buồn vì tim mình đau

Mình buồn thì ai thấu đâu
Từng lời buông chưa hết câu
Nước mắt đã dâng khoé sầu
Đừng bên nhau nếu không vui
Em muốn thấy anh cười
Vì yêu nên em xin anh cứ đi
Bỏ mặc em ...
Trích Anh Cứ Đi Đi (Hari Won)

Khi anh p2o2HuaGiaBao nghe bài "Anh cứ đi đi" trên Youtube tại đây. Anh ấy cảm thấy rất chill sau cả năm học trên trường với \(67000\) dự án và bài tập. Bỗng nhiên, cậu dinh đến hỏi anh ta, một bài code mãi mà vẫn TLE. Câu hỏi như sau:

Hãy tìm giá trị lớn nhất của \(a_i\times a_j \times a_k\) (\(1\le i<j<k \le n\)) trong mảng có \(n\) phần tử.

Vì p2o2HuaGiaBao rất không muốn chỉ dinh do quá lười nên nhờ các bạn chỉ giúp!

Input

• Dòng \(1\) gồm một số nguyên dương \(n\) duy nhất (\(3\le n \le 10^6\))
• Dòng \(2\) gồm \(n\) số nguyên dương là các phần tử trong mảng \(a\) (\(-10^{18} \le a_i\le 10^{18}\))

Output

• Gồm \(1\) dòng duy nhất là kết quả của bài toán. Kết quả có thể rất lớn nên cần \(\text{mod}\) \(10^9 + 7\) (Lưu ý: Kết quả in ra KHÔNG được phép là số âm). (Giải thích thêm: Đề bài yêu cầu tính giá trị lớn nhất sau đó \(\text{mod}\) \(10^9 + 7\)).

Example

6
5 2 10 1 3 2

150

10
234 -15 67 89 32 78 90 -1 500 367

42939000

Scoring

• Subtask \(1\) \((20\%\) số điểm\()\): \(n\le 100\) và \(|a_i|\le 10^6\)
• Subtask \(2\) \((30\%\) số điểm\()\): \(n\le 10^5\) và \(|a_i|\le 10^6\)
• Subtask \(3\) \((50\%\) số điểm\()\): Không có ràng buộc gì thêm

Tại Summer Campus HGBCpp_ \(2026\), có các học viên tham gia tại hè như: trongphithien, PhuocThien, unknownuser00, Prototype và uou. Tại đây, các bạn học viên được thỏa sức sáng tạo và hiểu rõ bản chất, có hướng tư duy mới trong từng problem trong contest hay cả những điều nhỏ nhặt nhất như các khu vực tạp hóa, kinh doanh, ... Nhưng hoạt động này diễn ra sôi nổi tại tỉnh Cần Thơ. Nơi người ta thường gọi là Gạo trắng nước trong. Hoạt động đơn giản mà đầy ý nghĩa này được giáo sư p2o2HuaGiaBao phụ trách nhằm tạo ra các "coder" tương lai của đất nước. Một hôm, các bạn học viên vô tình lướt ngang qua đề của giáo sư p2o2HuaGiaBao nhưng các bạn lại không biết giải ra sao. Tuy nhiên, p2o2HuaGiaBao hôm ấy lại bị ốm nên không thể hướng dẫn các bạn ấy được. Bài toán như sau:
Cho hai chuỗi ký tự \(A\) và \(B\). Ta định nghĩa một đoạn con độ dài \(L\) của chuỗi \(A\) được gọi là "khớp sai lệch \(1\)" với một đoạn con cùng độ dài \(L\) của chuỗi \(B\) nếu chúng khác nhau tại tối đa một vị trí ký tự.
Yêu cầu: Tìm độ dài \(L\) lớn nhất sao cho tồn tại ít nhất một đoạn con độ dài \(L\) của \(A\) và một đoạn con độ dài \(L\) của \(B\) thỏa mãn điều kiện "khớp sai lệch \(1\)".

Input

• Dòng đầu tiên chứa chuỗi \(A\) \((1\le |A|\le 5000)\).
• Dòng thứ hai chứa chuỗi \(B\) \((1\le |B|\le 5000)\).
• Cả hai chuỗi chỉ gồm các ký tự tiếng Anh thường (a...z).

Output

• Một số nguyên duy nhất là độ dài \(L\) lớn nhất tìm được. Nếu không có đoạn con nào khớp (kể cả khi khác 1 ký tự), in ra N/A.

Example

abcdef
axcxez

3

kfgkfksvd
njnkfklnlknf

4

Một ngày đẹp trời nọ có một siêu nhân chính là p2o2HuaGiaBao. Cậu ấy thấy dân tộc HGBCpp_ bị các tên ác nhân bao vây để làm chuyện xấu nên anh ta đã chuẩn bị ra tay. Các tên ác nhân đều là đàn em của Phụng Tỷ thuộc tập đoàn Người Thượng Vì Công Lý (MSFJ). Vì anh ta thấy hành vi này quá xấu nên quyết định ra tay. Nhưng vì nhân lực của họ quá mạnh nên phải tên chiến thuật hợp lí mà cậu ta tính bằng tay không nổi nên mới code. Tuy nhiên, máy tính và các thiết bị điện tử bị hỏng nên đành nhờ các bạn hỗ trợ siêu nhân p2o2HuaGiaBao tính toán nhé! Chiến lược như sau:
Siêu nhân p2o2HuaGiaBao phải đối đầu với \(n\) tên ác nhân, những tên ác nhân này được đánh số từ \(1\) đến \(n\), mỗi tên thứ \(i\) có sức mạnh là \(a_{i}\). Siêu nhân muốn nâng cấp sức mạnh bằng cách chia \(n\) tên ác nhân thành \(k\) nhóm liên tiếp \([l_i, r_i]\) thỏa mãn các điều kiện phân chia (như \(l_1=1, r_k=n\)). Sức mạnh tăng thêm được tính bằng công thức tổng \(\sum_{i=1}^{k} f(l_i, r_i)\), trong đó \(f(x, y) = a_x - a_{x+1} + a_{x+2} - \dots \pm a_y\).Nhiệm vụ là tìm cách chia để tổng sức mạnh này là lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n,k\) (\(1\le k\le n\le 2\times 10^{5}\))
• Dòng thư hai gồm \(n\) số nguyên dương \(a_1,a_2,a_3,...,a_n\) (\(a_i\le 10^{9}\), \(1\le i\le n\))

Output

• Gồm một dòng chứa kết quả bài toán – sức mạnh tăng thêm lớn nhất của siêu nhân.

Example

5 5
1 2 3 4 5

15

10 4
4 5 8 29 5 4524 355 853 2539 2435

10027

PhuocThien, uou, p2o2HuaGiaBao và Prototype đang đứng trước một mạng lưới gồm \(n\) phòng và \(n-1\) hành lang, trong đó giữa hai phòng bất kỳ luôn có đúng một đường đi, vì vậy toàn bộ công trình tạo thành một cây có trọng số. Ban đầu mọi phòng đều có năng lượng \(0\).

Có \(q\) thao tác cần xử lý:

• Thao tác 1 x y: Gán lại năng lượng của phòng \(x\) thành \(y\).
• Thao tác 2 x: Tính tổng ảnh hưởng mà phòng \(x\) nhận được từ toàn bộ hệ thống, tức là:
  
  \[ \sum_{i=1}^{n} a_i \cdot dist(x,i) \]

Với mỗi truy vấn loại 2 x, hãy in ra đáp án tương ứng. Dữ liệu bảo đảm cây liên thông và không có chu trình. Mỗi hành lang có độ dài dương. Các truy vấn cập nhật luôn hợp lệ. Mạng lưới này được Prototype thiết kế để kiểm tra khả năng phản ứng của hệ thống trong thời gian thực. PhuocThien phụ trách phần bản đồ, uou phụ trách phần tín hiệu, còn Prototype và p2o2HuaGiaBao quan sát toàn bộ kết quả. Đây là một bài cần xử lý nhanh vì số lượng thao tác rất lớn. Hãy chú ý rằng tổng giá trị có thể vượt khỏi phạm vi 32-bit.

Input

• Dòng đầu chứa hai số nguyên \(n, q\) (\(1 \le n, q \le 10^6\)).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le n\) và \(1 \le w \le 10^6\)).
• \(q+1\) dòng sau, mỗi dòng là một thao tác 1 x y hoặc 2 x.
• Ban đầu mọi giá trị \(a_i\) đều bằng \(0\).

Output

• Với mỗi truy vấn loại 2 x, in ra một dòng là giá trị \(\sum_{i=1}^{n} a_i \cdot dist(x,i)\).

Example

5 7
1 2 3
1 3 2
2 4 4
2 5 1
1 2 3
1 4 5
2 1
1 2 0
2 5
1 3 2
2 4
2 3

44
25
18
45