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~

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.

Vào năm ~3202~, trò chơi "Fake Pyramid" đang vô cùng thịnh hành với giới trẻ.

Trong trò chơi này, bạn được nhận một mảnh giấy kẻ ~n~ dòng và ~m~ cột, tạo ra ~n \times m~ ô vuông. Ô ở hàng ~i~ và cột ~j~ được gọi là ô ~(i,j)~. Mỗi ô ~(i,j)~ đều có một giá trị là ~a_{i,j}~, nếu ~a_{i,j} = 0~ thì nghĩa là ô đó đã bị "cấm", ngược lại, ~a_{i,j}~ sẽ mang một giá trị nguyên dương.

Bạn cần tìm cách vẽ ra một kim tự tháp trên mảnh giấy được cho theo luật như sau (do vẽ trên giấy nên có thể sẽ khác so với tưởng tượng):

• Đầu tiên, bạn chọn ra hai giá trị ~A,B~ thỏa mãn ~1 \le A \le B \le n~.
• Với mỗi ~i~ thuộc đoạn ~[A,B]~, bạn chọn ra hai giá trị ~L_i,R_i~ thỏa mãn ~1 \le L_i \le R_i \le m~. Bạn cần chọn các giá trị ~L_i,R_i~ này sao cho với mọi ~i \in [A,B-1]~, ~L_i \ge L_{i+1}~ và ~R_i \le R_{i+1}~
• Sau khi chọn xong các giá trị, bạn sẽ thu được một kim tự tháp được tạo bởi các ô ~(i,j)~ thỏa mãn ~i \in [A,B]~ và ~j \in [L_i,R_i]~.
• Nói cách khác, với mỗi hàng từ ~A~ tới ~B~, bạn sẽ cần chọn ra một số ô liên tiếp sao cho các ô ở hàng dưới trùm lên các ô ở hàng trên.
• Để tăng độ khó cho trò chơi, kim tự tháp của bạn vẽ ra không được chứa ô nào bị cấm.
• Giá trị của một kim tự tháp chính là tổng giá trị các ô nó chứa.

Ví dụ, cho mảnh giấy ~5 \times 5~ có minh họa như sau:

Ta chọn:

• ~A = 1; B = 3~.
• ~L_1 = 1; R_1 = 1~.
• ~L_2 = 1; R_2 = 3~.
• ~L_3 = 1; R_3 = 3~.

Sẽ thu được kim tự tháp thỏa mãn ở dưới (những ô màu cam là những ô nằm trong kim tự tháp):

Dưới đây cũng là một kim tự tháp thỏa mãn:

Tuy nhiên, hình ảnh dưới đây lại không phải một kim tự tháp thỏa mãn do chứa ô có giá trị ~a(i,j) = 0~ (ô bị cấm):

Cuối cùng, ta có minh họa dưới đây cũng không phải một kim tự tháp do ~L_4 < L_5~

MoHuymed Salah rất hứng thú với trò chơi này, nhưng do anh đang bận rộn với định lý một mùa dài ~7~ năm của mình nên dù đã có một mảnh giấy nhưng chưa có thời gian để tìm ra lời giải tối ưu nhất. Bạn hãy giúp anh ấy nhé.

Yêu cầu: Cho ma trận ~n \times m~ miêu tả mảnh giấy, hãy tìm cách vẽ kim tự tháp sao cho thu được tổng lớn nhất có thể.

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

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n,m \le 2000)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~m~ số nguyên dương ~a_{i,1}, a_{i,2}, ..., a_{i,m}~ miêu tả mảng giá trị ~a~ ~(a_{i,j} \le 50)~.
• Dữ liệu đảm bảo luôn luôn tồn tại ít nhất một giá trị ~a(i,j) \neq 0~.

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

• In ra một số nguyên là giá trị lớn nhất có thể đạt được của một kim tự tháp.

Ràng buộc

• Có ~15\%~ số test thỏa mãn: ~n = 1~.
• Có ~20\%~ số test thỏa mãn: Nếu hàng ~i~ ~(1 \le i \le n)~ có ô bị cấm, thì tất cả các ô trong hàng đó cũng đều bị cấm.
• Có ~20\%~ số test thỏa mãn: ~n,m \le 60~.
• Có ~25\%~ số test thỏa mãn: ~n,m \le 300~.
• ~20\%~ số test còn lại không có ràng buộc gì thêm.

