Bài tập

Bạn được cho một cây gồm \(n\) đỉnh, mỗi đỉnh được gán một số. Số tại đỉnh \(i\) được ký hiệu là \(a_i\).

Gọi hàm \(g(x, y)\) là ước số chung lớn nhất (GCD) của các số nằm trên đường đi đơn giản từ đỉnh \(x\) đến đỉnh \(y\) (bao gồm cả \(x\) và \(y\)). Đồng thời, định nghĩa \(dist(x, y)\) là số lượng đỉnh trên đường đi đơn giản giữa \(x\) và \(y\), bao gồm cả hai đỉnh \(x\) và \(y\). Lưu ý rằng \(dist(x, x) = 1\) với mọi đỉnh \(x\).

Nhiệm vụ:

• Tìm giá trị lớn nhất của \(dist(x, y)\) trong tất cả các cặp đỉnh \((x, y)\) sao cho \(g(x, y) > 1\).
• Nếu không có cặp đỉnh nào thỏa mãn \(g(x, y) > 1\), in ra \(0\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 2 \cdot 10^5)\) --- số lượng đỉnh trong cây.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq 2 \cdot 10^5)\) --- các số được gán cho các đỉnh.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) \((1 \leq x, y \leq n, x \neq y)\), biểu diễn một cạnh kết nối hai đỉnh \(x\) và \(y\).

Đảm bảo rằng các cạnh này tạo thành một cây.

Output

• In ra \(0\) nếu không tồn tại cặp đỉnh \((x, y)\) sao cho \(g(x, y) > 1\).
• Ngược lại, in ra giá trị lớn nhất của \(dist(x, y)\) trong tất cả các cặp \((x, y)\) thỏa mãn điều kiện \(g(x, y) > 1\).

Example

3
2 3 4
1 2
2 3

1

3
2 3 4
1 3
2 3

2

Scoring

• Có \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n \leq 100\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n \leq 2000\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm có \(a_{i} = 2^k\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm không có ràng buộc gì thêm.

Trong một thiên hà xa xôi, một nền văn minh cổ đại đã phát triển một hệ thống số học phức tạp để đo lường năng lượng của các vì sao. Năng lượng của một chòm sao, được biểu diễn bằng một số nguyên không âm \(a\), khi được kích hoạt bởi một hằng số vũ trụ \(b\), sẽ tạo ra một giá trị năng lượng mới. Giá trị này được tính toán bằng phép toán luỹ thừa, nhưng để tránh sự quá tải năng lượng, kết quả phải được lấy theo một modulo đặc biệt, là \(10^9 + 7\).

Tuy nhiên, có một trường hợp đặc biệt mà các nhà thiên văn học cổ đại đã ghi chép lại: khi một chòm sao có năng lượng ban đầu là 0 được kích hoạt bởi hằng số 0, nó sẽ tạo ra một năng lượng kích hoạt cơ bản bằng 1.

Bạn là một nhà toán học vũ trụ, được giao nhiệm vụ giải mã những công thức cổ đại này. Bạn cần xây dựng một chương trình để tính toán giá trị năng lượng cuối cùng cho một loạt các chòm sao và hằng số vũ trụ được đưa ra.

Yêu cầu: Cho các cặp số nguyên không âm \((a, b)\), hãy tính giá trị \(a^b \pmod{10^9 + 7}\). Lưu ý rằng theo quy tắc đặc biệt, \(0^0 = 1\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)), là số lượng câu hỏi.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a, b\) (\(0 \le a, b \le 10^9\)).

Output

• In ra \(n\) dòng, mỗi dòng chứa một số nguyên là kết quả của phép tính \(a^b \pmod{10^9 + 7}\) tương ứng với mỗi cặp \((a, b)\) trong dữ liệu vào.

Example

3
3 4
2 8
123 123

81
256
921450052

Scoring

• Subtask \(1\) (\(50\%\) số điểm) : \(n, a, b \leq 1000\).
• Subtask \(2\) (\(50\%\) số điểm) : không có ràng buộc gì thêm.

Cho hai dãy số nguyên dương đều gồm \(N\) phần tử \(A_1, A_2, \ldots, A_N\) và \(B_1, B_2, \ldots, B_N\). Một tập con \(S(K)\) được xác định là bộ chỉ số \((i_1, i_2, \ldots, i_K)\) với \(i_x \ne i_y\) (\(x \ne y\)).

