Thi thử HSG9 TFL & TK - 2025 (lần 2)

Cho số nguyên dương \(n\), hãy kiểm tra xem nó có chia hết cho một số chính phương nào khác \(1\) hay không. Số chính phương là số có thể biểu diễn được dưới dạng bình phương của một số tự nhiên.

Input

• Gồm một dòng duy nhất chứa số nguyên dương \(n\) (\(n \le 10^9\)).

Output

• In ra YES nếu \(n\) tồn tại một ước khác \(1\) là số chính phương, ngược lại in ra NO.

Example

7

NO

12

YES

Ràng buộc

• \(40\%\) số điểm có \(n \le 10\)
• \(40\%\) số điểm tiếp theo có \(n \le 10^4\)
• \(20\%\) số điểm còn lại có \(n \le 10^9\)

Chính có một món đồ chơi giải đố cho trẻ em 5 tuổi, đồ chơi có thể được biểu diễn thành một xâu \(s\) gồm \(n\) kí tự latin thường. Một ngày, em họ của Chính đến nhà chơi và đã \(q\) lần nghịch đồ chơi của anh, lần thứ \(i\) em của Chính đã đổi tất cả các kí tự \(u_i\) trong xâu \(s\) thành kí tự \(v_i\). Sau khi phát hiện ra, Chính không chỉ không tức giận mà ngược lại còn rất hứng thú với trò nghịch ngợm của em họ. Chính quay sang đố bạn xác định xâu \(s\) cuối cùng sau \(q\) lần phá của em họ Chính.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, q\) (\(n, q \leq 10^5\)).
• Dòng thứ hai gồm một xâu \(s\), chỉ gồm các kí tự latin thường.
• Trong \(q\) dòng tiếp theo, dòng thứ \(i\) gồm hai kí tự \(u_i, v_i\).

Output

• In ra duy nhất một xâu là đáp án của bài toán.

Example

7 4
contest
et
ta
mo
no

cooaasa

4 3
aaaa
ba
ab
bc

cccc

Ràng buộc

• \(30\%\) số điểm có \(n, q \leq 10^3\).
• \(30\%\) số điểm tiếp theo thỏa mãn xâu \(s\) chỉ có duy nhất một loại kí tự.
• \(20\%\) số điểm tiếp theo thỏa mãn xâu \(s\) chỉ có hai loại kí tự.
• \(20\%\) số điểm còn lại có \(n, q \leq 10^5\).

Vương quốc dưới sự lãnh đạo của nhà vua gồm có \(n\) thành phố nằm cạnh nhau. Mỗi thành phố sẽ có cho mình \(a_i\) trạm phát điện. Với mỗi trạm điện ở thành phố thứ \(i\) nó có thể phát điện được cho các thành phố \(j\) sao cho \(|i - j| \le r\). Ta có năng lượng mà thành phố \(i\) sở hữu là số lượng trạm phát điện có thể phát được tới thành phố \(i\). Gọi độ phát triển của vương quốc là giá trị nhỏ nhất của năng lượng mà các thành phố sở hữu. Vì nhận thấy sự phát triển chưa mạnh mẽ nên nhà vua dự định sẽ cho lắp đặt thêm \(k\) trạm phát điện ở các thành phố bất kì. Hãy giúp nhà vua tính độ phát triển lớn nhất mà vương quốc có thể đạt được.

Input

• Dòng đầu chứa ba số nguyên \(n\), \(r\) và \(k\) (\(1 \le n \le 5 \cdot 10^5\); \(0 \le r \le n\); \(0 \le k \le 10^{18}\)) – Lần lượt là số thành phố, khoảng cách mà các trạm điện có thể phát tới, số trạm phát điện dự tính lắp đặt thêm.
• Dòng thứ hai gồm \(n\) số nguyên \(a_i\) (\(0 \le a_i \le 10^9\)) – Số trạm phát điện ban đầu ở các thành phố.

Output

• In ra một số nguyên duy nhất – Độ phát triển tối đa mà vương quốc có thể đạt được.

Example

5 0 6
4 1 3 2 5

4

10 2 4
2 4 3 1 1 6 6 1 2 6

11

Scoring

• \(40\%\) số điểm có \(r = 0\).
• \(30\%\) số điểm tiếp theo có \(k = 0\).
• \(20\%\) số điểm tiếp theo có \(n, k \le 2 \cdot 10^3\).
• \(10\%\) số điểm còn lại có \(n \le 5 \cdot 10^5\), \(k \le 10^{18}\).

