Anh Quân đang chơi một trò chơi trên trục số một chiều.

Nhân vật của anh đứng tại điểm ~0~ trên trục số, với ~s~ điểm thể lực ban đầu. Mục tiêu là đi đến điểm ~d~ (~d > 0~).

Trong mỗi lượt, anh chỉ được chọn một trong hai hành động sau:

1. Nghỉ ngơi dưới bóng râm

   • Thể lực tăng thêm ~1~ điểm.

2. Di chuyển sang phải

   • Nếu hiện tại đang ở vị trí ~x~, anh có thể đi đến ~x + 1~.
   • Gọi ~k~ là số lượt di chuyển liên tiếp tính từ sau lần nghỉ gần nhất (hoặc từ đầu nếu từ đầu chỉ toàn di chuyển). Khi đó, nếu đây là lần di chuyển liên tiếp thứ ~k~, anh sẽ mất ~k~ điểm thể lực.
   • Nước đi này chỉ hợp lệ nếu sau khi trừ đi ~k~ điểm, thể lực vẫn lớn hơn ~0~. Nếu thể lực sau khi di chuyển trở thành ~0~ hoặc âm, thì không được phép thực hiện nước đi đó.

Hãy tìm số lượt ít nhất (gồm cả lượt nghỉ và lượt di chuyển) để anh có thể đi từ điểm ~0~ đến đúng điểm ~d~.

Yêu cầu

Cho hai số nguyên dương ~s~ và ~d~, hãy tính số lượt tối thiểu ~T~ để nhân vật xuất phát từ điểm ~0~, có ~s~ điểm thể lực ban đầu, đi đến điểm ~d~ theo đúng luật chơi.

Dữ liệu

• Dòng duy nhất chứa hai số nguyên dương ~s~ và ~d~ — lần lượt là số điểm thể lực ban đầu và vị trí đích trên trục số.

Kết quả

• In ra một số nguyên duy nhất — số lượt tối thiểu ~T~ cần để đến được điểm ~d~.

Ví dụ

Ví dụ 1

Input

3 2

Output

3

Ví dụ 2

Input

1 1

Output

2

Giải thích

Ví dụ 1

• Ban đầu: vị trí ~0~, thể lực ~3~.
• Lượt ~1~: di chuyển từ ~0~ đến ~1~. Đây là lần di chuyển liên tiếp thứ ~1~, mất ~1~ thể lực, còn ~2~.
• Lượt ~2~: nghỉ ngơi, thể lực tăng ~1~, từ ~2~ lên ~3~. Chuỗi di chuyển liên tiếp được đặt lại.
• Lượt ~3~: di chuyển từ ~1~ đến ~2~. Đây lại là lần di chuyển liên tiếp thứ ~1~, mất ~1~ thể lực, còn ~2~.

Đã đến điểm ~d = 2~ sau ~3~ lượt. Nếu thử di chuyển liên tiếp hai lần từ đầu (mất ~1~ rồi ~2~ thể lực) thì sau lượt thứ hai thể lực còn ~0~, không hợp lệ, nên không thể ít hơn ~3~ lượt.

Ví dụ 2

• Ban đầu: vị trí ~0~, thể lực ~1~.
• Không thể di chuyển ngay, vì nếu di chuyển (lần di chuyển thứ ~1~) sẽ mất ~1~ thể lực và còn ~0~, là không hợp lệ.
• Lượt ~1~: nghỉ ngơi, thể lực tăng từ ~1~ lên ~2~.
• Lượt ~2~: di chuyển từ ~0~ đến ~1~, mất ~1~ thể lực (lần di chuyển liên tiếp thứ ~1~), còn ~1~.

Đã đến điểm ~d = 1~ sau ~2~ lượt.

Ràng buộc và chấm điểm

Ràng buộc

• Thời gian: ~1~ giây.
• Trong tất các test, ~1 \le s, d \le 10^9~

Chấm điểm

• Subtask1 ~(30\%~ số test): dữ liệu nhỏ (các giá trị ~s~, ~d~ không quá lớn).
• Subtask2 ~(70\%~ số test còn lại): không có ràng buộc gì thêm ngoài việc ~s~, ~d~ là số nguyên dương.

