Cpascal vẫn còn là một ẩn số. Chưa ai có thể giải đáp được anh ấy là ai và anh ấy có những năng lực gì. Đến cả người bạn thân nhất của anh ấy abcnickname vẫn chưa thể hiểu được hết tính cách và năng lực của anh ấy. Một hôm abcnickname có tìm được một mảnh giấy. Trong đó có ghi "giải và tận hưởng chúng" abcnickname mặc dù hoang mang nhưng anh ấy biết rõ đó là tờ giấy của Cpascal để lại. Nhiệm vụ của bạn là giải mã tờ giấy đó và chờ câu trả lời từ anh ấy

Yêu cầu: Cho ~q~ truy vấn. Đa giác ~n~ đỉnh, ~k~ màu, hãy đếm số cách tô màu các đỉnh sao cho ~k~ có 2 đỉnh kề nhau nào trùng màu

Dữ liệu vào

• Nhập truy vấn ~q~ (~1 ≤ q ≤ 100~)
• Mỗi truy vấn nhập một số nguyên ~n~ và ~k~ (~1 ≤ n,k ≤ 10^6~)

Dữ liệu ra

• Là số các tô màu các đỉnh sao cho k có 2 đỉnh kề nhau nào trùng màu. Bởi vì dữ liệu lớn nên chia hết cho ~10^9+7~

Ví dụ

Input: 01

3
10 2
2 10
5 5

Output: 01

2
90
1020

Sau khi abcnickname tìm được đáp án thì anh ấy lập tức nhập những con số đó vào một cỗ máy bí ẩn của Cpascal ở trong tầm hầm. Nó khiến cho abcnickname lập tức dịch chuyển sang một khu vực khác, nơi mà hình dạng ở đây đều là các hình tam giác đầy bí ẩn. Thậm chí còn có cả quả dừa tam giác nữa, abcnickname đã thám hiểm xung quanh đảo thì phát hiện ra được một tầng hầm. Trong đó là một cánh cửa nhìn bề ngoài rất là cũ kỹ. Ở giữa cánh cửa có khắc những dòng chữ ngỡ như là một luận văn dài 500 chữ. Mà trên ô cửa, số ô nhập chữ lại rất giới hạn vậy nên không thể nhét 1 đống chữ vào đó được

Dữ liệu vào

• Là một số nguyên ~n~ và ~q~ tượng trưng cho số ký tự có trên cánh cửa và số truy vấn(~1 ≤ n,q ≤ 10^5~)
• Là một dãy chữ số ~a[1],a[2],...,a[n]~(~1 ≤ a[i] ≤ 10^7~)
• Là một dãy chữ số ~b[1],b[2],...,b[q]~(~1 ≤ b[i] ≤ n~)

Dữ liệu ra

• Là mật mã của cánh cửa đó

Hướng dẫn hoạt động

• Cho một dãy ~a~ và một dãy ~b~
• Xóa một ký tự ở dãy ~a[i]~ ở vị trí ~b[i]~ cắt chúng thành 2 hai dãy khác nhau
• Tìm dãy có tổng lớn nhất rồi in ra

SUBTEST

• 50% số điểm (~1 ≤ n,q ≤ 10^3~)
• 50% số điểm (không rằng buộc gì thêm)

Ví dụ

Input: 01

6 2
7 10 2 0 0 7
2 6

Output: 01

9
7

abcnickname nhập những dòng code kỳ quái thì lập tức cỗ máy đó đã mở cánh cổng rất đặc biệt. Nhìn vẻ bề ngoài thì chúng rất là cũ kỹ và bám bụi. Nhưng càng đi sâu abcnickname càng phát hiện nhiều thứ rất kỳ lạ ở đây. Như là cỗ máy enigma ở trong chapter 01 lần trước. Một khối cầu có thể lơ lửng và một chiều không gian 4 chiều được mô phỏng dựa trên chiều không gian 3 chiều. Là một người rất thân với Cpascal Thì abcnickname rất bất ngờ vì anh ấy chưa thấy rất nhiều thứ đồ sộ đến như vậy. Nhưng thứ anh ta quan tâm nhất là một cái máy dò mình. Chức năng của chúng là có thể dò được số lượng khu vực và chiều rộng của chúng. Và trước mặt của anh ấy là một ô mình với kích thước ~nxn~ và ~k~ mìn được đặt ngẫu nhiên. Dấu hiệu để nhận biết chúng đó là xung quanh bãi mình đó(tính cả đường chéo) đều được +1 đơn vị

Yêu cầu: Tính tổng các ô có số lượng ô trống lớn nhất

Dữ liệu vào

• Một số nguyên ~n~ tượng trưng cho kích thước của bảng ~n~ x ~n~ (5 ≤ n ≤ 100)
• Một cái bảng có các chi tiết như sau
• ~9~ là vị trí của mìn

Dữ liệu ra

• In ra một dãy số nguyên sắp xếp không giảm

Ví dụ

input: 01

