Bài tập

Cho hai dãy số nguyên dương \(A=\left(a_{1}, a_{2}, \ldots, a_{n}\right)\) và \(B=\left(b_{1}, b_{2}, \ldots, b_{n}\right)\) là hai hoán vị của \(1,2, \ldots, n\). Thực hiện lần lượt \(q\) thao tác, mỗi thao tác được mô tả bằng hai chỉ số \(i, j\ (1 \leq\) \(i, j \leq n)\) gồm hai công việc sau:

• Thực hiện tráo đổi hai phần tử thứ \(i\) và thứ \(j\) trong dãy \(B\).
• Tìm một dãy là hoán vị vòng của dãy \(A\) mà số lượng vị trí tương ứng khớp với dãy \(B\) là nhiều nhất, sau đó đưa ra số lượng vị trí khớp nhiều nhất tìm được. Cụ thể, tìm số nguyên không âm \(k\ (0 \leq k \leq n-1)\) để dãy \(\left(c_{1}, c_{2}, \ldots, c_{n}\right)=\left(a_{k+1}, a_{k+2}, \ldots, a_{n}, a_{1}, a_{2} \ldots, a_{k}\right)\) có số lượng vị trí \(i\ (1 \leq i \leq n)\) mà \(c_{i}=b_{i}\) là nhiều nhất.

Yêu cầu: Cho hai dãy \(A, B\) và \(q\) thao tác, với mỗi thao tác đưa ra số lượng vị trí khớp nhiều nhất tìm được.

Input

• Dòng đầu chứa hai số nguyên dương \(n, q\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) là một hoán vị của \(1,2, \ldots, n\).
• Dòng thứ ba chứa \(n\) số nguyên dương \(b_{1}, b_{2}, \ldots, b_{n}\) là một hoán vị của \(1,2, \ldots, n\).

Output

• Gồm \(q\) dòng, mỗi dòng là số lượng vị trí khớp nhiều nhất tìm được tương ứng với thao tác trong dữ liệu vào.

Example

3 2
1 2 3
1 2 3
1 3
2 3

1
3

Scoring

• Có \(40 \%\) số test của bài có \(n \leq 100 ; q \leq 100\).
• Có \(30 \%\) số test khác của bài có \(n \leq 10^{5} ; q \leq 100\).
• Có \(30 \%\) số test còn lại của bài có \(n \leq 10^{5} ; q \leq 10^{5}\).

Nam tham gia trò chơi "Thám hiểm mê cung". Mê cung có dạng ma trận vuông gồm \(n \times n\) phòng, phòng ở hàng \(i\) và cột \(j\) được gọi là phòng \((i,j)\). Tại phòng \((i,j)\) có giấu phần thưởng có giá trị \(a_{ij}\). Khi tiến vào mê cung, người chơi sẽ được đưa đến một phòng ngẫu nhiên. Người chơi sau khi tìm ra được phần thưởng mới có thể di chuyển đến các phòng kề cạnh. Trong mê cung, có một phòng thoát hiểm. Sau khi tìm ra được phần thưởng đã giấu ở phòng thoát hiểm, người chơi sẽ thoát khỏi mê cung. Để hạn chế trả thưởng cho người chơi, hệ thống quy định sau khi thoát khỏi mê cung, người chơi nhận một phần thưởng có giá trị nhỏ nhất trong tất cả các phần thưởng đã tìm được.

Yêu cầu: Cho \(q\) truy vấn, với mỗi truy vấn cho biết phòng xuất phát \((x, y)\) và phòng thoát hiểm \((u, v)\), hãy lập trình tìm giá trị phần thưởng lớn nhất mà Nam nhận được.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, q\) (\(1 \le n \le 500\); \(1 \le q \le 4 \times 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên \(a_{ij}\) (\(1 \le a_{ij} \le 10^5\)).
• \(q\) dòng cuối cùng, mỗi dòng chứa bốn số nguyên \(x, y, u, v\) (\(1 \le x, y, u, v \le n\)), dữ liệu đảm bảo \((x + u)^2 + (y + v)^2 > 4xu + 4yv\).
• Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Gồm \(q\) dòng, mỗi dòng in ra giá trị phần thưởng lớn nhất tương ứng với mỗi truy vấn.

Example

5 2
8 4 1 2 4
2 3 5 6 5
1 2 1 5 2
9 5 8 4 7
4 5 1 3 9
1 1 4 1
1 4 3 2

3
2

Scoring

• Có 20% số điểm tương ứng với \(n \le 100\) và \(q \le 100\);
• Có 20% số điểm tương ứng với \(n \le 100\) và \(q \le 2000\);
• Có 40% số điểm tương ứng với \(n \le 300\) và \(q \le 10^5\);
• Có 20% số điểm tương ứng với \(n \le 500\) và \(q \le 4 \times 10^5\).

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