Cho một bảng hình chữ nhật gồm ~n~ hàng và ~m~ cột. Hàng được đánh số từ ~1~ đến ~n~ (từ trên xuống dưới), cột được đánh số từ ~1~ đến ~m~ (từ trái sang phải). Ô ở hàng ~i~, cột ~j~ có giá trị nguyên ~a_{i,j}~.

Với mỗi bảng vuông ~k \times k~, ta định nghĩa:

• Đường chéo chính là các ô có chỉ số ~(x, x)~, với ~1 \le x \le k~ (tính trong hệ chỉ số của hình vuông đó).
• Nửa dưới của hình vuông là tất cả các ô nằm trên hoặc dưới đường chéo chính, tức là các ô ~(x, y)~ sao cho ~1 \le x \le k~, ~1 \le y \le k~ và ~x \ge y~.

Nhiệm vụ của bạn là chọn một hình vuông ~k \times k~ nằm hoàn toàn trong bảng ban đầu sao cho tổng các số trong nửa dưới của hình vuông đó là lớn nhất. Hãy tìm giá trị tổng lớn nhất này.

Yêu cầu

Cho ma trận hình chữ nhật ~n \times m~ và một số nguyên dương ~k~, hãy chọn một hình vuông con kích thước ~k \times k~ sao cho tổng các phần tử thuộc nửa dưới của hình vuông đó lớn nhất có thể.

Hãy in ra giá trị tổng lớn nhất đó.

Dữ liệu

• Dòng đầu tiên chứa ba số nguyên dương ~n~, ~m~, ~k~.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên, là các giá trị ~a_{i,j}~ của bảng.

Giả sử luôn tồn tại ~k \le \min(n, m)~, nên luôn có ít nhất một hình vuông ~k \times k~ trong bảng.

Kết quả

In ra một số nguyên duy nhất — tổng lớn nhất của các phần tử thuộc nửa dưới một hình vuông ~k \times k~ bất kỳ trong bảng.

Ví dụ

Ví dụ 1

Input

3 4 2
1 2 1 1
2 1 3 4
1 2 1 2

Output

8

Giải thích

Ví dụ 1

Các hình vuông ~2 \times 2~ có thể chọn (đánh dấu trên ma trận):

• Hình vuông ở góc trên bên trái:

1 2
2 1

Nửa dưới gồm các phần tử: ~1~, ~2~, ~1~, tổng ~1 + 2 + 1 = 4~.

• Hình vuông cho kết quả tốt nhất: lấy các hàng ~1~, ~2~ và các cột ~3~, ~4~ của ma trận ban đầu:

Ma trận ban đầu:

1 2 1 1
2 1 3 4
1 2 1 2

Hình vuông ~2 \times 2~ tương ứng là:

1 1
3 4

Nửa dưới gồm các phần tử: ~1~, ~3~, ~4~, tổng ~1 + 3 + 4 = 8~.

Trong tất cả các hình vuông ~2 \times 2~ có thể chọn, tổng lớn nhất ở nửa dưới là ~8~, nên kết quả cần in là ~8~.

Ràng buộc và chấm điểm

Ràng buộc

• Giới hạn thời gian: ~1~ giây.
• ~1 \le n, m \le 2000~
• ~1 \le k \le \min(n, m)~
• ~|a_{i,j}| \le 10^9~

Chấm điểm

• Subtask1 ~(30\%~ số điểm): ~n, m \le 100~.
• Subtask2 ~(40\%~ số điểm): ~n, m \le 500~.
• Subtask3 ~(30\%~ số điểm): Không có ràng buộc bổ sung ngoài giới hạn tổng quát nêu trên.

Một công ty muốn lắp đặt hệ thống camera giám sát trên mạng lưới đường dây được mô hình hóa bằng cây (đồ thị vô hướng, liên thông, có ~n~ đỉnh và ~n-1~ cạnh). Đỉnh ~i~ có chi phí lắp camera là ~w_i~.

