2025.04.27

Mùa đông lạnh lẽo đã tới rồi. Chúng mình xin được chúc tất cả các bạn nam đang làm contest này sẽ có người yêu, đừng như shiba trong chuỗi bài này nhé!

Nổi danh đã lâu trong giới lập trình thi đấu nhưng mà là "ao hồ", Trần Thanh Nguyên - còn được biết đến với shiba - là một chàng trai với cơ bụng sáu múi, cao mét tám. Có thể nói là mẫu chồng quốc dân của chị em. À đó là Trần Thanh Nguyên nào chứ shiba này là một chàng trai học công nghệ thông tin bình thường. Trước kia, cậu ấy có một cô bạn gái cực kì xinh gái, nhưng đã không giữ được cô ấy do không thực sự xuất sắc lắm ~nói thẳng ra là do lúc đó anh ta quá nghèo~. Giờ đây đã khác, tuy shiba có tất cả, nhưng giống như lời bài hát nào đó, "chúng ta sau này, chẳng có chúng ta sau này", có tất cả nhưng lại không có em. Chính vì vậy, cậu ấy rất nặng tình với "người yêu cũ" của mình, đó là cậu ấy nói vậy, còn người đời như _minhduc hay Flower_On_Stone thì lại cho là "luỵ", "nhớ" người yêu cũ.

Ngày \(19/11\) năm nay, shiba không có ai chúc mừng ngày Quốc tế Đàn ông, cậu ấy lại nhớ ngày xửa ngày xưa, người ấy đã chúc cậu ấy ngày \(19/11\) vui vẻ như thế nào. Và cậu nhớ lại kỉ niệm với cô ấy. Để hồi tưởng lại, cậu ấy quyết định hồi tưởng từ ngày bắt đầu tán cô ấy.

shiba đã chọn cách tán gái mà đa phần các chàng trai hay làm, đó là tặng sữa Milo cho cô bạn kia. Để nhắc mình nhớ về ngày hôm ấy có tặng cô bạn của mình sữa hay không, cậu ấy sẽ ghi số \(1\) hoặc \(0\) vào nhật kí của mình, biểu diễn cho ngày hôm ấy cậu ấy có hay không mua sữa cho cô bạn của mình. Lâu dần, việc này đã biến cuốn nhật kí của shiba thành một xâu nhị phân \(s\). Việc tán cô bạn đã tốn mất \(n\) ngày của shiba, nên xâu nhị phân đó có độ dài là \(n\).

Giờ đây, chỉ còn mình shiba ngồi lại, cậu ấy nhớ lại những kỉ niệm mua sữa cho cô ấy, và cậu ấy nhận thấy, không biết có phải trùng hợp ngẫu nhiên hay không, nếu như từ ngày \(l\) tới ngày \(r\) (\(l \le r\)), biểu diễn thập phân của đoạn đó đúng bằng \(r-l+1\) thì cô ấy sẽ cực kì vui vẻ và cậu ấy coi đây là một quãng đẹp. Nói cách khác, gọi \(f(l,r)\) là giá trị một số nguyên biểu diễn dưới dạng xâu nhị phân của xâu \(S\) được cắt ra từ vị trí \(l\) đến \(r\) của xâu \(s\), nếu \(f(l,r) = r-l+1\) thì đây sẽ được coi là một quãng đẹp. Cậu ấy tự hỏi, quãng thời gian đó, cô ấy đã vui vẻ được bao nhiêu lần, cậu ấy đã tạo ra được bao nhiêu quãng đẹp. Các quãng đẹp nếu đè lên nhau hoặc chứa nhau vẫn được coi là hai quãng đẹp riêng biệt.

Yêu cầu: Tính số quãng đẹp mà shiba đã tạo ra.

Input

• Dòng đầu tiên chứa một số nguyên \(\phi\) - số thứ tự của subtask chứa test đó.
• Dòng thứ hai chứa một số nguyên dương \(n\) (\(n \le 5 \times 10^5\)).
• Dòng thứ ba chứa một xâu nhị phân \(s\) độ dài \(n\).

Output

• Một dòng chứa một số nguyên là kết quả bài toán.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): xâu \(s\) chỉ chứa một loại kí tự.
• Subtask \(2\) (\(10\%\) số điểm): \(n \le 50\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^3\).
• Subtask \(4\) (\(15\%\) số điểm): xâu được tạo thành từ một xâu con lặp lại nhiều lần, độ dài xâu con đó không vượt quá \(30\) (*).
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^4\).
• Subtask \(6\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

2
4
0110

4

Vào ngày nghỉ, Đạt và Châu cùng nhau chơi tựa game Liên Minh Huyền Thoại. Để dạy Châu cách ra đòn đánh cuối cùng vào lính, Đạt đã tạo ra \(n\) con lính, con lính thứ \(i\) sẽ bị hạ gục khi nhận ít nhất \(a_{i}\) đòn đánh. Cả hai người đều sử dụng kĩ năng đánh thường, mỗi đòn đánh thường đều sẽ gây \(1\) sát thương cho lính. Hai người đánh các con lính lần lượt theo thứ tự từ \(1\) đến \(n\) cùng với nhau. Khi hạ gục con lính trước, hai người mới cùng chuyển sang đánh con lính sau. Nhân vật của Đạt có thể thực hiện \(x\) đòn đánh mỗi giây (nghĩa là sau mỗi \(\frac{1}{x}\) giây, nhân vật của Đạt sẽ thực hiện một đòn đánh), còn nhân vật của Châu có thể thực hiện \(y\) đòn đánh mỗi giây (nghĩa là sau mỗi \(\frac{1}{y}\) giây, nhân vật của Châu sẽ thực hiện một đòn đánh). Hỏi với mỗi con lính, người tiêu diệt con lính đó sẽ là ai, biết rằng người thực hiện đòn đánh cuối cùng sẽ được tính là người tiêu diệt con lính đó, nếu như hai người cùng thực hiện đòn đánh cuối cùng lên con lính cùng lúc thì sẽ tính là cả hai cùng tiêu diệt con lính đó.

Input

• Dòng thứ nhất chứa ba số nguyên \(n, x, y\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq x, y \leq 10^{6})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\).