Ví dụ

Input 1

5 5
5 0 1 4 4
7 12 6 5 4
5 7 8 0 1
1 6 4 5 0
1 0 7 5 8

Output 1

66

Input 2

5 3
1 1 2
0 0 0
1 2 3
2 3 4
0 0 0

Output 2

15

Giải thích

Ở ví dụ ~1~, ta lấy kim tự tháp theo hình dưới đây:

Còn đây là kim tự tháp ta cần lấy ở ví dụ ~2~:

Cho một đồ thị liên thông vô hướng gồm ~n~ đỉnh, ~n - 1~ cạnh (đây còn được gọi là đồ thị dạng cây). Cạnh thứ ~i~ nối giữa đỉnh ~u_i~ với ~v_i~ và có trọng số là ~w_i~. Quân đưa cho bạn ~m~ tập đỉnh, tập thứ ~i~ gồm ~t_i~ đỉnh là ~a_{i_1}, a_{i_2}, . . . , a_{i_{t_i}}~.

Giả sử ta có hai tập đỉnh ~p~ và ~q~ (một tập không có hai đỉnh giống nhau, nhưng một đỉnh có thể xuất hiện ở cả hai tập).

Đặt ~f(p,q)~ là tổng khoảng cách giữa các cặp đỉnh ~(u, v)~ trong đó ~u~ nằm trong tập ~p~ và ~v~ nằm trong tập ~q~ (khoảng cách giữa hai đỉnh là tổng trọng số các cạnh trên đường đi giữa chúng).

Cụ thể, nếu gọi ~dist(u,v)~ là khoảng cách giữa cặp đỉnh ~(u,v)~ trên cây, ta có tập ~p~ ~=~ ~ \{2,3\}~ và tập ~q~ ~=~ ~\{1,4,3\}~, thì ~f(p,q)~ sẽ được tính như sau:

• ~f(p,q) = dist(2,1) + dist(2,4) + dist(2,3) + dist (3,1) + dist(3,4) + dist(3,3)~.

Quân muốn bạn tính giá trị của biểu thức sau: ~S = \sum_{i=1}^m \sum_{j=i+1}^m f(i,j)~.

Vì kết quả có thể rất lớn, hãy in ra phần dư của ~S~ khi chia cho ~10^9 + 7~.

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

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n,m \le 10^6)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~u_i,v_i,w_i~ ~(1 \le u_i,v_i \le n; u_i \neq v_i; w_i \le 10^5)~.
• Ở mỗi dòng trong ~m~ dòng cuối cùng, số đầu tiên là ~t_i~, theo sau đó là ~t_i~ số ~a_{i_1},a_{i_2},...,a_{t_i}~ ~(1 \le a_x \le n; a_x \neq a_y \forall x \neq y)~.

Tổng ~t_1 + t_2 + ... + t_m~ không vượt quá ~10^6~.

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

• In ra một số nguyên không âm là kết quả bài toán.

Ràng buộc

• Có ~25\%~ số test thỏa mãn: ~n \le 100; m \le 100; t_1 + t_2 + ... + t_m \le 100~.
• Có ~25\%~ số test thỏa mãn: ~n \le 100; m \le 100; t_1 + t_2 + ... + t_m \le 10^5~.
• Có ~20\%~ số test thỏa mãn: ~n \le 10^5; m \le 100; t_1 + t_2 + ... + t_m \le 10^5~.
• Có ~20\%~ số test thỏa mãn: ~n, m, t_1 + t_2 + ... + t_m \le 10^5~.
• ~10\%~ số test còn lại không có ràng buộc gì thêm.

Ví dụ

Input

3 3
1 2 1
2 3 1
1 1
1 2
2 1 3

Output

5

Giải thích

~f(1,2) = dist(1,2) = 1~ ~f(1,3) = dist(1,1) + dist(1,3) = 0 + 2 =2~ ~f(2,3) = dist(2,1) + dist(2,3) = 1 + 1 = 2~

Vậy ~S = 1 + 2 + 2 = 5~