Bài tập

Cho một đồ thị vô hướng có trọng số \(G\). Biết rằng, ban đầu tất cả các cạnh đều có trọng số bằng \(0\), có \(q\) thao tác thay đổi, mỗi thao tác mô tả bằng \(5\) số: \(i_{min},\ i_{max},\ j_{min},\ j_{max},\ w\), nghĩa là các cạnh \((i, j)\) mà \(i_{min} \le i \le i_{max} < j_{min} \le j \le j_{max}\) được thay đổi một lượng \(w\).

Yêu cầu: Tìm trọng số của cây khung nhỏ nhất của \(G\).

Input

• Dòng đầu chứa hai số nguyên \(n, q\).
• Tiếp theo là \(q\) dòng, mỗi dòng chứa \(5\) số \(i_{min},\ i_{max},\ j_{min},\ j_{max},\ w\ (1 \le i_{min} \le i_{max} < j_{min} \le j_{max} \le n; |w| \le 10^6)\).

Output

• Gồm một dòng chứa một số là trọng số cây khung nhỏ nhất của \(G\).

Example

3 2
1 1 3 3 3
1 2 3 3 -2

-2

Vũ trụ Z có \(n\) hành tinh, các hành tinh được đánh số từ \(1\) đến \(n\). Một hệ thống gồm \(m\) đường dịch chuyển, đường dịch chuyển thứ \(k\) \((1 \leq k \leq m)\) sẽ giúp di chuyển từ hành tinh \(i_k\) đến hành tinh \(j_k\) và mất chi phí là \(e(i_k, j_k)\). Một vụ nổ trong vũ trụ đã làm ảnh hưởng lớn đến tất cả các hành tinh, trừ hành tinh số \(1\). Hành tinh số \(1\) lên kế hoạch cứu hộ cho \(n - 1\) hành tinh còn lại.

Các nhà khoa học ở hành tinh số \(1\) đã tìm ra cách di chuyển giúp đội cứu hộ có thể di chuyển đến một hành tinh khác với chi phí nhỏ hơn. Cụ thể, với số nguyên không âm \(a\) mà các nhà khoa học thiết đặt, giả sử đội cứu hộ lần lượt di chuyển qua dãy gồm \(p\) hành tinh \(1 = x_1, x_2, \ldots, x_p\). Như vậy, đội cứu hộ sẽ phải sử dụng \(p - 1\) đường dịch chuyển, gọi \(s_1\) là tổng chi phí của \(p - 1\) đường dịch chuyển, gọi \(r_1\) là tổng chi phí của \(a\) đường dịch chuyển có chi phí lớn nhất trong \(p - 1\) đường dịch chuyển (nếu \(a > p - 1\) đường dịch chuyển thì tính tổng chi phí của \(p - 1\) đường dịch chuyển), khi đó đội cứu hộ sẽ mất chi phí là \(s_1 - r_1\).

Về phía các hành tinh, các nhà khoa học cũng đã tính toán ra số nguyên không âm \(b\) dựa trên mức độ ảnh hưởng của vụ nổ để xác định được chi phí di chuyển của cư dân. Cụ thể, nếu cư dân hành tinh \(i\) phải di chuyển qua dãy gồm \(q\) hành tinh \(i = y_1, y_2, \ldots, y_q\), gọi \(s_2\) là tổng chi phí của \(q - 1\) đường dịch chuyên, gọi \(r_2\) là tổng chi phí của \(b\) đường dịch chuyển có chi phí nhỏ nhất trong \(q - 1\) đường dịch chuyển (nếu \(b > q - 1\) thì tính tổng chi phí của \(q - 1\) đường dịch chuyển), khi đó cư dân sẽ mất chi phí là \(s_2 + r_2\).

Chi phí để đội cứu hộ gặp được cư dân của hành tinh \(i\) là tổng chi phí di chuyển của đội cứu hộ cộng với tổng chi phí của cư dân hành tinh \(i\) di chuyển để họ gặp được nhau.

Với mỗi hành tinh \(i\) \((2 \leq i \leq n)\), hãy tính chi phí nhỏ nhất để đội cứu hộ xuất phát từ hành tinh \(1\) có thể gặp cư dân của hành tinh \(i\).

Input

• Dòng đầu chứa bốn số \(n, m, a, b\);

• Dòng thứ \(k\) \((1 \leq k \leq m)\) trong \(m\) dòng tiếp theo chứa ba số nguyên dương \(i_k, j_k, e(i_k, j_k)\), trong đó \(1 \leq i_k \neq j_k \leq n\) và \((i_k, j_k) \leq 10^9\). Dữ liệu đảm bảo từ hành tinh \(i\) không có quá một đường dịch chuyển tới \(j\) và không tới chính nó.

Output

• Gồm một dòng chứa \(n - 1\) số, số thứ \(i\) là chi phí nhỏ nhất để đội cứu hộ có thể gặp cư dân của hành tinh \(i + 1\), nếu đội cứu hộ không thể gặp được cư dân thì đưa ra số \(-1\) tương ứng.

