Bài tập

Bước vào cánh cửa đại học, có lẽ thứ ám ảnh nhất đối với Quân hiện tại là môn Giải tích. Cuộc sống Giải tích không hề dễ dàng, cuộc sống như đóng cửa tất cả các con đường của Quân. Tuy nhiên, môn Đại số tuyến tính lại mở ra cho Quân những ý tưởng mới.

Mặc dù không có kiến thức về TÍNH GIỚI HẠN LIM LOGARIT ĐẠO HÀM NGUYÊN HÀM VI PHÂN TÍCH PHÂN TÍCH PHÂN BẤT ĐỊNH TÍCH PHÂN SUY RỘNG ĐẠO HÀM CẤP CAO ĐẠO HÀM NHIỀU BIẾN NGUYÊN HÀM VÔ CÙNG LỚN VÔ CÙNG BÉ CHUỖI SỐ L... nhưng Quân lại có khả năng tốt ở môn Đại số tuyến tính. Vì thế, Quân đã đăng ký đi thi sơ loại Olympic Toán học Sinh viên của trường Đại học Công nghệ Thông tin tổ chức để thử sức ("mặc dù lý do chính là do thầy dạy Giải tích bảo nếu Quân đi thi thì sẽ được cộng "\(1\)" điểm quá trình).
Bài toán hôm nay ra khá khó, có một bài liên quan tới các đoạn thẳng, nhưng Quân không giải được, Quân phải mở máy lên code để dễ hình dung hơn thay vì trình bày ra giấy, bài toán như sau:

Xét \(n\) đoạn thẳng trên trục số, đoạn thẳng thứ \(i\) là đoạn \([l_{i}, r_{i}]\). Hai đoạn thẳng gọi là "giao nhau" khi và chỉ khi tồn tại một số thực \(x\) sao cho \(l_{i} \leq x \leq r_{i}\) và \(l_{j} \leq x \leq r_{j}\). Đếm số cách tô màu các đoạn thẳng sao cho các đoạn thẳng giao nhau có màu khác nhau. Vì kết quả có thể rất lớn, in ra kết quả chia lấy dư cho \(998244353\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n \leq 5 \times 10^5\), \(1 \leq k \leq 10^9\)) --- số lượng đoạn thẳng và số lượng màu.
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l_i\) và \(r_i\) (\(1 \leq l_i \leq r_i \leq 10^9\)) --- điểm đầu và điểm cuối của đoạn thẳng thứ \(i\).

Output

• Với mỗi bộ test, in ra một dòng chứa một số nguyên --- kết quả là số cách để tô màu các đoạn. Vì kết quả có thể rất lớn, hãy in ra kết quả modulo \(998244353\).

Example

4 5
1 3
2 5
4 10
20 50

400

Scoring

• \(20\%\) số test có \(n \leq 10\).
• \(10\%\) số test có \(k = 1, n \leq 1000\).
• \(10\%\) số test có \(k = 1, n \leq 5 \times 10^5\).
• \(30\%\) số test có \(n \leq 5000, r_{i} \leq 5000\).
• \(30\%\) số test còn lại không có ràng buộc gì thêm.

Tí đang chơi trò ghép nhà từ những que tính. Phần căn nhà đã được ghép xong, chỉ còn thiếu một cửa sổ hình chữ nhật. Hiện tại, Tí còn dư \(n\) que tính, các que tính được đánh số thứ tự từ \(1\) tới \(n\), que thứ \(i\) có độ dài \(a_i\) (đơn vị đo chiều dài). Tí muốn ghép được cửa sổ càng to càng tốt. Một cửa sổ sẽ được ghép từ 4 que tính.

*Không bẻ gãy hay chắp nối để thay đổi chiều dài que tính và hình vuông cũng được xem là hình chữ nhật.*

Input

Vào từ file CUASO.INP:

• Dòng đầu chứa số nguyên dương \(n\) \((1 \leq n \leq 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_i\) \((1 \leq a_i \leq 10^6;\ 1 \leq i \leq n)\).

Output

Ghi ra file CUASO.OUT số nguyên duy nhất là chu vi lớn nhất của cửa sổ có thể ghép được. Nếu không thể ghép được thì ghi \(-1\).

Example

7
3 8 4 3 8 1 1

22

5
4 9 1 9 3

-1

Scoring

• \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n \leq 50\).
• \(40\%\) số test tương ứng với \(40\%\) số điểm có \(50 < n \leq 1000\).
• \(30\%\) số test còn lại tương ứng với \(30\%\) số điểm không có ràng buộc gì thêm.

Trong khu vườn của mình, Hùng có \(n\) chiếc thùng chứa nước được đặt thẳng hàng, đánh số từ \(1\) đến \(n\). Mỗi thùng đều là hình trụ có đáy bằng nhau. Thùng thứ \(i\) có sức chứa là \(b_i\) và hiện đang chứa \(a_i\) lít nước.

Thời tiết ở đây thật thất thường. Mỗi cơn mưa được đặc trưng bởi ba số nguyên: \(L, H, d\). Cơn mưa này sẽ trút nước trong phạm vi từ thùng \(L\) đến thùng \(H\), mỗi thùng nhận thêm \(d\) lít nước. Lượng nước sẽ tràn ra ngoài nếu vượt quá sức chứa của thùng.

Sau mỗi cơn mưa, Hùng sẽ ra kiểm tra tình hình. Cậu sẽ tính tổng lượng nước trong các thùng từ \(L\) đến \(H\) để xem có đủ nước tưới cây hay không.

Ban đầu, bạn được cho thông tin về \(n\) thùng nước. Sau đó, bạn sẽ nhận được một loạt các truy vấn. Mỗi truy vấn có hai loại:

• Loại \(0\) \(L\) \(H\) \(d\) : Một cơn mưa mới xuất hiện, trút nước vào các thùng từ \(L\) đến \(H\).
• Loại \(1\) \(L\) \(H\) : Hùng ra kiểm tra và bạn cần tính tổng lượng nước hiện có trong các thùng từ \(L\) đến \(H\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 10^5\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\) (\(0 \le a_i \le b_i \le 10^9\)).
• Dòng tiếp theo chứa số nguyên \(T\) (\(1 \le T \le 10^5\)), là số lượng truy vấn.
• \(T\) dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai dạng trên.

Output

• Với mỗi truy vấn dạng "\(1\) \(L\) \(H\)", in ra trên một dòng tổng lượng nước trong các thùng từ \(L\) đến \(H\).

Example

5
1 3
2 4
3 5
4 6
5 7
5
0 1 3 1
0 3 5 2
1 1 5
1 3 3
1 1 2

23
5
5

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm : \(n, T \leq 5000\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm : \(L = 1, H = n\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm : \(a_i = 0\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm còn lại không có ràng buộc gì thêm.

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}\).