Nếu đặt camera tại đỉnh ~u~, nó sẽ giám sát được chính đỉnh ~u~ và tất cả các đỉnh có khoảng cách không quá ~k~ cạnh từ ~u~.

Trong cây có một số đỉnh được coi là quan trọng, bắt buộc phải nằm trong tầm giám sát của ít nhất một camera.

Yêu cầu

Cho cây gồm ~n~ đỉnh, bán kính giám sát ~k~, trọng số (chi phí) ~w_i~ của từng đỉnh, và danh sách các đỉnh quan trọng.

Hãy chọn một tập các đỉnh để đặt camera sao cho:

• Mỗi đỉnh quan trọng đều nằm trong khoảng cách không quá ~k~ cạnh tới ít nhất một đỉnh được chọn.
• Tổng trọng số của các đỉnh được chọn là nhỏ nhất có thể.

In ra tổng trọng số nhỏ nhất đó.

Dữ liệu

• Dòng thứ nhất chứa hai số nguyên dương ~n~, ~k~ — số đỉnh của cây và phạm vi giám sát (theo số cạnh).
• Dòng thứ hai chứa ~n~ số nguyên dương ~w_1, w_2, \dots, w_n~, trong đó ~w_i~ là trọng số của đỉnh ~i~.
• Dòng thứ ba chứa một số nguyên dương ~t~ — số đỉnh quan trọng cần được giám sát.
• Dòng thứ tư chứa ~t~ số nguyên phân biệt trong đoạn từ ~1~ đến ~n~, là các chỉ số những đỉnh quan trọng.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~ (~1 \le u, v \le n~, ~u \ne v~), biểu diễn một cạnh nối hai đỉnh ~u~ và ~v~ của cây.

Đảm bảo rằng đồ thị cho bởi các cạnh là một cây.

Kết quả

In ra một số nguyên duy nhất — tổng trọng số nhỏ nhất của các đỉnh được chọn để đặt camera thoả mãn yêu cầu giám sát tất cả các đỉnh quan trọng.

Ví dụ

Ví dụ 1

Input

12 2
8 9 12 6 1 1 5 1 4 8 10 6
10
1 2 3 5 6 7 8 9 10 11
1 3
2 3
3 4
4 5
4 6
4 7
7 8
8 9
9 10
10 11
11 12

Output

10

Giải thích

Ví dụ 1

Cây có ~12~ đỉnh, bán kính giám sát ~k = 2~. Các đỉnh quan trọng là ~1, 2, 3, 5, 6, 7, 8, 9, 10, 11~.

Một cách chọn tối ưu là đặt camera tại các đỉnh ~4~ và ~9~:

• Tổng chi phí: ~w_4 + w_9 = 6 + 4 = 10~.
• Từ đỉnh ~4~, với khoảng cách không quá ~2~ cạnh, ta giám sát được các đỉnh ~2, 3, 4, 5, 6, 7~ (và cả ~1~ thông qua đường ~4 - 3 - 1~, khoảng cách ~2~ cạnh).
• Từ đỉnh ~9~, với khoảng cách không quá ~2~ cạnh, ta giám sát được các đỉnh ~7, 8, 9, 10, 11~.

Như vậy tất cả các đỉnh quan trọng đều được giám sát, và không thể đạt tổng chi phí nhỏ hơn ~10~, nên đáp án là ~10~.

Ràng buộc và chấm điểm

Ràng buộc

• Thời gian: ~1~ giây.

• Bộ test đảm bảo:

  • ~1 \le n \le 2 \cdot 10^5~
  • ~1 \le k \le n~
  • ~1 \le w_i \le 10^9~
  • ~1 \le t \le n~

Chấm điểm

• Subtask1 ~(20\%~ số điểm): ~n \le 2000~.
• Subtask2 ~(20\%~ số điểm): ~n \le 10^4~.
• Subtask3 ~(20\%~ số điểm): ~n \le 5 \cdot 10^4~.
• Subtask4 ~(20\%~ số điểm): ~n \le 10^5~.
• Subtask5 ~(20\%~ số điểm): Không có ràng buộc bổ sung ngoài giới hạn tổng quát nêu trên.

