Do đã tiêu hết tiền, Bessie phải đi tìm một công việc mới. May mắn thay, ngay lúc đó có \(K\) anh nông dân đang tuyển "bò". Do công việc này chỉ cần ngồi chơi xơi nước nên có rất nhiều chú bò ứng tuyển. Có \(N\) chú bò đã ứng tuyển trước Bessie nên số thứ tự của cô là \(N + 1\) (\(1 \leq K \leq N \leq 3 \times 10^5\)).

Quá trình phỏng vấn diễn ra như sau: Tại thời điểm \(0\), anh nông dân thứ \(i\) sẽ bắt đầu phỏng vấn chú bò \(i\) \((1 \leq i \leq K)\). Khi một nông dân phỏng vấn xong một chú bò, chú bò tiếp theo sẽ ngay lập tức được phỏng vấn. Nếu có nhiều nông dân cùng phỏng vấn xong một lúc, chú bò tiếp theo có thể chọn bất kì anh nông dân để phỏng vấn mình tùy thích.

Nhờ tài do thám, Bessie đã biết trước thời gian phỏng vấn của những chú bò ở trước cô là chính xác \(t_i\) phút (\(1 \leq t_i \leq 10^9\)) vơi chú bò có thứ tự \(i\). Tuy nhiên cô không biết cách các chú bò khác chọn người phỏng vấn như thế nào (trong trường hợp có ít nhất hai anh nông dân cùng hoàn thành phỏng vấn và có thể phỏng vấn chú bò).

Để chuẩn bị tốt nhất có thể, Bessie cần biết khi nào cô sẽ được phỏng vấn và trong tất cả các kịch bản có thể xảy ra (phụ thuộc vào cách các chú bò chọn người phỏng vấn), Bessie có thể được những anh nông dân nào phỏng vấn. Nhiệm vụ của bạn là giúp cô ấy có được thông tin này.

Input:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \leq K \leq N \leq 3 \times 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(t_1, ... t_N\) (\(1 \leq t_i \leq 10^9\)).

Output:

• Dòng thứ nhất chứa một số nguyên là thời gian Bessie được phỏng vấn.
• Dòng thứ hai chứa một xâu nhị phân có độ dài \(K\), nếu Bessie có thể được phỏng vấn bởi người thứ \(i\) thì ở vị trí thứ \(i\) in ra 1, ngược lại thì in ra 0.

Scoring:

• Subtask 1: Không có hai nông dân nào kết thúc vào cùng một thời điểm.
• Subtask 2: \(N \leq 3 \times 10^3\)
• Subtask 3: Không có ràng buộc gì thêm.

6 3
3 1 4159 2 6 5

8
110

Anh nông dân John có \(N\) chú bò (\(1 \leq N \leq 10^5\)) và chúng rất thích tản bộ quanh hàng rào của trang trại. Tuy nhiên, những chú bò của John hơi hậu đậu nên mỗi khi chúng đi qua một hàng rào thì sẽ làm xước hàng rào đó, khiên John phải đi sơn lại hàng rào mỗi ngày.

Hàng rào của John bao gồm \(P\) cây cọc (\(4 \leq P \leq 2 \times 10^5\), \(P\) là số chẵn), với mỗi cây cọc là một điểm phân biệt trên trục tọa độ hai chiều \((0 \leq x,y \leq 10^9)\) được nối với các cây cọc kề nó bằng đường thẳng song song với trục tung hoặc trục hoành. Vậy nên toàn bộ hàng rào tạo thành một đa giác khép kín bao quanh cánh đồng. Các cạnh của hàng rào phải đáp ứng những điều kiện như sau: các đoạn của hàng rào chỉ có thể giao nhau ở các đầu mút (chính là các cây cọc), mỗi cây cọc chỉ có thể là đầu mút của hai đoạn hàng rào và các đoạn phải vuông góc với nhau tại điểm giao.

Mỗi chú bò có một điểm bắt đầu và điểm kết thúc chuyến đi khác nhau dọc theo hàng rào (có thể ở các cây cọc, có thể không). Chúng đi dạo dọc theo hàng rào mỗi ngày từ điểm bắt đầu đến điểm kết thúc. Có hai tuyến đường những chú bò có thể đi, vì hàng rào tạo thành một vòng tròn khép kín. Tuy nhiên do có phần lười biếng, chúng sẽ luôn chọn đi đường ngắn hơn. Lưu ý rằng với mỗi chú bò không bao giờ xảy ra trường hợp mà cả hai tuyến đường có độ dài bằng nhau.