Sau nhiều năm cày cuốc, Chính đã mua được cho mình một căn biệt thự to bự. Hôm nay là ngày họp mặt đại gia đình, họ hàng; vì biệt thự của Chính vô cùng rộng rãi, thoáng mát và thư giãn nên mọi người đã chốt địa điểm họp ở đó. Nhưng vì chính quá béo nên đã ngủ quên tới chiều, trong lúc mọi người đang đứng chờ ở trước cổng biệt thự. Quá bức xúc, mọi người quyết định tự mình tìm cách mở cổng thay vì chờ Chính.

Cổng biệt thự bị khóa bằng một loại ổ khóa đặc biệt, mật khẩu là một số nguyên dương \(x\). Trên cổng vô tình có một tờ giấy gợi ý ghi: \(F(x) = a\) với \(a\) là một số nguyên dương cho trước. Trên tờ giấy đó cũng có định nghĩa \(F(x)\) là tổng các ước số nguyên dương \(k\) của \(x\) thỏa mãn điều kiện \(k\) và \(\frac{x}{k}\) nguyên tố cùng nhau. Bạn hãy giúp người thân của Chính xác định được mật khẩu \(x\) để mở khóa cổng biệt thự, do có thể có nhiều hơn một giá trị thỏa mãn \(F(x) = a\), mật khẩu chính là giá trị \(x\) nhỏ nhất.

Input

• Gồm một dòng duy nhất chứa số nguyên dương \(a\) (\(a \le 10^{10}\)).
• Dữ liệu vào đảm bảo luôn tồn tại mật khẩu \(x\).

Output

• Gồm một dòng duy nhất chứa kết quả của bài toán.

Example

3

2

12

6

Scoring

• \(30\%\) số điểm có \(a \le 100\).
• \(30\%\) số điểm khác có \(a \le 10^4\).
• \(40\%\) số điểm còn lại có \(a \le 10^{10}\).

Hệ thống Kiểm soát không lưu có trách nhiệm điều hướng, đảm bảo an toàn cho các chuyến bay từ lúc cất cánh đến khi hạ cánh. Một máy bay nhận được các tín hiệu điều khiển từ Hệ thống yêu cầu tăng, giảm độ cao đến độ cao \(H_i\) để tránh va chạm, các độ cao liên tiếp đảm bảo khác nhau. Cơ trưởng ghi lại nhật kí điều khiển liên tiếp trong một khoảng thời gian. Hỏi số lần nhiều nhất có thể mà máy bay bay qua độ cao nào đó.

Input

• Dòng thứ nhất chứa số nguyên dương \(N\) (\(2 \leq N \leq 10^5\)) - số lần điều khiển;
• Dòng hai ghi \(N\) số nguyên là độ cao \(H_i\) của lệnh điều khiển (\(1 \leq H_i \leq 10^9\)).

Output

• Ghi số lần nhiều nhất có thể mà máy bay bay qua độ cao nào đó.

Scoring

• Subtask 1 (\(50\%\) test) \(1 \leq N, H_i \leq 1000\)
• Subtask 2 (\(50\%\) test) \(1 \leq N, H_i \leq 10^5\)

Example

Input

5
1 2 3 2 3

Output

3

Có \(N\) em bé được xếp thành một vòng tròn, được đánh số từ \(1\) đến \(N\) theo chiều kim đồng hồ. Người ta tổ chức chia kẹo cho các em bé trong \(M\) lượt, mỗi lượt xác định một cặp chỉ số \(L\), \(R\). Tất cả các em bé được đánh số từ \(L\) đến \(R\) theo chiều kim đồng hồ sẽ được nhận 1 cái kẹo. Hỏi sau \(M\) lượt chia kẹo, thì số kẹo lớn nhất mà một em bé có thể nhận được là bao nhiêu và có bao nhiêu em bé nhận được số kẹo như vậy?

Input

• Dòng đầu tiên là số \(N, M\) (\(1 \leq N \leq 10^9; 1 \leq M \leq 10^5\)) là số em bé và số lần chia kẹo;
• \(M\) dòng tiếp theo là các cặp chỉ số \(L\), \(R\) (\(1 \leq L, R \leq N\))

Output

• Ghi 2 số là đáp số của yêu cầu trong đề bài, số kẹo lớn nhất và số em bé nhận được số kẹo đó.

Scoring

• Subtask 1 (\(60\%\)) \(N,M \leq 10^3\);
• Subtask 2 (\(20\%\)) \(N,M \leq 10^5\);
• Subtask 3 (\(20\%\)) Không ràng buộc gì thêm.

Example

Input

5 2
1 5
4 2

Output

2 4

Giải thích

• Ban đầu các em bé đều có 0 kẹo.
• Sau lượt 1, số kẹo là: \(1, 1, 1, 1, 1\)
• Sau lượt 2, số kẹo là: \(2, 2, 1, 2, 2\)