Một chuỗi số chỉ gồm các chữ số từ ~1~ đến ~9~ được viết trên bảng. Gọi ~|S|~ là độ dài của chuỗi ~S~.

Với mỗi cặp chỉ số ~(i, j)~ thoả mãn ~1 \le i \le j \le |S|~, ta lấy các kí tự từ vị trí ~i~ đến ~j~ (liên tiếp trong chuỗi) để tạo thành một số tự nhiên (theo hệ thập phân thông thường).

Nhiệm vụ của bạn là đếm xem có bao nhiêu cặp ~(i, j)~ sao cho số đó chia hết cho ~2019~.

Yêu cầu

Cho một chuỗi ~S~ chỉ chứa các chữ số từ ~1~ đến ~9~, hãy đếm số lượng cặp chỉ số ~(i, j)~ với ~1 \le i \le j \le |S|~ sao cho số được tạo từ đoạn con liên tiếp ~S_i S_{i+1} \dots S_j~ chia hết cho ~2019~.

In ra số lượng cặp như vậy.

Dữ liệu

• Dòng duy nhất chứa chuỗi ~S~, chỉ gồm các kí tự là chữ số từ ~'1'~ đến ~'9'~.
• Độ dài chuỗi thoả mãn ~1 \le |S| \le 200000~.

Kết quả

Ghi ra một số nguyên duy nhất — số cặp ~(i, j)~ sao cho số được tạo từ ~S_i S_{i+1} \dots S_j~ chia hết cho ~2019~.

Ví dụ

Ví dụ 1

Input

1817181712114

Output

3

Ví dụ 2

Input

14282668646

Output

2

Ví dụ 3

Input

2119

Output

0

Giải thích

Ví dụ 1

Với chuỗi ~S = 1817181712114~, có đúng ~3~ cặp ~(i, j)~ thoả mãn đề bài, đó là:

• ~(1, 5)~
• ~(5, 9)~
• ~(9, 13)~

Ba đoạn con tương ứng tạo thành các số đều chia hết cho ~2019~.

Ví dụ 2

Với chuỗi ~S = 14282668646~, có đúng ~2~ cặp thoả mãn:

• ~(3, 7)~
• ~(7, 11)~

Hai đoạn con tương ứng tạo thành các số đều chia hết cho ~2019~.

Ví dụ 3

Với chuỗi ~S = 2119~, không có đoạn con liên tiếp nào tạo thành số chia hết cho ~2019~, nên kết quả bằng ~0~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le |S| \le 200000~
• Các kí tự của ~S~ đều nằm trong ~{1, 2, 3, 4, 5, 6, 7, 8, 9}~.
• Thời gian: ~1~ giây.
• Bộ nhớ: ~256~ MB.

Chấm điểm

• Subtask 1 (30% số test): ~|S| \le 500~.
• Subtask 2 (30% số test): ~|S| \le 50000~.
• Subtask 3 (40% số test): ~|S| \le 200000~.

An có ~n~ cái cốc được gán nhãn lần lượt từ ~1, 2, \dots, n~, mỗi cốc có dung tích không hạn chế và ban đầu đều chứa nước.

An muốn uống hết nước nhưng chỉ uống ở đúng ~k~ cốc. Vì vậy, An sẽ rót nước từ cốc này sang cốc khác sao cho cuối cùng chỉ còn đúng ~k~ cốc còn nước, các cốc còn lại đều rỗng.

Khi rót nước từ cốc ~i~ sang cốc ~j~, An mất một lượng thời gian là ~C_{ij}~. Biết rằng:

• ~C_{ij} \ge 0~ với mọi ~1 \le i, j \le n~.
• Nếu ~i = j~ thì ~C_{ij} = 0~.

Hãy giúp An quyết định rót nước từ cốc nào sang cốc nào, theo thứ tự nào, sao cho:

• Cuối cùng chỉ còn đúng ~k~ cốc có nước.
• Tổng thời gian rót nước là nhỏ nhất có thể.

Yêu cầu

