Cho biểu thức như sau:

Hãy điền phép tính +, -, * vào ? để được biểu thức đúng.

Dữ liệu vào từ tệp văn bản: dienpheptinh.inp

• Dòng đầu tiên chứa số nguyên dương ~A~.
• Dòng đầu tiên chứa số nguyên dương ~B~.
• Dữ liệu đầu vào luôn đảm bảo có cách điền dấu phù hợp.

Kết quả ghi ra tệp văn bản: dienpheptinh.out

• In ra hai kí tự theo thứ tự là dấu của phép tính tương ứng. Có thể có nhiều cách điền, chỉ cần in ra cách điền đúng bất kì. Mỗi kí tự in trên một dòng (dòng đầu tiên là phép tính ở dấu hỏi đầu tiên, dòng thứ hai là phép tính ở dấu hỏi thứ hai).

Chú ý: dấu nhân là kí tự sao (*)

Ràng buộc

• Có ~60\%~ số test thỏa mãn: ~A, B \le 10^3~;
• Có ~20\%~ số test thỏa mãn: ~A, B \le 10^9~;
• Có ~20\%~ số test thỏa mãn: ~A, B \le 10^{18}~;

Ví dụ

Input

3
6

Output

*
-

Giải thích

~3*3-3=6~

Số chính phương đặc biệt là số chính phương được tạo bởi một số nguyên tố. Ví dụ ~4 = 2 \times 2; \ 9 = 3 \times 3; \ 36 = 6 \times 6~ nên ~4~ và ~9~ là số chính phương đặc biệt còn ~36~ thì không phải là số chính phương đặc biệt.

Yêu cầu: Cho ~2~ số nguyên dương ~a, b~. Hãy đếm xem trong đoạn ~[a..b]~ có bao nhiêu số chính phương đặc biệt?

Dữ liệu vào từ tệp văn bản CP.INP:

Gồm hai số nguyên dương ~a, b \ (2 \le a \le b \le 10^{12})~.

Kết quả ghi ra tệp văn bản CP.OUT:

Gồm một dòng chứa một số duy nhất là kết quả của bài toán.

Ràng buộc

• Có ~80\%~ số test ứng với ~80\%~ số điểm của bài thoả mãn ~2 \le 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.

Ví dụ

Input

2 10

Output

2

Châu và Huy là đôi bạn thân. Vì yêu âm nhạc nên họ gửi cho nhau lyrics của các bài hát. Cụ thể đó là những xâu ~S~ độ dài ~N~ và chỉ gồm các kí tự từ ~a~ đến ~z~. Để làm cho những xâu này trở nên hay hơn, Huy đã đưa cho Châu một số nguyên dương ~K~ và nhờ thực hiện những thao tác sau. (Lưu ý mỗi thao tác bắt buộc phải làm một lần duy nhất):

• Tạo ra xâu ~T~ từ xâu ~S~ đã cho bằng cách viết ~K~ lần liên tiếp xâu ~S~ liên kề nhau. (Ví dụ ~K = 2~ và xâu ~S~ là ~hello~ thì khi viết sẽ cho xâu ~T~ là ~hellohello~).
• Chọn một chữ cái ở vị trí bất kì trong xâu ~T~, giả sử là vị trí ~i~. Biến đổi tất cả các chữ cái trong xâu ~T~ giống với chữ cái ở vị trí ~i~ thành chữ cái ở vị trí ~i-1~ hoặc chữ cái ở vị trí ~i+1~ (Tất nhiên nếu ở vị trí đầu tiên sẽ không có ~i-1~ và vị trí cuối cùng sẽ không có ~i+1~ để mà biến). Gọi ~X~ là số lần xuất hiện của chữ cái xuất hiện nhiều nhất trong xâu vừa tạo. Phải đảm bảo thao tác biến đổi vừa rồi tạo ra ~X~ lớn nhất.

Yêu cầu:

• Cho xâu ~S~ độ dài ~N~ và số ~K~. Tạo ra xâu ~T~ mới bằng viết liền xâu ~S~ cạnh nhau ~K~ lần. Sau đó thực hiện thao tác như đã miêu tả trong đề sao cho số lần xuất hiện của chữ cái xuất hiện nhiều nhất là lớn nhất và cho biết số lần xuất hiện là bao nhiêu.

