Bài tập

Số tự nhiên \(m\) được gọi là ước nguyên tố của số nguyên dương \(n\) nếu \(n\) chia hết cho \(m\) và \(m\) là số nguyên tố.

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn gồm ba số nguyên \(a,b,k\). Với mỗi truy vấn, hãy xác định số lượng các số nguyên \(x\) thỏa mãn: \(a \le x \le b\) và có số lượng ước nguyên tố không nhỏ hơn \(k\).

Input

Vào từ tệp văn bản BAI2.INP có cấu trúc:

• Dòng thứ nhất chứa số nguyên dương \(Q\) là số lượng truy vấn \((1 \le Q \le 10^5)\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a,b,k\) \((1 \le a \le b \le 10^6; 0 \le k \le 7)\).

Output

Ghi ra tệp văn bản BAI2.OUT gồm \(Q\) dòng, mỗi dòng ghi một số nguyên duy nhất là kết quả tương ứng với mỗi truy vấn.

Example

1
25 30 2

3

Scoring

• Có \(60\%\) số test ứng với \(60\%\) số điểm của bài thỏa mãn: \(Q = 1\); \(1 \le a \le b \le 10^3\).
• Có \(20\%\) số test khác ứng với \(20\%\) số điểm của bài thỏa mãn: \(Q = 1\); \(10^3 < a \le b \le 10^6\).
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.

Trong buổi sinh hoạt ngoại khóa, thầy giáo tổ chức một trò chơi nhỏ như sau: mỗi lần thầy viết lên bảng cặp số \(a\) và \(b\), thì các bạn nhanh chóng đếm xem có bao nhiêu số nguyên trong đoạn từ \(a\) đến \(b\) có số lượng các ước của nó là một số nguyên tố.

Ví dụ, với \(a=4\) và \(b=6\), đoạn \([4, 6]\) ta có:

• Số \(4\) có \(3\) ước \((1, 2, 4)\): \(3\) là số nguyên tố;
• Số \(5\) có \(2\) ước \((1, 5)\): \(2\) là số nguyên tố;
• Số \(6\) có \(4\) ước \((1, 2, 3, 6)\): \(4\) không phải là số nguyên tố.

Nên trong đoạn \([4, 6]\) ta đếm được \(2\) số có số lượng ước của nó là số nguyên tố (\(4\) và \(5\)).

Sau \(N\) lần đưa ra các cặp số \(a\) và \(b\), thầy giáo yêu cầu đưa ra kết quả cuối cùng chính là tổng số của \(N\) lần đếm trên.

Yêu cầu: Là một học sinh đam mê lập trình trong lớp, em hãy viết một chương trình để tự động thực hiện yêu cầu của thầy giáo.

Input

Dữ liệu vào: Cho tệp văn bản CAU3.INP có cấu trúc như sau:

• Dòng 1: chứa số nguyên \(N\) là số lượng các cặp \([a, b]\) cần đếm (\(0 \leq N \leq 10^5\));
• \(N\) dòng tiếp theo: mỗi dòng chứa một cặp số nguyên \(a\) và \(b\) (\(1 \leq a \leq b \leq 10^6\)).

Các số được ghi cách nhau bởi một dấu cách.

Output

Kết quả: Ghi ra tệp văn bản CAU3.OUT gồm một dòng ghi số nguyên là tổng \(N\) lần đếm trên.

Example

2
4 6
4 7

5

Scoring

Ràng buộc:

• Có \(40\%\) số test tương ứng \(40\%\) số điểm của bài với \(1 \leq a \leq b \leq 200\) và \(N \leq 200\);
• Có \(30\%\) số test tương ứng \(30\%\) số điểm của bài với \(1 \leq a \leq b \leq 2000\) và \(N \leq 1000\);
• Có \(30\%\) số test tương ứng \(30\%\) số điểm của bài với \(1 \leq a \leq b \leq 10^6\) và \(N \leq 10^5\).

Bạn được cung cấp một đồ thị vô hướng liên thông gồm \(N\) đỉnh và \(M\) cạnh. Hãy tìm cây khung nhỏ thứ nhì của đồ thị.

Cây khung nhỏ thứ nhì là cây khung có tổng trọng số nhỏ nhất kế tiếp so với cây khung nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N, M\) \((1 \leq N \leq 10^5, 1 \leq M \leq 10^5)\) --- số lượng đỉnh và cạnh của đồ thị.
• \(M\) dòng tiếp theo mô tả danh sách các cạnh của đồ thị. Mỗi dòng chứa ba số nguyên \(u_i, v_i, w_i\) \((1 \leq u_i, v_i \leq N, 1 \leq w_i \leq 10^9)\), biểu thị một cạnh giữa hai đỉnh \(u_i\) và \(v_i\) với trọng số \(w_i\).

Output

Một số nguyên duy nhất là giá trị của cây khung nhỏ thứ nhì. Nếu không tồn tại, in ra -1.

Example

3 3
1 2 1
3 1 1
3 2 1

2

3 3
1 2 3
3 1 1
3 2 2

4

Scoring

• (\(50\%\) số điểm) \(1 \leq N \leq 500\), \(1 \leq M \leq 10^3\)
• (\(50\%\) số điểm) \(1 \leq N, M \leq 10^5\)

Trong một thiên hà rộng lớn, có \(N\) hành tinh nằm thẳng hàng trong một khu vực. Mỗi hành tinh có một lượng tài nguyên nhất định. Một nhóm phi hành gia được giao nhiệm vụ đến thăm đúng \(K\) hành tinh để thu thập càng nhiều tài nguyên càng tốt.

Tuy nhiên, do hạn chế về năng lượng, họ chỉ được phép ghé thăm đúng \(K\) hành tinh trong số \(N\) hành tinh có sẵn. Mỗi hành tinh thứ \(i\) có một giá trị tài nguyên là \(a_i\), giá trị này có thể dương (tài nguyên quý giá) hoặc âm (chứa chất thải nguy hiểm).

Nhiệm vụ của bạn là giúp các phi hành gia chọn ra \(K\) hành tinh sao cho tổng tài nguyên thu được là lớn nhất.

Input

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \leq K \leq N \leq 10^5\)) --- số hành tinh và số hành tinh mà nhóm phi hành gia có thể thăm.

Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) (\(-10^5 \leq a_i \leq 10^5\)) --- lượng tài nguyên trên mỗi hành tinh.

Output

In ra một số nguyên duy nhất --- tổng lượng tài nguyên lớn nhất mà phi hành gia có thể thu được khi ghé thăm đúng \(K\) hành tinh.

Example

4 2
2 4 6 8

14

4 4
5 5 5 5

20

Scoring

• \(10\%\) số test tương ứng với \(10\%\) số điểm có \(N = 1\).
• \(10\%\) số test tương ứng với \(10\%\) số điểm có \(N = 2\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(N \leq 20\).
• \(40\%\) số test tương ứng với \(40\%\) số điểm có \(N \leq 1000\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(N \leq 10^5\).