Example

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

0 1 2 

Scoring

• Subtask \(1\) (\(25\) điểm): \(n \leq 100\); \(m \leq 1000\); \(a = b = 0\);

• Subtask \(2\) (\(25\) điểm): \(n \leq 100\); \(m \leq 1000\); \(a = b = 1\);

• Subtask \(3\) (\(25\) điểm): \(n \leq 10^5\); \(m \leq 10^5\); \(a = b = 0\);

• Subtask \(4\) (\(25\) điểm): \(n \leq 10^5\); \(m \leq 10^5\); \(0 \leq a, b \leq 3\).

Cho dãy \(a\) gồm \(n\) số \(1\) và \(-1\), các phần tử được đánh số từ \(1\) đến \(n\).

Cho \(q\) thao tác gồm một trong hai dạng:

• Thao tác loại \(1\) có dạng "\(1\) \(i\) \(v\)" (\(1 \le i \le n\) và \(v \in \{1,-1\}\)), thao tác này sẽ gán \(a_i = v\).

• Thao tác loại \(2\) có dạng "\(2\) \(l\) \(r\) \(k\)" (\(1 \le l \le r\ le n\) và \(|k| \le n\)), thao tác này cần tìm hai số nguyên \(x,y\) thỏa mãn \(l \le x \le y \le r\) và tổng các phần tử từ \(x\) đến \(y\) của dãy \(a\) đúng bằng \(k\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n,q\) (\(1 \le n,q \le 10^5\)).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\) (\(a_i \in \{1,-1\}\)).

• Mỗi dòng trong \(q\) dòng tiếp theo chứa một thao tác theo định dạng như trên đề bài.

Output

• Với mỗi thao tác loại \(2\), in ra hai số \(x,y\) bất kì thỏa mãn điều kiện. Nếu không tồn tại đáp án, in ra "-1".

Example

5 8
1 -1 -1 1 1
2 1 4 0
2 1 4 -3
1 4 -1
2 1 5 -3
1 3 1
1 1 -1
1 5 -1
2 1 5 -3

1 2
-1
2 4
1 5

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(k = 0\) với mọi thao tác loại \(2\).

• Subtask \(2\) (\(20\%\) số điểm): \(n,q \le 5000\).

• Subtask \(3\) (\(30\%\) số điểm): không có thao tác loại \(1\).

• Subtask \(4\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Một tổ chức hoạt động bí mật có \(M\) thành viên. Tổ chức có các nhóm hoạt động được đánh số \(0\), \(1\), \(2\), ..., và trong mỗi nhóm có các nhiệm vụ khác nhau đánh số \(1\), \(2\), \(3\), ... Người đứng đầu tổ chức cần lập mã định danh cho các thành viên trong tổ chức, mỗi thành viên tương ứng với một mã. Mã định danh của một thành viên thuộc nhóm \(n\) và làm nhiệm vụ \(k\) sẽ là số dư của giá trị của hàm \(f(n, k)\) khi chia cho \(10^9 + 7\), với hàm \(f(n, k)\) được định nghĩa như sau :

\(f(n, k) = 1\) nếu \(n = 0\).

\(F(n, k) = \frac{k \times (F(0, k) + F(1,k) + ... + f(n - 1, k))}{n}\), nếu \(n \geq 1.\)

Yêu cầu: Cho danh sách các thành viên, mỗi thành viên cho biết họ hoạt động trong nhóm nào và thực hiện nhiệm vụ gì, hãy xác định mã định danh của \(M\) thành viên của tổ chức đó.

Input

• Dòng đầu tiên chứa số nguyên \(M\) (\(1 \leq M \leq 2 \times 10^5\)).

• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i, k\) cách nhau bởi dấu cách (\(1 \leq i, k \leq 2 \times 10^5\)) thể hiện mỗi thành viên hoạt động với mã nhóm \(i\) và thực hiện nhiệm vụ thứ \(k\).

Output

Gồm \(M\) dòng, mỗi dòng chứa một số nguyên là mã định danh của một thành viên, theo đúng thứ tự trong danh sách đã cho ở tệp đầu vào.

Example

4
1 13
2 213
5 45
7 56789

13
22791
1906884
460782414

Scoring

• \(20\%\) số test tương ứng với \(20\%\) số điểm của bài có : \(M \leq 2.10^5\), \(n \leq 3\), \(k \leq 2.10^5\);
• \(20\%\) số test tương ứng với \(20\%\) số điểm của bài có : \(M \leq 2.10^5\), \(n + k \leq 65\);
• \(30\%\) số test tương ứng với \(30\%\) số điểm của bài có : \(M \leq 5.10^3\), \(n, k \leq 5.10^3\);
• \(30\%\) số test tương ứng với \(30\%\) số điểm của bài có : không có ràng buộc gì thêm.