Một chú bò sẽ làm xước cây cọc nếu nó đi qua cây cọc đó hoặc cây cọc là điểm bắt đầu hoặc kết thúc của chuyến đi. Nhiệm vụ của bạn là giúp nông dân John tính số lần mỗi cây cọc bị làm xước để tính toán xem nên sơn lại cây cọc nào tiếp theo.

Dữ liệu đảm bảo những cây cọc luôn được nối thành một hàng rào.

Input:

• Dòng đầu tiên chứa \(N\) và \(P\).
• \(P\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\)
• \(N\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\) đại diện cho điểm bắt đầu và điểm kết thúc ưa thích của mỗi chú bò.

Output:

• In ra \(P\) dòng, mỗi dòng chứa một số nguyên đại diện cho số lần bị quệt phải của mỗi cây cọc.

Scoring:

• Subtask 1: \(N, P \leq 1000\)
• Subtask 2: Tất cả các vị trí thỏa mãn \(0 \leq x, y \leq 1000\).
• Subtask 3: Không có ràng buộc gì thêm

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

1
2
2
1

2 8
1 1
1 2
0 2
0 3
0 0
0 1
2 3
2 0
1 1 2 1
1 0 1 3

1
0
0
0
1
1
1
2

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

1
1
1
1
1
0
0
0
0
0
0
0

Sau những năm tổ chức game show của mình và nhìn Bessie giành lấy giải nhất liên tục, nông dân John nhận ra đây không hề là ngẫu nhiên mà là to Bessie đã được cấy mã gen của kẻ chiến thắng. Để giải nhất không rơi vào tay Bessie thêm nữa, nông dân John đã bắt đầu công cuộc tìm kiếm gen của kẻ chiến thắng.

Nhiệm vụ của bạn là giúp anh nông dân John xác định mã gen ưng ý thông qua các bước sau: Từ xâu \(S\) có độ dài \(N\) (\(1 \leq N \leq 3000\)) là mã gen của Bessie, anh ấy chọn vài cặp số nguyên \((K,L)\) (\(1 \le L \le K \le N\)) mô tả mã gen "chiến thắng" có độ dài \(L\) và có thể thu được từ một xâu con độ dài \(K\) của xâu \(S\). Ta định nghĩa \(k-mer\) là tập hợp gồm các xâu con có độ dài \(K\) của xâu \(S\). Với mỗi phần tử của \(k-mer\), anh ấy viết ra tất cả xâu con có độ dài bằng \(L\) của nó, chọn ra xâu có thứ tự từ điển nhỏ nhất là một ứng cử viên cho mã gen "chiến thắng" (nếu tồn tại nhiều xâu con có thứ tự từ điển nhỏ nhất, chọn xâu có vị trí đầu tiên nhỏ nhất) và thêm vị trí xuất hiện lần đầu của nó trong xâu S \(p_i\) (các vị trí đánh số từ \(0\)) vào trong tập hợp \(P\).

Do quá gấp gáp, anh John vẫn chưa chọn được \(K\) và \(L\) nên anh ấy muốn bạn tìm ra số ứng cử viên cho mỗi cặp \(K\) và \(L\) anh ấy đưa ra.

Với mỗi \(v\) trong đoạn từ 1 đến \(N\), hãy giúp anh ấy tìm số cặp \(K, L\) thoả mãn \(|P| = v\).

Input:

• Dòng đầu tiên chứa \(N\), mô tả độ dài của chuỗi.
• Dòng thứ hai chứa chuỗi \(S\) (\(s_i \in A - Z\) \(\forall i \in [0, n - 1]\)).

Output:

• Đối với mỗi \(v\) từ \(1\) đến \(N\), in ra số lượng cặp \((K, L)\) với \(|P| = v\), mỗi số trên một dòng riêng biệt.

Scoring:

• Subtask \(1\): \(N \leq 100\)
• Subtask \(2\): \(N \leq 500\)
• Subtask \(3\): Không có ràng buộc gì thêm

8
AGTCAACG

11
10
5
4
2
2
1
1