Output

• Với mỗi con lính bị tiêu diệt, in ra trên một dòng. Nếu con lính bị hạ gục bởi Đạt, in ra một dòng \texttt{D}, nếu con lính bị hạ gục bởi Châu, in ra một dòng \texttt{C}, nếu con lính bị hạ gục bởi cả hai người, in ra một dòng \texttt{Both}.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(x = 1, y = 2\).
• Subtask \(2\) (\(30\%\) số điểm): \(x = 1\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

4 1 2
5 6 10 12

Both
Both
C
Both

Thành phố Nồi Hạ có phân bổ dân cư hết sức đặc biệt: Thành phố có \(r \cdot c\) khu dân cư đựoc xếp dưới dạng lưới hình chữ nhật gồm \(r\) hàng và \(c\) cột. Các hàng được đánh số từ \(1\) đến \(r\), các cột được đánh số từ \(1\) đến \(c\). Khu dân cư nằm trên giao của hàng \(i\) và cột \(j\) được kí hiệu là \((i, j)\).

Trong đợt khảo sát vừa qua, lãnh đạo thành phố đã đi từng ngõ, gõ từng nhà để thu thập thông tin về chất lượng cuộc sống ở các khu dân cư. Tiếp đó, họ xếp hạng các khu dân cư bằng các con số phân biệt từ \(1\) đến \(r \cdot c\). Khu dân cư xếp hạng \(1\) có chất lượng cuộc sống tốt nhất. Khu dân cư xếp hạng \(r \cdot c\) có chất lượng tệ nhất. Khu dân cư được xếp hạng càng nhỏ thì chất lượng sống càng cao. Theo kết quả, khu dân cư \((i, j)\) được xếp hạng \(p_{i, j}\).

Từ kết quả xếp hạng, thành phố sẽ chọn ra một khu vực để tăng cường đầu tư nhằm nâng cao chất lượng cuộc sống ở đây. Thành phố quyết định rằng các khu dân cư được nâng cấp sẽ nằm trong một hình chữ nhật con có kích thước \(h \cdot w\) (gồm \(h\) hàng và \(w\) cột), với \(h\) và \(w\) là các số lẻ. Lãnh đạo thành phố muốn chọn những nơi chất lượng sống còn thấp để ưu tiên cải tạo, nhưng họ cần đưa ra một tiêu chí đánh giá chung cho một vùng hình chữ nhật kích thước \(h \cdot w\). Theo đó, "mức sống tiêu biểu" của một khu vực là trung vị của thứ hạng chất lượng cuộc sống của các khu dân cư bên trong đó. (xem phần dưới để biết định nghĩa về trung vị)

Khu vực được chọn để đầu tư phải có "mức sống tiêu biểu" lớn nhất (vì thứ hạng càng lớn thì chất lượng cuộc sống càng thấp) trong các khu vực có thể chọn. Bạn hãy giúp họ tìm ra "mức sống tiêu biểu" lớn nhất này nhé.

Giá trị trung vị của một dãy số \((a_1, a_2, \ldots, a_n)\) (với \(n\) là số lẻ) là giá trị thứ \(\frac{n+1}{2}\) (ở vị trí chính giữa) của dãy số sau khi dãy đã được sắp xếp theo thứ tự tăng dần. Ví dụ, trung vị của dãy \((22, 7, 97)\) là \(22\) (do dãy sau khi sắp xếp trở thành \((7, 22, 97)\); trung vị của dãy \((2, 2, 7, 1, 9, 9, 7)\) là \(7\) (do dãy sau khi sắp xếp trở thành \((1, 2, 2, 7, 7, 9, 9)\).

Input

• Dòng đầu tiên chứa bốn số nguyên \(r\), \(c\), \(h\), \(w\) \((1 \leq h \leq r \leq 3000, 1 \leq w \leq c \leq 3000)\), lần lượt là kích thước của thành phố Nồi Hạ và kích thước vùng được chọn để nâng cao chất lượng cuộc sống. Dữ liệu vào đảm bảo \(h\) và \(w\) là các số lẻ.

• Trong \(r\) dòng còn lại, dòng thứ \(i\) chứa \(c\) số nguyên \(p_{i, 1}, p_{i, 2}, \ldots, p_{i, c}\) \((1 \leq p_{i, j} \leq r \cdot c)\), trong đó \(p_{i, j}\) là thứ hạng chất lượng cuộc sống của khu \((i, j)\). Dữ liệu vào đảm bảo \(r \cdot c\) số này là đôi một phân biệt.

Output

• In ra một số nguyên duy nhất là "mức sống tiêu biểu" lớn nhất của một khu vực có dạng hình chữ nhật kích thước \(h \cdot w\).

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask \(1\) (\(9.1\) điểm): \(h = w = 1\)
• Subtask \(2\) (\(9.1\) điểm): \(h = r\) và \(w = c\)
• Subtask \(3\) (\(14.7\) điểm): \(r, c \leq 30\)
• Subtask \(4\) (\(14.7\) điểm): \(r, c \leq 100\)
• Subtask \(5\) (\(7\) điểm): \(r, c \leq 300\)
• Subtask \(6\) (\(7\) điểm): \(r, c \leq 1000\)
• Subtask \(7\) (\(8.4\) điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(70\) điểm.

Example

5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15

20