Bài tập

Một mảnh vườn hình chữ nhật có hai kích thước \(a\) và \(b\). Người ta đào một cái ao hình tròn bán kính \(R\) nằm hoàn toàn bên trong mảnh vườn. Phần đất còn lại (không tính ao) dùng để trồng rau. Hãy tính diện tích phần đất trồng rau.

Dùng giá trị chính xác của hằng số \(\pi\).

Input

• Một dòng gồm ba số nguyên dương \(a, b, R\) cách nhau bởi dấu cách.

Output

• In ra diện tích phần đất trồng rau, làm tròn đến đúng \(2\) chữ số sau dấu phẩy thập phân.

Constraints

• \(1 \le a, b, R \le 10^6\)
• \(2R \le \min(a, b)\) (ao nằm trọn trong vườn)

Sample Input 1

10 6 2

Sample Output 1

47.43

Explanation

Diện tích vườn là \(60\), diện tích ao là \(4\pi \approx 12.566\), phần còn lại khoảng \(47.434\) nên làm tròn thành \(47.43\).

Có \(N\) con ốc được đánh số từ \(1\) đến \(N\); giá trị của con ốc thứ \(i\) là \(i\). Trên mỗi con ốc phải đặt một dấu \(+\) hoặc \(-\). Đếm số cách đặt dấu sao cho tổng đại số

bằng đúng số nguyên \(S\) cho trước. Hai cách được coi là khác nhau nếu có ít nhất một con ốc được đặt dấu khác nhau.

Vì kết quả có thể rất lớn, in ra phần dư khi chia cho \(998\,244\,353\).

Input

Một dòng chứa hai số nguyên \(N\) và \(S\).

Output

In ra một số nguyên là số cách, lấy modulo \(998\,244\,353\).

Constraints

• \(1 \le N \le 600\).
• \(|S| \le 10^9\).

Sample Input

4 2

Sample Output

2

Explanation

Hai cách là \(-1+2-3+4 = 2\) và \(+1+2+3-4 = 2\).

Với mỗi số nguyên dương \(x\), gọi \(d(x)\) là số ước dương của \(x\). Một dãy số nguyên dương được gọi là dãy đẹp nếu số ước của các phần tử tăng thực sự theo thứ tự trong dãy, tức là \(d(b_1) < d(b_2) < \ldots < d(b_k)\).

Cho dãy \(a_1, a_2, \ldots, a_n\). Ta được xóa một số phần tử (giữ nguyên thứ tự các phần tử còn lại) để phần còn lại là một dãy đẹp. Hãy tìm độ dài lớn nhất của dãy đẹp có thể thu được (tức là số phần tử ít nhất phải xóa là \(n\) trừ đi giá trị này).

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\).

Output

• In ra một số nguyên: số phần tử lớn nhất của dãy đẹp thu được.

Constraints

• \(1 \le n \le 5 \cdot 10^5\)
• \(1 \le a_i \le 10^9\)
• Subtask 1 (20%): \(n \le 20\), \(a_i \le 10^3\).
• Subtask 2 (40%): \(n \le 10^3\), \(a_i \le 10^6\).
• Subtask 3 (20%): \(n \le 5 \cdot 10^4\), \(a_i \le 10^6\).
• Subtask 4 (20%): không có ràng buộc thêm.

Sample Input 1

6
12 2 9 7 30 4

Sample Output 1

3

Explanation

Số ước của từng phần tử là \(6, 2, 3, 2, 8, 3\). Có thể giữ lại các phần tử \(2, 9, 30\) (số ước \(2 < 3 < 8\)) tạo thành dãy đẹp dài \(3\), và không có dãy đẹp nào dài hơn.

Cho xâu \(S\) gồm các chữ cái thường a đến z, độ dài \(L\). Hãy tìm xâu \(S'\) ngắn nhất sao cho khi viết nối liên tiếp nhiều lần xâu \(S'\) ta được một xâu dài vô hạn/đủ dài mà \(S\) là một xâu con liên tiếp của nó.

In ra độ dài của \(S'\).

Input

• Dòng đầu chứa số nguyên \(L\).
• Dòng thứ hai chứa xâu \(S\) có đúng \(L\) ký tự.

Output

In ra một số nguyên là độ dài ngắn nhất của \(S'\).

Constraints

• \(1 \le L \le 100\,000\)
• \(S\) chỉ gồm các chữ cái thường a..z.

Sample Input

8
abcabcab

Sample Output

3

Explanation

$S' = $ abc, lặp lại được abcabcabc... chứa abcabcab. Không có xâu nào ngắn hơn làm được.