Bài tập

Định nghĩa cây

Một cây là một đồ thị vô hướng liên thông không chứa chu trình. Tức là, cây là một đồ thị \(G = (V, E)\) thỏa mãn các điều kiện sau:

• \(G\) liên thông, tức là luôn có đường đi giữa hai đỉnh bất kỳ.
• \(G\) không chứa chu trình, tức là không có tập con của các cạnh tạo thành một đường khép kín.

Tính chất của cây

Một cây với \(n\) đỉnh (\(n \geq 1\)) có các tính chất sau:

• Cây có đúng \(n-1\) cạnh.
• Giữa hai đỉnh bất kỳ trong cây luôn tồn tại duy nhất một đường đi.
• Thêm một cạnh bất kỳ vào cây sẽ tạo thành đúng một chu trình.
• Loại bỏ một cạnh bất kỳ khỏi cây sẽ làm đồ thị không còn liên thông.

Ứng dụng của cây

Cây có nhiều ứng dụng quan trọng trong tin học và toán học:

• Cấu trúc dữ liệu: Cây nhị phân tìm kiếm, cây AVL, cây đỏ-đen.
• Mạng máy tính: Mô hình phân cấp mạng.
• Hệ thống tệp: Cấu trúc thư mục trong hệ điều hành.
• Nén dữ liệu: Cây Huffman.

Bài toán

Cho đồ thị có dạng một cây có \(n\) đỉnh có gốc của cây là đỉnh \(1\). Hãy trả lời các câu hỏi sau :

• Câu hỏi \(1\) : Với mỗi \(x\) từ \(1\) đến \(n\), hãy in ra cha của \(x\) trên cây. Nếu \(x\) là gốc của cây thì in ra chính nó.
• Câu hỏi \(2\) : Tìm khoảng cách từ gốc của cây đến tất cả các đỉnh trên cây.
• Câu hỏi \(3\) : In ra tất cả các đỉnh lá của cây (theo thứ tự tăng dần chỉ số).
• Câu hỏi \(4\) : Với mỗi \(x\) từ \(1\) đến \(n\), hãy in ra số lượng đỉnh trong cây con gốc \(x\).

Input

Dòng đầu tiên là hai số nguyên dương \(n\) và \(t\). \(n\) là số đỉnh của cây và \(t\) là chỉ số câu hỏi. \((1 \leq n \leq 500, 1 \leq t \leq 4)\).

\(n - 1\) dòng tiếp theo, mỗi dòng là hai số nguyên dương \(u\) và \(v\), là cạnh của cây.

Output

Với câu hỏi in ra tương ứng, xem test ví dụ để hiểu rõ hơn.

Example

5 1
1 2
1 3
2 4
2 5

1 1 1 2 2 

5 2
1 2
1 3
2 4
2 5

0 1 1 2 2 

5 3
1 2
1 3
2 4
2 5

3 4 5 

5 4
1 2
1 3
2 4
2 5

5 3 1 1 1 

Số nguyên tố mạnh là số nguyên tố lớn hơn trung bình cộng của số nguyên tố liền trước và số nguyên tố liền sau nó.

Cho hai số nguyên dương \(L\) và \(R\) \((L < R)\). Hãy cho biến tổng của số nguyên tố mạnh lớn nhất và nhỏ nhất có trong đoạn \(L\) đến \(R\).

Em hãy viết chương trình thực hiện yêu cầu trên. Nếu không có thì in ra -1.

Input

Dữ liệu vào: Từ tệp NGUYENTOMANH.INP chứa hai số nguyên dương \(L\) và \(R\).

Output

Dữ liệu ra: Ghi vào tệp NGUYENTOMANH.OUT một số nguyên duy nhất là kết quả thực hiện yêu cầu bài toán trên.

Example

2 20

28

2 10

-1

Scoring

• Có \(50\%\) số test ứng với \(50\%\) số điểm của bài có \(1 < R \le 10^{6}\).
• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài có \(10^{3} < R \le 10^{9}\).
• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài có \(10^{9} < R \le 10^{16}\).

Cho \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\). Hãy xác định xem có bao nhiêu số nguyên \(x\) trong đoạn \([l, r]\) mà \(x\) không chia hết cho bất kỳ số \(a_i\) nào.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(n, l, r\) (\(1 \le n \le 18\), \(1 \le l \le r \le 10^{18}\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).

Output

• In ra một số nguyên duy nhất là đáp án của bài toán.

Example

3 10 20
3 4 5

5

Scoring

• Subtask 1 (30% số điểm): \(1 \le l \le r \le 10^6\).
• Subtask 2 (70% số điểm): \(1 \le l \le r \le 10^{18}\).