Giá trị của tập \(S(K)\) là:
$
\min(A_{i_1}, A_{i_2}, \ldots, A_{i_K}) + B_{i_1} + B_{i_2} \ldots + B_{i_K}.
$

Cho trước \(K\), hãy xác định giá trị lớn nhất của tập \(S(K)\).

\InputFile
Gồm \(tc\) (\(tc \le 10\)) bộ test, mỗi bộ test có dạng như sau:

• Dòng đầu tiên gồm hai số nguyên dương \(N, K\) (\(K \le N\)).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\). \((A_i \le 10^8)\)
• Dòng thứ ba gồm \(N\) số nguyên dương \(B_1, B_2, \ldots, B_N\). \((B_i \le 10^8)\)

\OutputFile

• In ra một số nguyên duy nhất là giá trị lớn nhất của \(S(K)\).

\Scoring

• Subtask 1 (30%): \(K \le N \le 20\)
• Subtask 2 (30%): \(K \le N \le 2000\)
• Subtask 3 (40%): \(K \le N \le 100000\)

Example

1
5 2
3 7 8 6 2
9 8 1 2 10

21

Bạn đang khám phá một tòa nhà lớn gồm \(R\) hàng và \(C\) cột phòng, tạo thành một lưới ô vuông kích thước \(R \times C\). Ô ở góc trái trên là ô \((1,1)\) và ô ở góc phải dưới là \((R,C)\).

Mỗi căn phòng của tòa nhà này có một mức độ bảo vệ \(A_{i,j}\) và trong mỗi phòng có chứa một gói kẹo loại \(B_{i,j}\). Bạn sẽ bắt đầu tại một căn phòng \((x, y)\) và chỉ được phép đi qua các phòng có mức độ bảo vệ không vượt quá \(k\) thì số loại kẹo khác nhau lớn nhất bạn thu thập được là bao nhiêu.

Lưu ý rằng bạn chỉ có thể di chuyển sang các phòng kề nhau theo bốn hướng: trái, phải, trên, dưới.

Không dừng lại ở đó, tòa nhà này lại thay đổi theo thời gian, nghĩa là sẽ có thời điểm loại kẹo tại một phòng bị thay đổi. Xen giữa những lần thay đổi này, bạn được yêu cầu trả lời các câu hỏi có dạng \((x,y,a)\) như trên.

Bạn cần xử lý \(Q\) truy vấn sau:

• 1 \(x\) \(y\) \(b\) --- loại kẹo tại hàng \(x\), cột \(y\) được thay đổi thành \(b\).
• 2 \(x\) \(y\) \(a\) --- nếu bắt đầu từ phòng \((x, y)\), chỉ được đi qua các phòng có độ khó \(\le a\), hãy tính xem bạn có thể thu thập được bao nhiêu loại kẹo khác nhau trong vùng bạn đi đến.

Ràng buộc: mức độ bảo vệ của các phòng đôi một khác nhau.

\InputFile

• Dòng đầu tiên chứa ba số nguyên \(R\), \(C\), \(Q\) (\(1 \le R \times C \le 10000\))
• \(R\) dòng tiếp theo: mỗi dòng gồm \(C\) số nguyên \(A_{i,j}\) (\(1 \le A_{i,j} \le 10^9\))
• \(R\) dòng tiếp theo: mỗi dòng gồm \(C\) số nguyên \(B_{i,j}\) (\(1 \le B_{i,j} \le 10000\))

• \(Q\) dòng tiếp theo, mỗi dòng ghi lần lượt một trong hai truy vấn sau:

• 1 \(x\) \(y\) \(b\): \(1 \le x \le R, \; 1 \le y \le C, \; 1 \le b \le 10000;\)

• 2 \(x\) \(y\) \(a\): \(1 \le x \le R, \; 1 \le y \le C, \; 1 \le a \le 10^9;\)

\OutputFile

Với mỗi truy vấn loại 2, in ra một dòng --- số lượng loại phòng khác nhau bạn có thể tiếp cận được.

\Scoring

• Subtask 1 (\(10\%\) số điểm): \(R = 1\), \(1 \le Q \le 1000\), \(A_{1,j} = j\) và không có truy vấn loại 1.
• Subtask 2 (\(20\%\) số điểm): \(1 \le Q \le 100\)
• Subtask 3 (\(24\%\) số điểm): Không có truy vấn loại \(1\).
• Subtask 4 (\(20\%\) số điểm): \(R = 1\), \(1 \le Q \le 10^5\)
• Subtask 5 (\(26\%\) số điểm): Không giới hạn gì thêm

Example

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

4
3
0