Bài tập

Khu đô thị mới VINNEXT gồm \(N\) biệt thự được đánh số thứ tự từ \(1\) đến \(N\), các biệt thự kết nối với nhau bởi đúng \(N-1\) đoạn đường hai chiều, mỗi đoạn đường nối trực tiếp giữa hai biệt thự. Giữa hai biệt thự bất kỳ luôn tồn tại đường đi thông qua một số đoạn đường.

Công ty xây dựng cầu đường VINTRA trúng thầu nâng cấp hệ thống giao thông của khu đô thị VINNEXT với \(M\) gói thầu khác nhau. Mỗi gói thầu \(M_i\) được xác định bởi bộ ba số \((x_i, y_i, z_i)\) và được hiểu là sẽ nâng cấp các đoạn đường trên đường đi đơn (đường đi đơn là không có đường nào đi lặp lại) từ biệt thự \(x_i\) đến biệt thự \(y_i\) và được sử dụng biệt thự \(z_i\) làm điểm tập kết vật liệu. Việc thực hiện gói thầu \(M_i\) sẽ gây ảnh hưởng tới những biệt thự nằm trên đường đi đơn từ biệt thự \(x_i\) đến biệt thự \(y_i\) (kể cả chính hai biệt thự \(x_i\) và \(y_i\)), mức độ chịu ảnh hưởng của mỗi biệt thự khi thực hiện gói thầu này chính là khoảng cách từ biệt thự đó tới điểm tập kết vật liệu \(z_i\) (khoảng cách là số đoạn đường trên đường đi đơn từ biệt thự đó đến \(z_i\)).

