Các nhà bác học tìm thấy một loại vi khuẩn mới khi lớp băng vĩnh cửu bị tan. Họ quyết định nhân giống để nghiên cứu. Đĩa chứa dung môi có hình chữ nhật và có thể coi là một lưới ô vuông kích thước vô hạn.

Ở thời điểm 1, vi khuẩn được cấy vào một ô. Cứ sau một đơn vị thời gian, vi khuẩn lại phát triển sang các ô bên cạnh:

• Ở thời điểm chẵn, vi khuẩn lan từ ô đã có sang ô kề cạnh và kề đỉnh chưa có vi khuẩn.
• Ở thời điểm lẻ, vi khuẩn lan sang ô kề cạnh chưa có vi khuẩn.

Hãy xác định số ô có vi khuẩn sau k đơn vị thời gian.

Ảnh minh họa

Dữ liệu

Vào từ thiết bị vào chuẩn gồm một dòng chứa số nguyên: 1 ≤ k ≤ ~10^8~

Kết quả

Đưa ra thiết bị ra chuẩn một số nguyên – số ô có vi khuẩn.

Ví dụ

INPUT

5

OUTPUT

69

Bob, bạn của Alice, đang nghiên cứu các vấn đề về lý thuyết số và thường hay nhờ Alice lập trình tìm các dãy số thỏa mãn một số tính chất nào đó.

Hôm nay, Bob nhờ tìm cặp số nguyên trong đoạn [lf, rt] có ƯSC lớn nhất trong số các cặp (x, y) thỏa mãn điều kiện:

• lf ≤ x, y ≤ rt

Đây không phải là một vấn đề khó và Alice đã nhanh chóng giải quyết.

Hãy xác định cặp số Alice đã đưa ra với lf và rt cho trước.

Dữ liệu vào

Dữ liệu vào từ thiết bị vào chuẩn: gồm 1 dòng chứa 2 số nguyên: lf, rf (1 ≤ lf < rf ≤ ~10^{18}~, |lf - rf| ≤ ~10^6~)

Kết quả

Đưa ra thiết bị ra chuẩn trên 1 dòng 2 số nguyên tìm được.

Ví dụ

INPUT

4 13

OUTPUT

6 12

Quân xe trên bàn cờ có thể đi dọc theo cột hoặc đi ngang theo hàng tới vị trí mới bất kỳ nếu các ô trên đoạn đường đi đều trống. Nếu trên hàng hay cột có quân cờ, xe có thể tới ăn. Xét bàn cờ kích thước n*m. Hãy xác định cách bố trí k quân xe một cách an toàn, nghĩa là không có quân nào có thể bị quân khác ăn.

Dữ liệu vào

Vào từ thiết bị vào chuẩn gồm một dòng chứa 3 số nguyên n, m và k (1 ≤ n, m, k ≤ 100).

Kết quả

Đưa ra thiết bị ra chuẩn thông báo Possible trên dòng thứ nhất và các dòng sau xác định một bản đồ bố trí xe gồm n dòng, mỗi dòng là một xâu m ký tự, các ô trống thể hiện bằng ký tự '.', ô có quân xe – ký tự '.'. Nếu không có cách bố trí an toàn – đưa ra thông báo Impossible.

Ví dụ

INPUT

3 5 2

OUTPUT

Possible
.*...
.....
*....

Trong cuộc sống, bên cạnh những định luật nghiêm túc như các định luật I, II và III của Newton còn có những định luật vui nhưng phản ánh khá chân thật bức tranh của cuộc sống. Một trong số đó là định luật Morgan: "Một đinh ốc bị rơi bao giờ cũng lăn vào chổ có thể gây tác hại lớn nhất!". Hôm nay An được trải nghiệm hiệu ứng của định luật này. Cô phải gửi gấp báo cáo của mình lên Hội đồng khoa học trước khi ra sân bay đi dự hội nghị. Để làm được việc đó cần tải báo cáo lên Googe.com/Drive. Googe Drive của An đang ở trạng thái rỗng. Việc đầu tiên là tải báo cáo lên đó. Nhưng khi copy, phím chuột trái bị dính. Khi An nhận ra điều này và ấn được phím gỡ trạng thái dính thì trong Drive đã có n bản sao! Vấn đề bây giờ là phải xóa hết các bản sao thừa, chỉ để lại một. Việc xóa một file đã tải lên mạng không đơn giản như xóa file trong máy, đặc biệt khi yêu cầu đã được tiếp nhận, nhưng file chưa được tải hoặc đang tải. Nhưng vận may đã không bỏ rơi An. Chắc ai đó cũng gặp trường hợp dính phím như cô và đã xây dựng một chương trình xóa files, rút số files trong thư mục xuống k lần, có điều chương trình hoạt động khi và chỉ khi số files trong thư mục chia hết cho k. Để trực tiếp xóa một file trên drive cần a giây, còn một lần chạy chương trình đã nêu – cần b giây. Hãy xác định khoảng thời gian nhỏ nhất cần thiết để giữ lại trên drive đúng một file.  

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 2×~10^9~)
• Dòng thứ 2 chứa số nguyên k (1 ≤ k ≤ 2×~10^9~)
• Dòng thứ 3 chứa số nguyên a (1 ≤ a ≤ 2×~10^9~)
• Dòng thứ 4 chứa số nguyên b (1 ≤ b ≤ 2×~10^9~)

Kết quả

Đưa ra thiết bị ra chuẩn một số nguyên – khoảng thời gian nhỏ nhất tìm được.

Ví dụ

INPUT

19
3
4
2

OUTPUT

12