Cho ~n~, ~k~ và ma trận thời gian ~C_{ij}~, hãy tìm tổng thời gian ít nhất cần dùng để thực hiện các lần rót nước sao cho cuối cùng chỉ còn đúng ~k~ cốc có nước.

Dữ liệu

• Dòng 1 chứa hai số nguyên ~n~, ~k~ (~1 \le k \le n \le 20~).
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên ~C_{ij}~ (~0 \le C_{ij} \le 10^5~) — thời gian cần thiết để rót nước từ cốc ~i~ sang cốc ~j~.
• Luôn có ~C_{ii} = 0~ với mọi ~i~.

Kết quả

In ra một số nguyên duy nhất — tổng thời gian nhỏ nhất mà An cần sử dụng để thực hiện việc rót nước, sao cho cuối cùng chỉ còn đúng ~k~ cốc còn nước.

Ví dụ

Ví dụ 1

Input

4 2
0 8 49 23
7 0 30 22
44 28 0 23
9 40 15 0

Output

16

Giải thích

Với ~n = 4~, ~k = 2~.

Ma trận thời gian:

• Từ cốc ~1~ sang ~2, 3, 4~ lần lượt tốn ~8, 49, 23~.
• Từ cốc ~2~ sang ~1, 3, 4~ lần lượt tốn ~7, 30, 22~.
• Từ cốc ~3~ sang ~1, 2, 4~ lần lượt tốn ~44, 28, 23~.
• Từ cốc ~4~ sang ~1, 2, 3~ lần lượt tốn ~9, 40, 15~.

Một cách tối ưu:

• Rót nước từ cốc ~2 \rightarrow 1~, tốn ~7~.
• Rót nước từ cốc ~4 \rightarrow 1~, tốn ~9~.

Lúc này:

• Cốc ~1~ chứa nước (từ chính nó, cốc ~2~, cốc ~4~).
• Cốc ~3~ vẫn còn nước ban đầu.
• Cốc ~2~ và ~4~ đã rỗng.

Như vậy An chỉ cần uống ở cốc ~1~ và cốc ~3~, đúng ~k = 2~ cốc. Tổng thời gian rót là ~7 + 9 = 16~, không thể nhỏ hơn, nên đáp án là ~16~.

Ràng buộc

• ~1 \le n \le 20~
• ~1 \le k \le n~
• ~0 \le C_{ij} \le 10^5~, ~C_{ii} = 0~.

Chấm điểm

• Subtask 1 (40% số test): ~1 \le n \le 10~.
• Subtask 2 (60% số test): ~1 \le n \le 20~ (không có ràng buộc gì thêm).

Trong công ty XYZ có ~N~ nhân viên rất xuất sắc. Nhưng vì ai cũng quá giỏi và quá tự tin nên hễ có từ 2 nhân viên trở lên cùng làm việc tại cùng một thời điểm thì hiệu suất lúc đó coi như bằng 0 (họ tranh cãi và không làm được gì). Ngược lại, nếu tại một thời điểm chỉ có đúng 1 nhân viên làm việc thì thời gian đó được tính là làm việc hiệu quả.

Nhân viên thứ ~i~ có giờ làm việc cố định là một khoảng liên tiếp từ ~a_i~ đến ~b_i~ với ~a_i < b_i~ (không thể thay đổi).

Giám đốc muốn giữ lại một số nhân viên sao cho tổng thời gian làm việc hiệu quả lớn nhất.

Yêu cầu

Chọn một tập con các nhân viên để giữ lại. Gọi ~c(t)~ là số nhân viên được giữ lại đang làm việc tại thời điểm ~t~. Khi đó:

• Nếu ~c(t)=1~ thì thời điểm ~t~ đóng góp ~1~ đơn vị thời gian hiệu quả.
• Nếu ~c(t)\neq 1~ (tức ~0~ hoặc ~\ge 2~) thì thời điểm ~t~ đóng góp ~0~.

Hãy tính tổng thời gian hiệu quả lớn nhất có thể đạt được.

(Hiểu khoảng làm việc của nhân viên ~i~ là ~[a_i, b_i)~.)

