Chung kết LQDOJ Cup 2024

Một khu vực gồm \(n\) trạm phân phối hàng hoá được đánh số từ \(1\) đến \(n\). Trạm \(1\) là trung tâm kho vận, nghĩa là nơi xuất hàng hoá để cung cấp cho các trạm khác.

Có \(m\) con đường, con đường thứ \(i\) nối hai trạm \(u_i\) và \(v_i\) có thời gian di chuyển là \(w_i\). Các con đường này đảm bảo từ một trạm bất kỳ có thể đến một trạm bất kỳ khác qua một hoặc nhiều con đường, và giữa hai trạm có tối đa một con đường nối chúng.

Khi hàng hóa được phát từ trạm \(1\) tới trạm \(i\), thì thời gian dự kiến nhận được hàng bằng thời gian di chuyển nhỏ nhất từ trạm \(1\) tới trạm này.

Do một số lý do như bảo trì hoặc sự cố, một trạm \(x\) nào đó có thể bị gián đoạn hoạt động. Khi đó:

• Trạm \(x\) không nhận được hàng hoá.
• Các con đường nối đến trạm \(x\) cũng không hoạt động.

Từ đó, khi trạm \(x\) bị gián đoạn thì trong \(n\) trạm ban đầu sẽ có những trạm bị ảnh hưởng, tức là thời gian nhận hàng sẽ dài hơn so với dự kiến hoặc không thể nhận hàng.

Là một người quản lý tốt, bạn cần biết với mỗi \(x\) từ \(1\) đến \(n\), khi trạm \(x\) bị gián đoạn thì có bao nhiêu trạm bị ảnh hưởng như đã nói ở trên.

Input

• Dòng đầu gồm hai số nguyên \(n\) và \(m\) (\(2 \le n \le 2 \cdot 10^5\); \(1 \le m \le 3 \cdot 10^5\)) là số trạm và số con đường.
• Mỗi dòng trong số \(m\) dòng tiếp theo gồm ba số nguyên \(u, v, w\) (\(1 \le u, v \le n; u \neq v; 1 \le w \le 10^9\)) mô tả một con đường.

Output

• Gồm \(n\) dòng, dòng thứ \(i\) chứa một số nguyên là số trạm bị ảnh hưởng khi trạm thứ \(i\) bị gián đoạn.

Constraints

• Subtask \(1\) (\(20\%\) số điểm): \(n, m \le 10^3\).
• Subtask \(2\) (\(20\%\) số điểm): \(m = n - 1\).
• Subtask \(3\) (\(20\%\) số điểm): Mỗi trạm có đúng hai con đường nối đến nó.
• Subtask \(4\) (\(20\%\) số điểm): \(n, m \le 7 \cdot 10^3\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

4
3
2
1

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

6
2
2
1
1
1

Cho một đồ thị vô hướng gồm \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\). Ban đầu đồ thị không có cạnh.

Ta khởi gán biến \(res = 0\). Sau đó, ta sẽ thực hiện \(n - 1\) yêu cầu, mỗi yêu cầu thuộc một trong hai dạng sau:

• 1 x y: Đặt \(u = x \oplus res, v = y \oplus res\). Thêm một cạnh nối hai đỉnh \(u\) và \(v\). Dữ liệu vào đảm bảo \(1 \le u, v \le n\) và trước đó trên đồ thị không có đường đi giữa \(u\) và \(v\).
• 2 x y: Thêm một cạnh nối hai đỉnh \(x\) và \(y\). Dữ liệu vào đảm bảo \(1 \le x, y \le n\) và trước đó trên đồ thị không có đường đi giữa \(x\) và \(y\).

Dễ thấy, sau mỗi thao tác, đồ thị luôn gồm một hoặc nhiều thành phần liên thông, và mọi thành phần liên thông đều là cây. Ta gọi \(sum\_dia\) là tổng độ dài đường kính của các cây (đường kính của cây là số cạnh của đường đi có nhiều cạnh nhất trên cây). Ta thực hiện phép gán \(res \leftarrow res \oplus sum\_dia\).

