Bài tập

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.

Trên mặt phẳng có \(N\) điểm được liệt kê theo một thứ tự cố định, điểm thứ \(i\) có toạ độ nguyên \((a_i, b_i)\). Ta muốn chọn ra một số điểm, giữ nguyên thứ tự xuất hiện của chúng, sao cho khi đi từ điểm chọn này sang điểm chọn kế tiếp thì cả hoành độ lẫn tung độ đều không giảm.

Nói cách khác, cần tìm dãy chỉ số \(i_1 < i_2 < \dots < i_k\) sao cho với mọi \(t\) ta có \(a_{i_t} \le a_{i_{t+1}}\) và \(b_{i_t} \le b_{i_{t+1}}\). Hãy tìm giá trị \(k\) lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\).

Output

In ra một số nguyên duy nhất là độ dài lớn nhất \(k\) của dãy điểm chọn được.

Constraints

• \(1 \le N \le 10^5\)
• \(0 \le a_i, b_i \le 10^9\)

Sample Input

7
40 400
20 600
50 400
50 700
10 900
80 800
50 700

Sample Output

4

Explanation

Chọn các điểm thứ 1, 3, 4, 6: \((40,400) \to (50,400) \to (50,700) \to (80,800)\). Không tồn tại dãy dài hơn.

An trực nhật cứ \(a\) ngày một lần, Bách trực nhật cứ \(b\) ngày một lần. Hôm nay (ngày \(0\)) cả hai cùng trực. Hỏi sau ít nhất bao nhiêu ngày thì hai bạn lại trực cùng một ngày? Tính đến ngày đó (kể cả ngày đó, không tính ngày \(0\)), mỗi bạn đã trực bao nhiêu lần?

Input

Hai số nguyên \(a\) và \(b\) (có thể nằm trên cùng một dòng hoặc hai dòng).

Output

In ra ba dòng:

• Dòng 1: số ngày \(D\) nhỏ nhất (là bội chung nhỏ nhất của \(a\) và \(b\)).
• Dòng 2: An: theo sau là số lần An trực, tức \(D / a\).
• Dòng 3: Bach: theo sau là số lần Bách trực, tức \(D / b\).

Constraints

• \(1 \le a, b \le 2000\)

Sample Input

4 6

Sample Output

12
An: 3
Bach: 2

Explanation

Sau \(12\) ngày hai bạn gặp nhau: An trực vào các ngày \(4, 8, 12\) (\(3\) lần), Bách trực vào các ngày \(6, 12\) (\(2\) lần).

Bến xe có \(N\) chiếc xe buýt. Mỗi ngày, xe thứ \(i\) tiêu thụ \(a_i\) đơn vị nhiên liệu. Ban điều hành cần chọn đúng \(K\) chiếc xe để chạy trong ngày và muốn tổng nhiên liệu tiêu thụ là bé nhất.

Hãy tính tổng lượng nhiên liệu nhỏ nhất có thể.

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(K\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\).

Output

In ra một số nguyên: tổng nhiên liệu nhỏ nhất của \(K\) xe được chọn.

Constraints

• \(1 \le K \le N \le 300\,000\).
• \(1 \le a_i \le 10^9\).

Sample Input

6 4
7 2 9 4 4 1

Sample Output

11

Explanation

Chọn các xe tiêu thụ \(1, 2, 4, 4\): tổng là \(11\).