Yêu cầu: Bạn biết trước \(M\) gói thầu, hãy tính tổng mức độ chịu ảnh hưởng của mỗi biệt thự khi thực hiện \(M\) gói thầu này.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) \((1 \le N, M \le 3 \times 10^5)\) lần lượt là số biệt thự và số gói thầu.
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\) cho biết có đoạn đường hai chiều nối giữa hai biệt thự \(x\) và \(y\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(x_i, y_i, z_i\) \((1 \le x_i, y_i, z_i \le N)\) mô tả gói thầu \(M_i\).

Output

• Ghi ra một dòng gồm \(N\) số nguyên cách nhau một dấu cách, số thứ \(i\) là tổng mức độ chịu ảnh hưởng của biệt thự \(i\).

Example

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

2 3 2 2 4 3

Scoring

• Subtask 1 (\(25\) điểm): \(N, M \le 10^3\).
• Subtask 2 (\(25\) điểm): Mỗi biệt thự nối trực tiếp với không quá \(2\) biệt thự khác.
• Subtask 3 (\(25\) điểm): Mọi gói thầu \(i\) đều có biệt thự \(z_i\) nằm trên đường đi đơn từ \(x_i\) đến \(y_i\).
• Subtask 4 (\(25\) điểm): Không có ràng buộc gì thêm.

Sau khi sáp nhập, tỉnh Quảng Trị có quy mô dân số và diện tích tương đối lớn cùng với nhiều dư địa để phát triển. Với mục tiêu hiện đại hóa ngành nông nghiệp tỉnh nhà, hợp tác xã SEPA đã huy động các nông dân hợp tác với nhau để xây dựng những cánh đồng chuyên canh lớn, trong đó có cánh đồng chuyên trồng lúa hữu cơ được chia thành lưới gồm \(M \times N\) thửa ruộng hình vuông. Để thuận tiện trong việc áp dụng công nghệ cao vào sản xuất, các thửa ruộng trong lưới được đánh chỉ số hàng từ \(1\) đến \(M\) (từ trên xuống dưới) và chỉ số cột từ \(1\) đến \(N\) (từ trái qua phải), lúc này mỗi thửa ruộng sẽ được xác định thông qua một cặp chỉ số \((i,j)\) cho biết thửa ruộng nằm ở hàng \(i\) và cột \(j\).

Thật không may khi cánh đồng lúa xuất hiện dịch rầy nâu, lúc đầu chỉ có một con rầy nâu ở thửa ruộng \((1,1)\), sau đó đã lây lan nhanh đến tất cả các thửa ruộng khác với số lượng càng tăng. Hợp tác xã đã sử dụng một thiết bị bay thông minh để khảo sát mật độ rầy nâu trên các thửa ruộng, kết quả cho thấy hiện tại mỗi thửa ruộng ở hàng \(i\) và cột \(j\) có \(i \times j\) con rầy nâu.

Để diệt rầy nâu, hợp tác xã đã sử dụng \(P\) thiết bị bay không người lái đặc biệt, mỗi thiết bị có thể thực hiện tiêu diệt toàn bộ rầy nâu trong phạm vi lưới con hình chữ nhật gồm các thửa ruộng trong cánh đồng. Lãnh đạo hợp tác xã muốn biết sau khi sử dụng \(P\) thiết bị này thì số lượng rầy nâu còn lại chưa bị tiêu diệt là bao nhiêu.

Yêu cầu: Hãy tính số \(Q\) là số lượng rầy nâu còn lại chưa bị tiêu diệt.

Input

• Dòng đầu tiên chứa ba số nguyên \(M, N, P\) \((1 \le M, N \le 10^9; 1 \le P \le 10)\).
• Dòng thứ \(i\) trong \(P\) dòng tiếp theo, chứa bốn số nguyên dương \(x1_i, y1_i, x2_i, y2_i\) \((1 \le x1_i \le x2_i \le M; 1 \le y1_i \le y2_i \le N)\) cho biết thiết bị \(P_i\) đã diệt rầy nâu trong lưới con hình chữ nhật với thửa góc trên bên trái là \((x1_i, y1_i)\) và thửa góc dưới bên phải là \((x2_i, y2_i)\).

Output

• Ghi ra một dòng chứa số nguyên duy nhất là phần dư của phép chia \(Q\) cho \(10^9+7\).

Example

3 4 1
2 2 3 4

15

Scoring

• Subtask 1 (\(40\) điểm): \(1 \le M, N \le 10^3\); \(P = 1\).
• Subtask 2 (\(30\) điểm): \(1 \le M, N \le 10^9\); \(1 \le P \le 2\) và \(P\) lưới con hình chữ nhật không chồng lấn lên nhau.
• Subtask 3 (\(30\) điểm): Không có ràng buộc gì thêm.

Chuyển đổi số là một xu thế tất yếu với hầu hết các công việc được thực hiện trên môi trường số. Cùng với sự phát triển nhanh chóng của AI, số người tham gia làm việc và đưa thông tin lên môi trường số ngày càng nhiều, song song với đó là nhu cầu nâng cao các giải pháp bảo mật thông tin và khóa số là một trong những giải pháp.

IT làm việc cho một công ty bảo mật và đã nghĩ ra giải pháp mã hóa các chuỗi mật khẩu thành các con số như sau: Từ một xâu \(S\) đã cho chỉ chứa các chữ cái tiếng Anh, IT liệt kê ra tất cả các xâu con khác rỗng của xâu \(S\), sau đó gom các xâu con giống nhau vào cùng một cụm và đếm số lượng xâu trong mỗi cụm. Tiếp theo IT viết chương trình cho sinh ra một số ngẫu nhiên \(N\) và tính số \(T\) là tổng các lũy thừa bậc \(N\) của số lượng xâu của các cụm, \(T\) được gọi là khóa số của xâu \(S\).

Ví dụ: \(N=3\) và xâu \(S\) là "mama" thì các xâu con khác rỗng của \(S\) là: "m", "a", "m", "a", "ma", "am", "ma", "mam", "ama", "mama" được gom thành \(7\) cụm (cụm 1 chứa xâu "m" với số lượng là 2, cụm 2 chứa xâu "a" với số lượng là 2, cụm 3 chứa xâu "ma" với số lượng là 2, cụm 4 chứa xâu "am" với số lượng là 1, cụm 5 chứa xâu "mam" với số lượng là 1, cụm 6 chứa xâu "ama" với số lượng là 1, cụm 7 chứa xâu "mama" với số lượng là 1). Khi này tổng \(T = 2^3 + 2^3 + 2^3 + 1^3 + 1^3 + 1^3 + 1^3 = 28\).

Yêu cầu: Bạn được cho một xâu \(S\) và số \(N\), hãy lập trình tìm khóa số \(T\) tương ứng với xâu \(S\).

Input

• Gồm một dòng duy nhất chứa xâu ký tự \(S\) và số nguyên dương \(N\) cách nhau bởi một dấu cách (độ dài xâu \(S\) không vượt quá \(10^4\), \(1 \le N \le 10^9\)).

Output

• Ghi ra một số nguyên duy nhất là phần dư của phép chia \(T\) cho \(10^9+7\).

Example

mama 3

28

Scoring

• Subtask 1 (\(30\) điểm): Độ dài xâu \(S\) không vượt quá \(10^2\).
• Subtask 2 (\(30\) điểm): Độ dài xâu \(S\) không vượt quá \(10^3\).
• Subtask 3 (\(40\) điểm): Không có ràng buộc gì thêm.

Khi hành lang cứu trợ đã được xác định, trung tâm cần chuyển từ hoạt động cơ động sang vận hành lâu dài và mở rộng hệ thống cứu trợ. Một mạng vận chuyển cố định được xây dựng để duy trì phân phối vật tư lâu dài, phục vụ đồng thời nhiều điểm phân phối.

Hệ thống mạng vận chuyển cố định gồm \(N\) điểm được đánh số từ \(1\) đến \(N\) và \(N-1\) đoạn đường hai chiều, mỗi đoạn nối trực tiếp \(2\) điểm. Giữa \(2\) điểm bất kỳ trong hệ thống luôn tồn tại đường đi và hệ thống được xem như một cây. Điểm \(1\) là trung tâm điều hành. Mỗi điểm \(i\) có chỉ số hiệu quả là \(A_i\) nếu được chọn làm điểm phân phối vật tư. Chỉ số này có thể có âm do điều kiện mặt bằng, nhân lực hoặc chi phí vận hành tại điểm đó không thuận lợi. Mỗi đoạn đường nối trực tiếp từ điểm \(u\) đến điểm \(v\) có một chi phí kích hoạt \(c\). Để phục vụ một điểm phân phối \(v\), tất cả các đoạn trên đường đi từ điểm \(1\) đến điểm \(v\) phải được kích hoạt. Một đoạn chỉ phải trả chi phí kích hoạt một lần, kể cả khi đoạn đó đồng thời phục vụ nhiều điểm phân phối.

Trung tâm cần xây dựng phương án chọn đúng \(K\) điểm làm điểm phân phối vật tư. Giá trị của một phương án bằng tổng chỉ số hiệu quả của \(K\) điểm được chọn trừ đi tổng chi phí của tất cả các đoạn phải kích hoạt.

Yêu cầu: Hãy giúp trung tâm tìm một phương án có giá trị lớn nhất.

Input

• Dòng \(1\) chứa hai số nguyên \(N, K\) \((1 \le N \le 5 \times 10^4; 1 \le K \le \min(N, 50))\).
• Dòng \(2\) chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) \((-10^9 \le A_i \le 10^9)\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, c\), biểu diễn đoạn đường hai chiều nối trực tiếp từ điểm \(u\) đến điểm \(v\) có chi phí kích hoạt \(c\) \((1 \le u, v \le N; 1 \le c \le 10^9)\).

Output

• Ghi ra một dòng chứa một số nguyên duy nhất là giá trị lớn nhất của phương án tìm được.

Example

8 3
-6 5 14 6 16 2 13 11
1 2 2
2 3 13
1 4 5
3 5 17
5 6 11
5 7 5
4 8 14

6

Scoring

• Subtask 1 (\(15\) điểm): \(N \le 20\).
• Subtask 2 (\(20\) điểm): Cây có đúng \(2\) đỉnh lá.
• Subtask 3 (\(20\) điểm): \(N \le 2000, K \le 20\).
• Subtask 4 (\(45\) điểm): Không có ràng buộc gì thêm.