Hãy in ra giá trị của biến \(res\) sau mỗi thao tác.

Nhắc lại, phép toán \(\oplus\) (xor) đối với bit được định nghĩa như sau:

• \(0 \oplus 0 = 0\)
• \(1 \oplus 0 = 1\)
• \(0 \oplus 1 = 1\)
• \(1 \oplus 1 = 0\)

Phép toán \(\oplus\) đối với các số có nhiều hơn một bit được thực hiện theo từng bit. Ví dụ:

• \(2 \oplus 3 = 1\) (\(10_2 \oplus 11_2 = 01_2\))
• \(2 \oplus 5 = 7\) (\(010_2 \oplus 101_2 = 111_2\))
• \(5 \oplus 5 = 0\) (\(101_2 \oplus 101_2 = 000_2\))

Input

• Dòng đầu chứa số nguyên \(n\) (\(2 \le n \le 2 \cdot 10^5\)).
• Mỗi dòng trong số \(n - 1\) dòng tiếp theo chứa \(3\) số nguyên \(t, x, y\) (\(1 \le t \le 2; 0 \le x, y \le 2 \cdot n\)) mô tả một thao tác.

Output

• In ra \(n - 1\) dòng, mỗi dòng là giá trị của biến \(res\) sau mỗi yêu cầu.

Example

8
1 4 8
1 3 2
1 2 6
2 5 3
2 6 3
2 7 1
1 13 6

1
3
0
4
0
5
0

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

1
3
0
4
1
4

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le n \le 10^3\).
• Subtask \(2\) (\(33\%\) số điểm): Không có yêu cầu loại \(1\).
• Subtask \(3\) (\(37\%\) số điểm): Không có ràng buộc gì thêm.

Alice và Bob vừa chơi bài với nhau. Trò chơi bao gồm \(2 \cdot n\) lá bài được đánh số lần lượt từ \(1\) đến \(2 \cdot n\). Alice nhận \(n\) lá bài trong số này, và Bob nhận \(n\) lá bài còn lại.

Trò chơi diễn ra theo lượt như sau: Alice là người đi trước. Ở lượt thứ \(i\), Alice sẽ chọn một lá bài trong số các lá còn lại của mình và đặt lên bàn, sau đó Bob cũng sẽ chọn một lá bài để đấu với lá của Alice. Nếu số trên lá bài của Bob cao hơn của Alice, Bob sẽ thắng lượt đó; ngược lại, Alice thắng. Sau đó, cả hai tiếp tục chơi các lượt tiếp theo, mỗi người còn \(n - i\) lá bài. Sau \(n\) lượt chơi, người nào thắng nhiều lượt hơn sẽ là người thắng chung cuộc. Nếu cả hai thắng cùng số lượt thì trò chơi kết thúc với kết quả hòa.

Alice và Bob đã có một đêm chơi bài vui vẻ cùng nhau, nhưng giờ Alice đã quên mất trò chơi đã diễn ra như thế nào. Alice chỉ nhớ một vài lá bài được chơi trong một số lượt và kết quả của một số lượt. Nói cách khác, Alice chỉ nhớ \(m\) mẩu thông tin, mẩu thông tin thứ \(i\) được biểu diễn bởi bộ bốn số \((p_i, a_i, b_i, r_i)\) có ý nghĩa như sau:

• \(p_i\) là số thứ tự của lượt chơi.
• \(a_i\) là số của lá bài Alice đã chơi ở lượt thứ \(p_i\). Nếu \(a_i = 0\), Alice không nhớ chính xác lá bài này.
• \(b_i\) là số của lá bài Bob đã chơi ở lượt thứ \(p_i\). Nếu \(b_i = 0\), Alice không nhớ chính xác lá bài này.
• \(r_i\) là kết quả của lượt chơi thứ \(i\). \(r_i = 0\) nếu Alice thắng và \(r_i = 1\) nếu Bob thắng.