9
0 0 0 0 0 0 0 0 0 
0 9 0 0 0 0 0 9 0 
0 0 0 0 0 0 0 0 0 
0 0 0 9 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 9 0 0 0 0 0 0 
0 0 0 0 0 0 0 9 0 
0 0 0 0 9 0 0 0 0 
0 0 9 0 0 0 0 0 0 

output: 01

3 7 17

Chi tiết

Ta sẽ được một bãi mình như sau

1 1 1 0 0 0 1 1 1 
1 9 1 0 0 0 1 9 1 
1 1 2 1 1 0 1 1 1 
0 0 1 9 1 0 0 0 0 
0 1 2 2 1 0 0 0 0 
0 1 9 1 0 0 1 1 1 
0 1 1 2 1 1 1 9 1 
0 1 1 2 9 1 1 1 1 
0 1 9 2 1 1 0 0 0 

• Ta thấy có 3 mảnh là bị chia cắt bởi những quả mình và vị trí của chúng
• Sau đó tính những ô đó và sắp xếp chúng

Sau rất nhiều ô mình được tìm thấy. Thì abcnickname đã thoát ra được khỏi khu vực đó. Thì anh ấy đến thử thách cuối cùng, nhưng cũng là thử thách dễ hơn. Anh ấy bước vào căn phòng gồm ~n~ cột. Mỗi cột có các kích thước như sau(Chiều rộng bằng 1 và chiều dài bằng ~a[i]~). Nhiệm vụ của bạn là tìm được một dãy cột sao cho kết hợp lại ra được hình chữ nhật với chiều dài bằng tổng số cột được chọn, chiều rộng bằng cây cột có chiều dài bé nhất có diện tích lớn nhất.

Dữ liệu vào

• Là một số nguyên ~n~ tượng trưng cho số cột (~1 ≤ n ≤ 10^6~)
• Là những chiếc cột có chiều dài ~a[1],a[2],...,a[n]~ (~1 ≤ a[i] ≤ 10^9~)

Dữ liệu ra

• Diện tích lớn nhất của hình chữ nhật được kết hợp bởi những cây cột

Ví dụ

Input: 01

8
5 4 1 4 3 5 4 1

Output: 01

12

Khi tìm được những cây cột đó. Thì cánh của vẫn thực sự chưa mở được lối mòn dẫn đến cỗ máy dịch chuyển đó. Thứ trước mắt anh ấy là ~n~ ô gạch rất rộng trong đó

• Viên gạch có chứa " . " là viên gạch trống, không cần phải làm gì
• Viên gạch có chứa "X" là ô gạch có một tảng đá khổng lồ cao hàng ngàn mét với sức nặng lên đến nghìn tấn

Trên tay bạn là một khẩu súng có thể di chuyển những tảng đá đó di chuyển trái, phải 1 ô. Nhưng vì phần hiện thị số lần sử dụng của súng bị hỏng nên bạn không thể xác định được số lần di chuyển còn lại là bao nhiêu. Để hồi phục lại số lần di chuyển không xác định thì cần phải đi qua bức tường đó và chỉ sạc lại đúng 1 lần duy nhất. Bạn cũng được biết thông tin rằng để có thể qua được bức tường đó. Ta cần phải tạo một ô trống đủ lớn với kích thước ~a[i]~ để có thể đi qua

Yêu cầu: Tính số bước di chuyển ít nhất để có thể mở một lối đi kích thước ~a[i]~

Dữ liệu vào

• Một số nguyên ~n~ (1 ≤ n ≤ 10)
• Một dãy giống như xâu ~s~ với kích thước không quá ~10^4~. Kèm thêm số nguyên ~a[i]~ tượng trưng cho kích thước lối đi tối thiếu cần có để có thể vượt qua bức tường đó
• Một xâu ~s~ gồm và chỉ gồm có các ký tự sau
• Dấu chấm . biểu hiện cho ô trống
• Ký tự "X" biểu hiện cho ô có tảng đá khổng lồ

Dữ liệu ra

• Lần lượt là số lần di chuyển viên gạch tối thiểu để có thể qua được các bức tường đó

Ví dụ

Input: 01

4
.XX..XX.X. 2
.XX..XX.X. 3
.XX..XX.X. 4
.XX..XX.X. 5

Output: 01

0
2
4
7

CHI TIẾT

• Di chuyển tảng đá sao cho có 2 ô trống thì ta không cần di chuyển vì đã có sẵn rồi
• Di chuyển tảng đá sao cho có 3 ô trống thì ta có thể di chuyển như thế này

XX...XX.X.

Có tổng cộng 2 lần di chuyển

• Di chuyển tảng đá sao cho có 4 ô trống thì ta có thể di chuyển nhu thế này

XX....XXX.

Có tổng cộng 4 lần di chuyển

• Di chuyển tảng đá sao cho có 5 ô trống thì ta có thể di chuyển nhu thế này

XX.....XXX

Có tổng cộng 7 lần di chuyển