Dữ liệu

• Dòng đầu ghi số nguyên ~N~ — số nhân viên (~1 \le N \le 10^5~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ ghi hai số nguyên ~a_i, b_i~ — thời điểm bắt đầu và kết thúc giờ làm việc của nhân viên ~i~ (~0 \le a_i < b_i \le 10^9~).

Kết quả

In ra một số nguyên duy nhất: tổng thời gian làm việc hiệu quả lớn nhất có thể.

Ví dụ

Ví dụ 1

Input

7
100 150
200 300
900 1000
100 1000
900 1800
1900 2000
1800 2000

Output

1800

Giải thích

Ví dụ 1

Giữ lại các nhân viên ~4, 5, 7~ với các khoảng:

• ~[100,1000)~, ~[900,1800)~, ~[1800,2000)~.

Khi đó:

• ~[100,900)~ chỉ có 1 người làm → hiệu quả ~800~.
• ~[900,1000)~ có 2 người làm → hiệu quả ~0~.
• ~[1000,1800)~ chỉ có 1 người làm → hiệu quả ~800~.
• ~[1800,2000)~ chỉ có 1 người làm → hiệu quả ~200~.

Tổng lớn nhất đạt được là ~800+800+200=1800~.

Chấm điểm

• Subtask 1 (20%): Các khoảng thời gian làm việc đôi một rời nhau (không giao nhau).
• Subtask 2 (50%): ~N \le 10^4~.
• Subtask 3 (30%): ~10^4 < N \le 10^5~.

Có ~N~ lá bài được đánh số từ ~1~ đến ~N~, lá bài thứ ~i~ ghi số nguyên dương ~A_i~.

Bạn phải chọn đúng ~K~ lá bài. Điểm nhận được:

• Nếu tất cả các số trên ~K~ lá bài đã chọn đều chẵn hoặc đều lẻ thì điểm bằng tổng các số đó.
• Ngược lại (chọn lẫn chẵn và lẻ) thì điểm bằng ~0~.

Yêu cầu

Hãy xác định số điểm lớn nhất có thể đạt được khi chọn đúng ~K~ lá bài.

Dữ liệu

• Dòng 1: hai số nguyên dương ~N, K~ (~1 \le K \le N \le 10^5~).
• Dòng 2: ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ (~1 \le A_i \le 10^9~).

Kết quả

In ra một số nguyên duy nhất là số điểm tối đa có thể đạt được.

Ví dụ

Ví dụ 1

Input

5 5
1 1 1 1 1

Output

5

Ví dụ 2

Input

6 4
1 2 1 1 2 2

Output

0

Ví dụ 3

Input

7 3
3 7 9 1 7 5 3

Output

23

Ví dụ 4

Input

10 3
23 19 21 20 22 18 22 22 24 27

Output

71

Giải thích

Ví dụ 1

Chọn cả ~5~ lá, tất cả đều lẻ nên điểm là ~1+1+1+1+1=5~.

Ví dụ 2

Muốn có điểm khác ~0~ thì phải chọn 4 lá chẵn hoặc 4 lá lẻ. Trong dữ liệu có ~3~ số chẵn và ~3~ số lẻ nên không thể chọn đủ ~4~ lá cùng tính chẵn lẻ ⇒ điểm tối đa ~0~.

Ví dụ 3

Tất cả đều lẻ. Chọn ~3~ lá có giá trị lớn nhất: ~9, 7, 7~ ⇒ điểm ~=23~.

Ví dụ 4

Có thể chọn ~3~ lá lẻ lớn nhất: ~27, 23, 21~ ⇒ tổng ~71~ (lớn hơn mọi cách chọn ~3~ lá chẵn).

Ràng buộc và chấm điểm

• Subtask 1 (30%): ~N = K~.
• Subtask 2 (25%): ~A_i \le 2~ với mọi ~i~.
• Subtask 3 (20%): Tất cả ~A_i~ đều là số lẻ.
• Subtask 4 (25%): Không có ràng buộc bổ sung.

Cẩm Linh thiết kế một poster dạng lưới ~N \times N~. Mỗi ô được tô một trong ~K~ màu (đánh số từ ~1~ đến ~K~). Cụ thể, ô hàng ~i~ cột ~j~ có màu ~A_{i,j}~.

Người ta định nghĩa độ rực rỡ của poster là số lượng hình vuông con kích thước ~2 \times 2~ có chứa ít nhất 3 màu khác nhau (tức tập các màu trong 4 ô của hình vuông đó có kích thước ~\ge 3~).

Cẩm Linh được phép thực hiện thao tác sau tối đa một lần: chọn một ô bất kỳ và tô lại ô đó bằng một màu bất kỳ trong ~[1..K]~ (cũng có thể không tô lại ô nào).

Yêu cầu

Tính độ rực rỡ lớn nhất có thể đạt được sau khi thực hiện thao tác trên tối đa một lần.

Dữ liệu

• Dòng đầu gồm hai số nguyên dương ~N, K~ (~2 \le N \le 270; 3 \le K \le 10^9~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ gồm ~N~ số nguyên dương ~A_{i,1}, A_{i,2}, \dots, A_{i,N}~ (~1 \le A_{i,j} \le K~).

Kết quả

In ra một số nguyên duy nhất: độ rực rỡ tối đa có thể đạt được.

Ví dụ

Ví dụ 1

Input

2 3
1 2
2 1

Output

1

Ví dụ 2

Input

5 5
1 1 1 2 2
1 1 1 2 2
3 3 1 2 2
3 3 5 5 5
3 3 5 5 5

Output

5

Ví dụ 3

Input

3 3
1 2 3
2 2 2
3 2 1

Output

2

Giải thích

Ví dụ 1

Chỉ có đúng một hình vuông ~2 \times 2~ (toàn bộ lưới). Ban đầu có 2 màu ~{1,2}~ nên chưa rực rỡ. Tô lại ô ~(2,2)~ thành màu ~3~, ta được:

1 2
2 3

Hình vuông ~2 \times 2~ chứa ~{1,2,3}~ nên độ rực rỡ đạt ~1~.

Ví dụ 2

Một cách tối ưu là tô lại ô ~(2,3)~ từ ~1~ thành ~4~, khi đó độ rực rỡ đạt ~5~.

Ví dụ 3

Tô lại ô trung tâm ~(2,2)~ từ ~2~ thành ~1~, ta được:

1 2 3
2 1 2
3 2 1

Khi đó có đúng ~2~ hình vuông ~2 \times 2~ chứa ít nhất 3 màu (hai hình vuông có góc trên-trái lần lượt là ~(1,2)~ và ~(2,1)~).

Ràng buộc và chấm điểm

• Subtask 1 (9%): ~N = 2~, ~K = 3~.
• Subtask 2 (6%): Các giá trị ~A_{i,j}~ đôi một phân biệt.
• Subtask 3 (27%): ~N \le 10~, ~K \le 10~.
• Subtask 4 (26%): ~N \le 10~.
• Subtask 5 (32%): Không có ràng buộc bổ sung.

Một trường học chuẩn bị tham gia chuyến dã ngoại. Có tổng cộng ~3^N~ học sinh, mỗi học sinh chọn một trong hai kế hoạch:

• Kế hoạch A
• Kế hoạch B

Ý kiến ban đầu của tất cả học sinh được mã hoá bởi xâu ~S~ độ dài ~3^N~, trong đó ký tự thứ ~i~ là A hoặc B.

Thầy Hiệu trưởng áp dụng quy tắc rút gọn để chọn kế hoạch chung như sau: thực hiện đúng ~N~ lần rút gọn, mỗi lần biến xâu độ dài ~3^K~ thành xâu độ dài ~3^{K-1}~ (với ~K>0~), trong đó: ~S'*i = \text{ký tự xuất hiện nhiều nhất trong } (S*{3i-2}, S_{3i-1}, S_{3i})~ Sau ~N~ lần, xâu chỉ còn 1 ký tự, đó là kế hoạch được chọn.

Trong thời gian tới có ~Q~ sự kiện. Mỗi sự kiện cho một vị trí ~p~: học sinh thứ ~p~ đổi ý (từ A sang B hoặc ngược lại). Mỗi thay đổi được áp dụng vĩnh viễn cho các sự kiện sau.

Yêu cầu

Sau mỗi sự kiện đổi ý, hãy in ra ký tự (A hoặc B) là kế hoạch thầy Tuấn chọn sau khi thực hiện đủ ~N~ lần rút gọn.

Dữ liệu

• Dòng 1: hai số nguyên dương ~N, Q~ (~1 \le N \le 12~, ~1 \le Q \le 2\cdot 10^5~).
• Dòng 2: xâu ~S~ độ dài ~3^N~ chỉ gồm ký tự A và B.
• ~Q~ dòng tiếp theo: mỗi dòng là một số nguyên dương ~p~ (~1 \le p \le 3^N~), tương ứng học sinh thứ ~p~ đổi ý.

Kết quả

Ghi ra ~Q~ dòng, dòng thứ ~i~ là một ký tự A hoặc B — kết quả sau sự kiện thứ ~i~.

Ví dụ

Ví dụ 1

Input

2 3
ABABBAABB
3
8
4

Output

B
B
A

Ví dụ 2

Input

2 5
AAAAAAAAA
1
2
7
8
5

Output

A
A
A
B
B

Ví dụ 3

Input

1 4
AAB
3
1
2
3

Output

A
A
B
B

Ví dụ 4

Input

3 6
AABABABBABAABABBBBBBBAABABAA
4
1
9
3
8
9

Output

B
B
B
B
B
A

Giải thích

Ví dụ 1

~N=2~ nên mỗi lần rút gọn gom theo từng bộ ~3~ ký tự và lấy đa số, làm 2 lần sẽ còn 1 ký tự. Sau mỗi lần lật tại vị trí ~p~, kết quả cuối lần lượt là B, B, A.

Ví dụ 2

Ban đầu toàn A. Một số lần lật vẫn chưa đủ tạo đa số B ở cấp cao, đến khi lật thêm thì kết quả cuối chuyển sang B.

Ví dụ 3

~N=1~ nên chỉ cần xét đúng 1 bộ ba ký tự, lấy đa số. Mỗi lần lật một vị trí sẽ làm đa số của bộ ba thay đổi tương ứng.

Ví dụ 4

Thực hiện tương tự, sau mỗi lần lật in ra kết quả cuối cùng.

Ràng buộc

• Subtask 1 (8%): ~N=1~.
• Subtask 2 (17%): ~Q \le 10~.
• Subtask 3 (22%): ~p \le 5~.
• Subtask 4 (28%): ~S~ chỉ gồm A, và các giá trị ~p~ đôi một phân biệt.
• Subtask 5 (25%): Không có ràng buộc bổ sung.

Trong cổ thư của phái CVP có ghi về cặp số thượng cổ: hai số ~a~ và ~b~ chỉ thật sự hòa hợp khi tích của chúng chia hết cho tổng của chúng.

Bạn cần đếm trong các số từ ~1~ đến ~N~, có bao nhiêu cặp ~(a,b)~ với ~1 \le a \le b \le N~ thỏa mãn: ~a \cdot b~ chia hết cho ~a+b~.

Yêu cầu

Cho số nguyên dương ~N~, hãy tính số lượng cặp ~(a,b)~ với ~1 \le a \le b \le N~ sao cho: ~(a \cdot b) \bmod (a+b) = 0~.

Dữ liệu

• Gồm một dòng duy nhất chứa số nguyên dương ~N~ (~N \le 10^{12}~).

Kết quả

• In ra một số nguyên duy nhất: số lượng cặp ~(a,b)~ thỏa mãn điều kiện.

Ví dụ

Ví dụ 1

Input

5

Output

2

Giải thích

Ví dụ 1

Có 2 cặp thỏa mãn: ~(2,2)~, ~(4,4)~.

Ràng buộc và chấm điểm

• 30%: ~N \le 2000~
• 30%: ~N \le 10^6~
• 40%: không có ràng buộc thêm.