Đối với Mirko, không có hạnh phúc nào lớn hơn việc tìm thấy một cuộn băng dính mới, và ngày hôm nay anh ấy đặc biệt hạnh phúc vì anh ấy còn tìm thêm được cuốn lịch Advent của Slavko.

Cuốn lịch Advent có thể biểu diễn như một bảng hình chữ nhật với ~n~ hàng và ~m~ cột, mỗi ô vuông chứa một cửa sổ nhỏ, và đằng sau mỗi cửa sổ là một miếng sô cô la. Slavko đã mở một số ô trong số đó, còn những cửa sổ khác vẫn đang đóng.

Mirko quyết định sử dụng cuộn băng dính của anh ấy để dán lại tất cả những cửa sổ đóng. Cuộn băng dính thì dài vô tận, và nó có chiều rộng bằng ~1~ ô của cuốn lịch. Mirko có thể xé một đoạn băng dính và dùng nó để dán một đoạn liền kề những ô cửa sổ đã đóng theo chiều dọc hoặc chiều ngang. Anh ấy không muốn dán nhiều hơn một lớp băng dính lên bất kỳ cửa sổ nào, vì anh ấy vẫn muốn giữ tình bạn với Slavko.

Anh ấy đang tự hỏi rằng, anh ấy cần tối thiểu bao nhiêu mẩu băng dính để dán lại hết các cửa sổ đóng trong cuốn lịch.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n \le 1000~, ~1 \le m \le 10~), là kích thước của cuốn lịch Advent.

• Mỗi trong ~n~ dòng tiếp theo chứa ~m~ ký tự . và #, biểu diễn cuốn lịch Advent.

• Ký tự . mô tả một ô cửa sổ đã mở

• Ký tự # mô tả một ô cửa sổ đang đóng

Output

In ra số lượng nhỏ nhất các mẩu băng dính cần thiết để dán hết những ô cửa sổ đóng.

Sample Input 1

2 3
#.#
###

Sample Output 1

3

Sample Input 2

4 3
.#.
###
.##
.#.

Sample Output 2

3

Giải thích ví dụ 1

Một cách dán hợp lý là:

• Dán một đoạn cho cột đầu tiên,

• Một đoạn cho cột thứ 3,

• Và một đoạn cho ô ở hàng 2, cột 2.

• Tổng cộng cần 3 đoạn băng dính.

Mr. Nežmah vừa bắt đầu công việc mới của mình với vai trò một quantitative researcher. Anh ấy đang làm việc với dữ liệu lịch sử của một cổ phiếu (không nêu tên) trong khoảng ~n~ ngày liên tiếp. Dữ liệu này được biểu diễn bằng một mảng ~a_i~, trong đó ~a_i~ cho biết giá của cổ phiếu thay đổi bao nhiêu vào ngày thứ ~i~.

Ngay khi bắt đầu huấn luyện mô hình, anh ấy nhận ra rằng dữ liệu bị lỗi!

Toàn bộ mảng ~a_i~ đã bị cộng sai lệch bởi một hằng số chưa biết. Một trong những đặc trưng quan trọng trong mô hình của anh ấy là độ thay đổi giá lớn nhất xảy ra trong ~n~ ngày đó. Cụ thể, đối với một mảng ~b~ có độ dài ~n~, anh ấy quan tâm đến giá trị:

~ \max_{1 \le l \le r \le n} \left( b_l + \cdots + b_r \right) ~

Bây giờ, do dữ liệu bị sai lệch, Nežmah muốn tính giá trị này đối với các bản dịch (shift) khác nhau của mảng ~a~, tức là: ~ S(x) := \max_{1 \le l \le r \le n} \left( (a_l + x) + \cdots + (a_r + x) \right) ~

Hãy giúp Nežmah tính ~S(x)~ cho ~q~ giá trị khác nhau của ~x~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 2 \cdot 10^5~).
• Dòng thứ hai chứa mảng ~a~ với ~n~ phần tử (~-10^8 \le a_i \le 10^8~).
• Dòng thứ ba chứa ~q~ truy vấn — mỗi truy vấn là một giá trị ~x~ (~-10^8 \le x \le 10^8~).

Output

Với mỗi test, in ra ~q~ số: đáp án cho từng truy vấn theo đúng thứ tự.

Ví dụ

Input

