Bài tập

Bạn được cung cấp \(N\) đoạn dây, với \(1 \le N \le 10^5\). Đoạn dây thứ \(i\) có độ dài \(a_i\), với \(0 < a_i \le 10^9\).

Cần cắt các đoạn dây này thành \(K\) đoạn có độ dài bằng nhau, với \(K\) là một số nguyên dương. Các đoạn dây ban đầu có thể không cần được sử dụng hết. Phần thừa từ các đoạn dây bị cắt có thể bỏ đi.

Hãy xác định độ dài lớn nhất của đoạn dây mà bạn có thể thu được sau khi cắt, sao cho có thể tạo ra ít nhất \(K\) đoạn như vậy. Nếu không có cách nào để cắt được \(K\) đoạn có độ dài nguyên dương, hãy in ra \(0\).

Input

Dữ liệu vào được cung cấp từ bàn phím theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(K\) (\(N \le 10^5, K \le 10^{14}\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(a_i\), là độ dài của đoạn dây thứ \(i\).

Output

In ra một dòng duy nhất chứa độ dài lớn nhất của đoạn dây có thể nhận được.

Example

4 11
802
743
547
539

200

Một công ty đồ chơi nhập khẩu \(n\) con búp bê gỗ, được đánh số từ \(1\) đến \(n\). Mỗi con búp bê thứ \(i\) có kích thước là một số nguyên dương \(a_i\). Một con búp bê thứ \(i\) có thể được lồng vào bên trong một con búp bê thứ \(j\) nếu con búp bê thứ \(j\) đang rỗng và kích thước của chúng thỏa mãn điều kiện \(a_i + k \le a_j\), trong đó \(k\) là một hằng số nguyên dương cho trước.

Khi các con búp bê được lồng vào nhau, công ty chỉ cần tìm chỗ đặt cho những con búp bê ngoài cùng (những con không được lồng vào bất kỳ con búp bê nào khác).

Yêu cầu:
Hãy tìm cách lồng các con búp bê vào nhau sao cho tổng kích thước của tất cả các con búp bê ngoài cùng là nhỏ nhất.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn (stdin) theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) (\(n \le 10^5\), \(k \le 10^9\)), cách nhau bởi một dấu cách.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10^9\)), cách nhau bởi một dấu cách.

Output

In ra một số nguyên duy nhất là tổng kích thước nhỏ nhất của các con búp bê ngoài cùng.

Example

8 2
8 4 2 1 1 3 5 9

18

Scoring

\begin itemize

• Có 30% số điểm ứng với \(n \le 10\).
• 70% số điểm còn lại không có ràng buộc gì thêm.
  \end itemize

Bình và An đang ôn thi vào trường THPT chuyên. Bình định nghĩa "số đẹp" là số không có chữ số 0 ở tận cùng. Cho hai số nguyên dương \(a, b\) (\(a < b\)), đặt \(S = a \times (a+1) \times \cdots \times b\). Hãy đếm số chữ số 0 tận cùng của \(S\) cần xóa để \(S\) trở thành số đẹp.

Input

Tệp SODEP.INP gồm:

• Dòng 1: Số nguyên \(T\) (\(1 \leq T \leq 10^5\)) - số lượng test cases
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số \(a, b\) (\(a < b \leq 10^{16}\))

Output

Tệp SODEP.OUT gồm \(T\) dòng, mỗi dòng là số chữ số 0 tận cùng của \(S\) tương ứng, lấy modulo \(10^9 + 7\).

Example

4
1 6
1 10
2 4
10 20

1
2
0
3

Scoring

• 40% test: \(T \leq 10\), \(b \leq 18\)
• 30% test: \(T = 1\), \(b \leq 10^5\)
• 20% test: \(T \leq 10^4\), \(b \leq 10^5\)
• 10% test: \(T \leq 10^5\), \(b \leq 10^{16}\)

Một số nguyên dương được gọi là số "đặc biệt" nếu số đó có đúng 3 ước nguyên dương đồng thời khác nhau.

**Yêu cầu:** Cho $M$ cặp số nguyên dương $(a; b)$, hãy đếm số lượng số "đặc biệt" $x$ thoả mãn $a \leq x \leq b$.

Yêu cầu: Cho \(M\) cặp số nguyên dương \((a; b)\), hãy đếm số lượng số "đặc biệt" \(x\) thoả mãn \(a \leq x \leq b\).

Input

Từ file SNUM.INP gồm:

• Dòng đầu là số nguyên dương \(M\) (\(1 \leq M \leq 10^5\));
• \(M\) dòng tiếp theo mỗi dòng chứa hai số nguyên dương \(a, b\) cách nhau bởi một khoảng trắng (\(1 \leq a \leq b \leq 10^6\)).

Output

Ghi ra file SNUM.OUT gồm \(M\) dòng, mỗi dòng là kết quả tương ứng tìm được.

Example

2
1 10
1 100

2
4

Scoring

• Có \(20\%\) số điểm ứng với (\(1 \leq M \leq 10^2; 1 \leq b \leq 10^2\));
• Có \(30\%\) số điểm ứng với (\(1 \leq M \leq 10^3; 1 \leq b \leq 10^3\));
• \(50\%\) số điểm còn lại không có giới hạn gì thêm.