Dữ liệu vào từ tệp văn bản: amnhac.inp

• Dòng đầu tiên là 2 số nguyên dương ~N~ và ~K~. ~(N \le 10^6, K \le 10^9)~
• Dòng thứ hai là xâu ~S~ chỉ gồm các kí tự từ ~a~ đến ~z~.

Kết quả ghi ra tệp văn bản: amnhac.out

• In ra một số nguyên duy nhất là số lần xuất hiện của chữ cái xuất hiện nhiều nhất sau các thao tác đã nêu trong đề.

Ràng buộc:

• Có ~20\%~ số điểm với ~N * K \le 10^3~
• Có ~30\%~ số điểm với ~K = 1~.
• ~50\%~ số điểm còn lại không có ràng buộc gì thêm.

Ví dụ

Input 1

10 1
bbabdcccaa

Output 1

6

Input 2

3 2
abc

Output 2

4

Giải thích

Ở ví dụ ~1~, ta được xâu ~T~ là ~bbabdcccaa~. Sau đó biến tất cả kí tự ~a~ thành ~c~ vì ở vị trí thứ ~8~ kí tự ~c~ liền kề với kí tự ~a~ ở vị trí ~9~ và được xâu mới là ~bbcbdccccc~. Ta được 6 kí tự ~c~ trong xâu mới này nên kết quả in ra là 6.

Ở ví dụ ~2~, ta được xâu ~T~ là ~abcabc~. Sau đó biến tất cả kí tự ~a~ thành ~c~ vì ở vị trí thứ ~3~ kí tự ~a~ liền kề với kí tự ~c~ ở vị trí ~4~ và được xâu mới là ~cbccbc~. Ta được 4 kí tự ~c~ trong xâu mới này nên kết quả in ra là 4.

Marisa có ~n~ tấm gỗ và sẽ sửa lại chúng để sử dụng, tấm gỗ thứ ~i~ sẽ có độ đẹp là ~A_i~ hoặc ~B_i~ (tuỳ vào mục đích sử dụng mà Marisa sẽ sửa chúng khác nhau).

Marisa dự định chọn ra ~k~ tấm gỗ để làm hàng rào bao quanh nhà. Trong đó, cô sẽ chọn ra ~k-1~ tấm để dựng hàng rào và ~1~ tấm để làm cửa. Khi đó, những tấm để làm hàng rào sẽ có độ đẹp là ~A_i~ và tấm để làm cửa sẽ có độ đẹp là ~B_i~.

Marisa đang cân nhắc số lượng tấm gỗ sử dụng để làm hàng rào, nên cô sẽ hỏi bạn ~q~ câu hỏi, mỗi câu hỏi là một số nguyên ~k~, hãy giúp cô tính độ đẹp lớn nhất có thể khi sử dụng ~k~ tấm gỗ.

Dữ liệu vào từ tệp văn bản: xayhangrao.inp

• Dòng đầu tiên gồm hai số nguyên ~n,q~.
• Dòng thứ hai gồm ~n~ số nguyên ~A_i~.
• Dòng thứ ba gồm ~n~ số nguyên ~B_i~.
• Dòng thứ tư gồm ~q~ số nguyên ~k~ theo thứ tự, mô tả các truy vấn.

Kết quả ghi ra tệp văn bản: xayhangrao.out

• In ra ~q~ số nguyên, số nguyên thứ ~i~ là đáp án truy vấn thứ ~i~.

Ví dụ

Input 1:

3 1
3 5 4
5 8 5
3

Output 1:

15

Input 2:

3 2
3 5 4
5 8 5
3 2

Output 1:

15 12

Giới hạn: Trong mọi test: ~1 \le n,q \le 10^5, 1 \le A_i, B_i \le 10^9~.

• Subtask 1 (25% số điểm): Marisa chỉ hỏi bạn một câu hỏi duy nhất với ~k = n~.
• Subtask 2 (25% số điểm): ~1 \le n,q \le 10~.
• Subtask 3 (25% số điểm): ~1 \le n,q \le 1000~.
• Subtask 4 (25% số điểm): Không có giới hạn gì thêm.