Hiếu và Ân đang muốn đi du lịch cùng nhau trước khi kết hôn và cũng muốn đi du lịch về sớm để tổ chức tiệc cưới. Sau khi đi du lịch phải về gặp mặt gia đình \(2\) bên. Nhà Ân nằm ở tọa độ \(1\). Nhà Hiếu nằm ở tọa độ \(L\). Họ có một danh sách \(N\) địa điểm du lịch khác nhau, địa điểm du lịch thứ i có tọa độ là \(x_i\). Quãng đường từ địa điểm có tọa độ \(A\) đến địa điểm có tọa độ \(B\) là \(|A - B|\). Vì để tiết kiệm thời gian họ đang tìm địa điểm để đến du lịch sao cho quãng đường từ đó đi đến nhà Hiếu hoặc nhà Ân, sau đó đi đến nhà còn lại là nhỏ nhất. Việc đó rất khó khăn với họ. Là một người tốt bụng các bạn hãy giúp họ tìm địa điểm du lịch sao cho từ đó đi đến gia đình \(2\) bên là ngắn nhất.

Input

• Dòng đầu tiên chứa \(2\) số nguyên dương lần lượt là \(N\), \(L\). (\(1 \leq N \leq 10^5\),\(2 \leq L \leq 10^9\));
• Dòng thứ hai chứa \(N\) số nguyên \(x_i\) (\(1 < x_i < L\)).

Output

• Chỉ gồm duy nhất \(1\) dòng: Chứa các số nguyên dương tăng dần là những địa điểm thõa mãn yêu cầu trên, mỗi số cách nhau \(1\) dấu cách.

Example

5 10
9 3 7 4 2

1 5

Shiba là một thanh niên đam mê tin học. Anh ta luôn tìm kiếm những thử thách mới để rèn luyện khả năng tính toán và tư duy logic của mình ~chủ yếu là để train đấm VOI~. Vào một ngày đẹp trời, khi đang tự học tại nhà, Shiba tình cờ đọc được một bài toán về các số nguyên tố và nhận ra rằng đó là một thử thách thú vị để giải quyết.

Bài toán yêu cầu Shiba đếm số lượng "số siêu đẹp" không lớn hơn một giá trị \(N\) cho trước. Một số nguyên dương \(K\) là "Số siêu đẹp" khi nó có dạng \(K = p \times q^3\) với \(p\) và \(q\) là hai số nguyên tố và \(p < q\). Shiba cảm thấy thích thú với bài toán này và quyết định bắt tay vào giải quyết nó.

Tuy nhiên sau bao lần nộp thì anh ấy vẫn không thể hoàn thành được bài này.

Biết rằng số nguyên tố là số nguyên dương chỉ chia hết cho \(1\) và chính nó, số nguyên tố đầu tiên là \(2\).

Yêu Cầu: Shiba cảm thấy bài trên quá khó, nên các bạn hãy giúp Shiba hoàn thành bài trên ~Để Shiba có động lực train để đấm VOI tiếp~.

Input

• Chứa một số nguyên dương \(N\) duy nhất (\(1 \le N \le 10^{18})\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(1 \le N \le 5000\).
• Subtask \(2\) (\(30\%\) số điểm): Có \(5000< N \le 10^9\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

250

2

shiba là một nhân viên IT làm công ăn lương. Vì ChatGPT bùng nổ, công ty hiện shiba đang làm cắt giảm nhân sự đi, trong đó có shiba. Tuy mất việc làm nhưng để tiếp tục kiếm thêm thu nhập nuôi gia đình, shiba đã phải đi làm phụ hồ.

Ngày đầu ở cơ sở làm việc, Thầy _minhduc, một thợ chính có tiếng trong vùng, giao cho shiba một nhiệm vụ đơn giản như sau: “Đường viền trang trí ở nền nhà có kích thước \(2 \times N\) được lát bằng 2 loại gạch: loại kích thước \(1×2\) và loại \(2×2\). Hãy xác định số cách lát khác nhau có thể thực hiện. Lưu ý là với loại \(1×2\), ta có thể xoay nó để trở thành \(2×1\)”.

Thầy _minhduc muốn shiba hoàn thành nhiệm vụ trước \(14h\) ngày \(9/4\) để thầy còn tham dự contest ôn tin học trẻ bảng B của LQDOJ. Nhiệm vụ ừ thì dễ đấy, nhưng shiba chưa có kinh nghiệm bôi vôi trát vữa bao giờ. shiba liền tìm đến bạn, người anh em chí cốt của mình, để xin sự giúp đỡ. Hãy giúp shiba hoàn thành công việc đúng deadline để còn train VOI nữa chứ :Đ.

Yêu cầu: Hãy xác định số cách lát gạch có thể thực hiện, in ra kết quả sau khi chia lấy dư cho \({10}^9+7\).

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) – số bộ dữ liệu \((1 \le T\le10)\).
• T dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(N\) \((1 \le N \le {10}^{18})\), là chiều dài của nền nhà cần lát gạch vô.

Output

• In ra số cách lát gạch sau khi chia lấy dư cho \({10}^9+7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 10\).
• Subtask \(2\) (\(40\%\) số điểm): Có \(N \le 10^6\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
2
8
12

3
171
2731