5 7
1 2 6 9 -4
0 -1 -20 -2 5 -4 -8

Output

18 14 -11 11 39 7 1

Input

7 8
6 -14 1 5 -14 3 -8
-5 -3 0 4 5 6 8 9

Output

1 3 6 14 18 23 35 42

Mọi người đang chuẩn bị cho kỳ nghỉ. Một hoạt động mà nhiều người thích trong kỳ nghỉ là đi công viên giải trí.

Kantipa là người vận hành một trò chơi trong công viên giải trí. Có ~n~ người đang xếp hàng để chơi trò này. Những người này được đánh số từ ~1~ đến ~n~, theo thứ tự từ đầu hàng đến cuối hàng. Mỗi người có một giá trị ~A_i~.

Kantipa có quyền phớt lờ quy tắc xếp hàng và cho họ chơi theo bất kỳ thứ tự nào mà cô ấy muốn. Do đó, có ~n!~ cách sắp xếp thứ tự chơi.

Với một thứ tự chơi mà Kantipa chọn, mức độ tức giận (anger level) của người ~i~ được tính như sau:

1. Gọi ~p~ là vị trí mà người ~i~ chơi.
2. Gọi ~s~ là tổng các giá trị ~A_j~ của mọi người ~j~ thỏa:
   • ban đầu đứng phía sau người ~i~ trong hàng,
   • nhưng lại được cho chơi sớm hơn người ~i~.
3. Mức độ tức giận của người ~i~ được tính: ~ p \times A_i + s ~

Tổng mức độ tức giận của một thứ tự chơi là tổng mức độ tức giận của toàn bộ ~n~ người.

Yêu cầu

Có tất cả ~n!~ giá trị tổng mức độ tức giận ứng với mọi thứ tự chơi. Kantipa muốn:

1. Tạo một mảng chứa tất cả ~n!~ giá trị này.
2. Sắp xếp mảng theo thứ tự không giảm.
3. Lấy phần tử thứ ~K~ trong mảng đã sắp xếp.

Hãy giúp cô ấy tìm giá trị đó.

Input

• Dòng đầu tiên: hai số nguyên ~n~ và ~K~
  ~1 \le n \le 200000~
  ~1 \le K \le \min(n!,\, 200000)~

• Dòng thứ hai: chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~
  ~1 \le A_i \le 200000~

Output

In ra một số nguyên — giá trị của phần tử thứ ~K~ trong mảng các tổng mức độ tức giận đã sắp xếp.

Ví dụ

Input

3 4  
2 6 5

Output

35

Input

4 7  
1 1 1 1

Output

12

Trong bài này, bạn cần duy trì một multiset ~T~ mà mỗi phần tử của nó là một cặp ~(v_i, w_i)~. Ban đầu, ~T~ rỗng. Bạn cần thực hiện ~n~ thao tác, mỗi thao tác thuộc một trong ba loại sau:

• + v w với ~1 \le v \le 500000~, ~1 \le w \le n~: Chèn cặp ~(v, w)~ vào đa tập ~T~.

• - v w với ~1 \le v \le 500000~, ~1 \le w \le n~: Xóa một cặp ~(v, w)~ khỏi ~T~. Đảm bảo rằng cặp đó luôn tồn tại trong ~T~. Lưu ý ~T~ là một đa tập, nếu có nhiều bản sao của cùng một cặp, chỉ cần xóa đúng một bản.

• ? k với ~1 \le k \le 500000~: Đây là một truy vấn. Bạn cần tìm một cặp ~(v, w)~ trong ~T~ sao cho: ~ \gcd(v, k) = 1 ~ và trong tất cả những cặp thỏa điều kiện trên, giá trị ~w~ là lớn nhất.
Hãy in ra giá trị ~w~ đó. Nếu không tồn tại cặp phù hợp, hãy in -1.

Input

Chỉ có một test mỗi lần chạy.

Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 200000~) — số lượng thao tác.

Mỗi dòng tiếp theo mô tả một thao tác theo đúng định dạng đã mô tả ở trên.

Output

Với mỗi truy vấn ? k, hãy in ra một dòng chứa giá trị ~w~ tương ứng, hoặc -1 nếu không tìm được.

Ví dụ

Input

6
+ 4 5
+ 3 4
? 2
? 3
- 3 4
? 4

Output

4
5
-1