Alice không quá xuất sắc trong việc ghi nhớ, vì vậy có thể có các lượt chơi không hợp lệ, chẳng hạn như một lá bài được chơi nhiều lần hoặc lá bài có số cao hơn lại thua. Trong các trường hợp này, sẽ không có cách chơi nào phù hợp với trí nhớ của Alice.

Alice muốn biết có bao nhiêu cách chơi hợp lệ khác nhau khớp với trí nhớ của Alice và kết quả là Alice thắng, Bob thắng hoặc cả 2 hòa. Hai cách chơi được coi là khác nhau nếu có một lượt mà Alice hoặc Bob đã chơi một lá bài trong cách này và một lá bài khác trong cách kia. Vì các số này có thể rất lớn, hãy in kết quả modulo \((10^9 + 7)\).

Input

• Dòng đầu tiên gồm một số nguyên \(t\) (\(1 \le t \le 10\)) là số test case.
• Mỗi test case có dạng:
  • Dòng đầu chứa hai số nguyên \(n\) và \(m\) (\(1 \le n \le 10^5, 0 \le m \le \min(300, n)\)).
  • Trong \(m\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(p_i, a_i, b_i, r_i\) (\(1 \le p_i \le n, 0 \le a_i, b_i \le 2 \cdot n, 0 \le r_i \le 1\)).
• Dữ liệu vào luôn đảm bảo tất cả giá trị \(p_i\) đều khác nhau.

Output

• Với mỗi test case, in ra ba số \(A, B, D\) lần lượt là số cách chơi khác nhau khớp với trí nhớ của Alice và kết quả là Alice thắng, Bob thắng và cả 2 hòa, modulo \(10^9 + 7\).

Example

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

360 360 0
12600 12600 15120
0 4 0
36 12 0
0 0 0

Scoring

• Subtask \(1\) (\(14\%\) số điểm): \(n \le 5\).
• Subtask \(2\) (\(15\%\) số điểm): \(m = 0\).
• Subtask \(3\) (\(16\%\) số điểm): \(m \le 8\) và \(a_i > 0\) hoặc \(b_i > 0\) với \(1 \le i \le m\).
• Subtask \(4\) (\(11\%\) số điểm): \(a_i = b_i = 0\) với \(1 \le i \le m\).
• Subtask \(5\) (\(12\%\) số điểm): \(n \le 10\).
• Subtask \(6\) (\(13\%\) số điểm): \(n = m\).
• Subtask \(7\) (\(19\%\) số điểm): Không có ràng buộc gì thêm.

Aroma bắt đầu học lập trình thi đấu. Theo kinh nghiệm truyền lại từ các tiền nhân, nếu Aroma giải được \(n\) bài tập có độ khó lần lượt là \(a_1, a_2, \dots, a_n\) thì Aroma sẽ đủ kinh nghiệm để đạt được kết quả tốt trong mọi kì thi.

Thời gian giải bài tập phụ thuộc trình độ của Aroma. Cụ thể, xem như Aroma có trình độ là một số nguyên \(s\), thì thời gian để Aroma giải một bài tập độ khó \(a_i\) là \(\frac{a_i}{s}\) ngày. Tuy nhiên mỗi khi Aroma giải được một bài tập thì cô sẽ ăn mừng cho đến hết ngày hôm đó và không thực hiện làm việc gì khác, nên thời gian thực tế cần bỏ ra là \(\lceil \frac{a_i}{s} \rceil\).

Trình độ ban đầu của Aroma là \(s = 1\), tuy nhiên cô có thể nâng cao trình độ của mình bằng cách tìm hiểu thêm về các kĩ năng trong lập trình thi đấu. Cụ thể Aroma có thể cải thiện \(m\) kĩ năng, mỗi kĩ năng có độ khó là \(b_1, b_2, \dots, b_m\). Khi cải thiện một kĩ năng thì trình độ \(s\) của Aroma sẽ tăng lên \(1\) đơn vị, không kể kĩ năng được cải thiện là gì.

Để cải thiện một kĩ năng \(i\) một lần thì Aroma cần dùng \(b_i\) ngày để nghiên cứu kĩ năng này. Tuy nhiên, vì trình độ ở một kĩ năng càng cao thì càng khó cải thiện, nên nếu Aroma muốn cải thiện thêm kĩ năng thứ \(i\) lần thứ \(2\) thì cần \(b_i^2\) ngày, nếu muốn cải thiện lần thứ \(3\) thì cần \(b_i^3\) ngày. Tổng quát, nếu muốn cải thiện lần thứ \(x\) thì cần \(b_i^x\) ngày.

Lưu ý rằng một khi Aroma bắt đầu giải một bài tập hoặc cải thiện một kĩ năng thì Aroma sẽ không làm việc khác cho đến khi cô hoàn thành công việc đó.

Hỏi xác định số ngày tối thiểu mà Aroma cần để hoàn thành cả \(n\) bài tập là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \le n, m \le 10^5\)) là số bài tập và số kĩ năng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) là độ khó của các bài tập.
• Dòng thứ ba chứa \(m\) số nguyên \(b_1, b_2, \dots, b_m\) (\(2 \le b_i \le 10^9\)) là độ khó của các kĩ năng.

