LQDOJ CUP 2022 - Round 1

Cho một dãy \(n\) số nguyên dương \(a_0, a_1, \ldots, a_{n-1}\).

Với mọi \(U\) thỏa mãn \(0 \leq U < n\): Tính tổng \(a_i \cdot a_j\) với mọi \(0\leq i,j < n, (i\text{ or }j) \leq U\).

Toán tử or ở đây biểu thị cho toán tử nhị phân OR.

Input

• Dòng đầu chứa số nguyên duy nhất là \(n\) \((1 \leq n \leq 2 \cdot 10^5)\), độ dài mảng \(a\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_0, a_1, \ldots, a_{n-1}\) \((0 < a_{i} \leq 10^7)\).

Output

• In ra \(n\) số nguyên dương trên cùng một dòng duy nhất. Số thứ \(i\) là đáp án cho \(U = i - 1\) khi chia dư cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^4\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Examples

3
1 2 8

1 9 89

5
2 3 5 5 3

4 25 70 225 246

10
19 18 16 14 16 17 8 15 9 10

361 1369 2233 4489 5353 8020 9412 15129 15552 16896

Cho cây \(n\) đỉnh, tìm cách tô các đỉnh bằng các màu từ \(1\) đến \(n\) thỏa mãn:

• Các đỉnh được tô cùng một màu tạo thành một đường đi.
• Gọi màu tô của đỉnh \(u\) là \(c_u\), thì dãy \(c_1, c_2, \ldots, c_n\) có thứ tự từ điển nhỏ nhất.

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 5 \times 10^5\)).
• Trong \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) mô tả các cạnh của cây.

Output

• In ra \(n\) số nguyên \(c_1, c_2, \ldots, c_n\) mô tả cách tô màu cây.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 5 \times 10^2\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \le 5 \times 10^3\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

1 1 1 2 3 3 2 2

Giữa năm 2023, một trường đại học tỉnh nọ tạo điều kiện cho các bạn sinh viên đi chơi trải nghiệm sinh hoạt hè. Đoàn thanh niên bao gồm \(n\) bạn tham gia, bạn thứ \(i\) sẽ có áo lớp mã số màu \(c_i\). Mỗi lớp sẽ gồm những người bạn mặc cùng màu áo và màu áo mỗi lớp là phân biệt. Mọi người đều có tinh thần tham gia để đem về chiến thắng cho cả đội.

Người quản trò sẽ tổ chức trò chơi bao gồm các bạn \(a_l, a_{l+1}, \ldots, a_r\) xếp thành hình tròn. Khi đó:

• Bạn \(a_{i+1}\) được gọi là người tiếp theo với bạn \(a_i\) với mọi \(i = l, l + 1, \ldots, r - 1\).
• Bạn \(a_l\) là người tiếp theo của bạn \(a_r\).

Khi đến lượt chơi của một bạn lớp \(X\), thì người đó có \(2\) lựa chọn:

• Loại đi người tiếp theo, nếu người đó không bạn cùng lớp thì lượt kế tiếp sẽ đi bởi người khác lớp \(X\), ngược lại thì người kế tiếp với người bị loại sẽ đi tiếp. Sau quá trình này vòng tròn sẽ giảm bơt đi một người.
• Bỏ lượt của bản thân, và tới lượt của người tiếp theo.

Các bạn trên vòng tròn sẽ lần lượt thực hiện quá trình trên cho tới khi chỉ còn lại một đội duy nhất. Lớp \(E\) dành được chiến thắng khi bất kể người nào là người bắt đầu, và chiến thuật của các đội có như thế nào, thì vẫn là đội duy nhất còn lại sau quá trình.

Để cho việc trải nghiệm sinh hoạt trở nên phong phú hơn, nhà trường quyết định tổ chức lần lượt \(q\) hoạt động sau:

• Thay đổ màu áo của các bạn \(a_l, a_{l+1}, \ldots, a_r\).
• Tạo một trò chơi gồm các bạn \(a_l, a_{l+1}, \ldots, a_r\).

Input

• Dòng đầu chứa hai số nguyên duy nhất là \(n\) và \(q\) (\(1 \leq n, q \leq 2 \cdot 10^4\)), số lượng sinh viên tham gia trải nghiệm và số lượng hoạt động nhà trường thực hiện.
• Dòng thứ hai chứa \(n\) số nguyên dương \(c_1, c_2, \ldots, c_n\) (\(0 \leq c_i \leq 10^9\)), với \(c_i\) nghĩa là mã số màu áo của bạn thứ \(i\) ban đầu đang mặc.
• Sau đó gồm \(q\) dòng miêu tả các hoạt động được thực hiện dần, mô tả một trong hai loại truy vấn như sau:
  • 1 \(l\) \(r\) \(v\): Thay đổ số màu áo của các bạn từ \(a_i\) thành \(a_i + v\) với các bạn \(i = l, l + 1, \ldots r\) (\(1 \leq l, r \leq n, |v| \leq 10^9\)).
  • 2 \(l\) \(r\): Quản trò tạo một trò chơi gồm các bạn trong đoạn [l, r], in ra màu áo lớp chiến thắng nếu tìm được, ngược lại in ra "IMPOSSIBLE".

Output

• Với mỗi truy vấn loại hai, in ra màu áo đội chiến thắng nếu tìm được, ngược lại in ra IMPOSSIBLE.

Scoring

• Subtask 1 (\(40\%\) số điểm): \(n, q \leq 10^3\).
• Subtask 2 (\(30\%\) số điểm): \(q \leq 5 \cdot 10^3\), chỉ bao gồm truy vấn loại \(2\).
• Subtask 3 (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

1
IMPOSSIBLE
IMPOSSIBLE
3