Bài tập

Con tàu Mediatron đang phân tích tín hiệu dữ liệu từ một chuỗi dài các giá trị năng lượng thu được từ bề mặt hành tinh. Chuỗi này được mã hóa theo dạng: \(a_1, a_2, ..., a_n\) --- mỗi \(a_i\) biểu thị cường độ bức xạ tại thời điểm \(i\), với \(n\) là độ dài của chuỗi mã hóa.

Để xác định vùng có hiện tượng nhiễu động thời không ổn định, bộ điều khiển của con tàu Mediatron yêu cầu phải tìm ra đoạn tín hiệu liên tiếp có độ dài lớn nhất sao cho trung vị của chúng đúng lớn hơn hoặc bằng \(x\).

(Trung vị của một dãy \(b_1, b_2, ..., b_m\) là phần tử ở vị trí \(\left\lfloor \frac{m+1}{2} \right\rfloor\) sau khi sắp xếp dãy theo thứ tự không giảm.)

Ví dụ, với dãy \(a = [3, 4, 1, 2, 5]\), sau khi sắp xếp dãy này trở thành \(a = [1, 2, 3, 4, 5]\), có trung vị là giá trị \(3\). Xét dãy \(a = [4, 6, 2, 9]\), sau khi sắp xếp dãy này trở thành \(a = [2, 4, 6, 9]\), trung vị của dãy này là giá trị \(4\).

Mediatron cần bạn trợ giúp ngay để tránh quá tải hệ thống!

Input

Dòng đầu chứa hai số nguyên dương \(n\) và \(x\) --- độ dài chuỗi tín hiệu và giá trị trung vị cần tìm (\(1 \leq n \leq 2 \cdot 10^5\), \(1 \leq x \leq 10^9\)).

Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) (\(1 \leq a_i \leq 10^9\)).

Output

In ra một số nguyên duy nhất --- độ dài lớn nhất của đoạn liên tiếp của chuỗi \(a\) có trung vị lớn hơn hoặc bằng \(x\). (Nếu không tồn tại đoạn liên tiếp, in ra \(0\)).

Example

6 3
3 2 4 1 1 2

3

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm : \(n \leq 100\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm : dãy \(a\) là dãy tăng dần.
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm : \(n \leq 2000\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm : không có ràng buộc gì thêm.

Cho một dãy gồm \(n\) số nguyên dương không giảm \(a_1,\) \(a_2,\) \(a_3,\) \(…,\) \(a_n\) và một số \(k,\) Ami muốn đếm số cặp \((i,\) \(j)\) không trùng nhau mà \(a_i\) \(+\) \(a_j\) \(=\) \(k,\) lưu ý rằng \((i,\) \(j)\) và \((j,\) \(i)\) được tính là \(1\) cặp.

Input

• Dòng đầu gồm \(2\) số nguyên dương \(n\) và \(k\) \((n\) \(\leq\) \(10^6,\) \(k\) \(\leq\) \(10^9).\)

• Dòng thứ hai gồm \(n\) số nguyên dương không giảm \(a_1,\) \(a_2,\) \(a_3,\) \(…,\) \(a_n\) \((a_i\) \(\leq\) \(10^9).\)

Output

• Hãy in ra một số nguyên là kết quá của bài toán.

Example

4 6
1 1 5 5

4

6 5
1 1 1 4 5 5

3

Cho \(1\) bảng có kích thước \(M \times N\) (\(M\) hàng \(N\) cột), mỗi ô của bảng có chứa \(1\) chữ cái tiếng Anh viết thường. Ô giao của hàng \(i\) và cột \(j\) được ký hiệu là ô \((i, j)\). Coi mỗi ô của bảng là một đỉnh của đồ thị, trong đó \(2\) ô có cạnh nối với nhau khi và chỉ khi chúng có chung cạnh và chữ cái được viết trong \(2\) ô đó là giống nhau.

Yêu cầu:

Cho \(Q\) truy vấn, mỗi truy vấn gồm \(4\) số nguyên \(x_{1}, y_{1}, x_{2}, y_{2}\). \((1 \leq x_{1} \leq x_{2} \leq M, 1 \leq y_{1} \leq y_{2} \leq N)\). Nhiệm vụ của bạn là đếm số lượng thành phần liên thông có ít nhất \(1\) đỉnh thuộc hình chữ nhật có góc trái trên là ô \((x_{1}, y_{1})\) và góc phải dưới là ô \((x_{2}, y_{2})\).

Input

Dòng đầu tiên là \(2\) số nguyên dương \(M\), \(N\) \((1 \leq M, N \leq 2000)\).

\(M\) dòng tiếp theo mỗi dòng gồm \(N\) chữ cái tiếng Anh in thường mô tả \(1\) hàng của bảng.

Dòng tiếp theo là số nguyên \(Q\) \((1 \leq Q \leq 5000)\), số lượng truy vấn bạn cần trả lời.

\(Q\) dòng tiếp theo, mỗi dòng chứa \(4\) số nguyên \(x_{1}, y_{1}, x_{2}, y_{2}\) \((1 \leq x_{1} \leq x_{2} \leq M, 1 \leq y_{1} \leq y_{2} \leq N)\) mô tả truy vấn như đã nói ở trên.

Output

In ra \(Q\) đáp án cho \(Q\) truy vấn theo đúng thứ tự được cho trong input, mỗi đáp án in trên một
dòng.

Example

5 6
aabbcc
abbbcc
cbeaed
adeeed
affttz
3
1 1 5 6
2 1 4 5
3 3 5 6

12
8
6

Farmer John và em đang chăn bò ở trên trang trại của mình. Vì thấy chán, Farmer John đã tạo ra một trò chơi cho người em.

Hiện tại, trên trang trại có \(N\) cái chuồng đang trống và độc lập nhau. Vì là quản trò, Farmer John sẽ ra \(K\) lượt hiệu lệnh và có ba loại hiệu lệnh sau:

• join X Y: Kết nối chuồng thứ \(X\) và chuồng thứ \(Y\) lại với nhau.
• add X V: Thêm \(V\) \((V \leq 100)\) con bò vào chuồng thứ \(X\) và những chuồng được kết nối với chuồng \(X\). Hai chuồng \(X\) và \(Y\) được xem là kết nối với nhau nếu có đường đi giữa chúng qua một số chuồng trung gian đã kết nối trước đó.
• get X: Farmer John hỏi người em rằng chuồng thứ \(X\) có bao nhiêu con bò.

Vì em của Farmer John còn non trẻ nên đã nhờ bạn làm bài này. Bạn hãy giúp đỡ nhé.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) \((1 \leq N \leq 10^5, 1 \leq K \leq 5 \times 10^5)\) --- số chuồng và số lệnh.

• \(K\) dòng tiếp theo chứa các lệnh của Farmer John, mỗi dòng thuộc một trong ba loại:

• join X Y: Kết nối chuồng \(X\) và chuồng \(Y\).

• add X V: Thêm \(V\) con bò vào chuồng \(X\) và những chuồng kết nối với nó.
• get X: Trả về số con bò hiện có trong chuồng \(X\).

Output

• Với mỗi truy vấn dạng get X, in ra số lượng bò trong chuồng \(X\) trên một dòng riêng biệt.

Example

4 10
join 1 2
add 1 100
join 2 3
add 1 50
join 3 4
add 1 25
get 1
get 2
get 3
get 4

175
175
75
25

Scoring

• Có \(30\%\) số test có \(n, k \leq 5000\).
• Có \(30\%\) số test có mỗi truy vấn join có \(y = x + 1\).
• \(40\%\) số test còn lại không có ràng buộc gì thêm.