Output

• In ra một số nguyên duy nhất là số ngày tối thiểu để Aroma giải quyết \(n\) bài tập.
• Lưu ý rằng trình độ cuối cùng của Aroma không quan trọng, chỉ cần cô giải được toàn bộ \(n\) bài tập.

Constraints

• Subtask 1 (25% số điểm): \(n \le 500\).
• Subtask 2 (25% số điểm): \(\max_{i=1}^n(a_i) - \min_{i=1}^n(a_i) \le 10^6\).
• Subtask 3 (25% số điểm): \(n \le 10000\) và \(a_i \le 10^8\).
• Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.

Example

3 2
10 20 30
2 3

25

Alice và Bob cùng nhau chơi trò chơi nối điểm trên một vòng tròn. Có \(2 \cdot n\) điểm cách đều nhau nằm trên đường tròn, các điểm được đánh số từ \(1\) đến \(2 \cdot n\) theo chiều kim đồng hồ. Hai bạn thay phiên nhau thực hiện đúng \(n\) lần nối hai điểm thỏa mãn:

• Mỗi điểm chỉ nối với đúng một điểm khác;
• Không có hai đoạn nối nào cắt nhau.

Alice và Bob đã thực hiện \(k\) lần nối \((a_1, b_1), (a_2, b_2), \dots, (a_k, b_k)\), trước mỗi lượt nối Alice muốn đếm số trạng thái kết thúc của trò chơi có thể xảy ra. Hai trạng thái kết thúc được gọi là khác nhau nếu tồn tại một điểm được nối với hai điểm khác nhau trong hai trạng thái.

Yêu cầu: Hãy giúp Alice đếm số trạng thái kết thúc có thể trước mỗi lượt nối, và sau khi kết thúc trò chơi.

Input

• Dòng đầu chứa hai số nguyên \(n, k\) (\(0 \le k \le n\));
• Dòng thứ \(t\) (\(1 \le t \le k\)) trong \(k\) dòng sau chứa hai số nguyên \(a_t, b_t\) (\(1 \le a_t, b_t \le 2 \cdot n\)). Dữ liệu đảm bảo các đoạn đã nối thỏa mãn yêu cầu trò chơi.

Output

• Gồm \(k + 1\) dòng, mỗi dòng chứa một số nguyên là số trạng thái kết thúc của trò chơi chia dư cho (\(10^9 + 7\)) trước mỗi lượt nối, và ở dòng thứ \(k + 1\) là sau khi kết thúc trò chơi.

Constraints

• Subtask \(1\) (\(05\%\) số điểm): \(n \le 5; k = 0\);
• Subtask \(2\) (\(15\%\) số điểm): \(n \le 5\);
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 5000; k = 0\);
• Subtask \(4\) (\(27\%\) số điểm): \(n \le 5000\);
• Subtask \(5\) (\(33\%\) số điểm): \(n \le 500000\);

Example

3 1
1 2

5
2