Series ℍ𝔾𝔹ℂ𝕡𝕡_'s - Tìm 𝓒𝓸𝓭𝓮𝓻 Tài năng nhất LQDOJ #02

Một hôm, p2o2HuaGiaBao thấy túi kẹo còn quá nhiều và cậu ấy rất ghét ăn kẹo. Nhưng, dinh rất thích ăn loại kẹo đó. Tuy nhiên, p2o2HuaGiaBao không muốn tặng kẹo cho cậu ấy quá nhiều. Chính vì vậy, cậu ấy đã nghĩ ra một cách chia đơn giản như sau: Trong túi kẹo, còn \(n\) túi kẹo với độ ngọt lần lượt là: \(w_1,w_2,...,w_n\) (Lưu ý: Độ ngọt không được sắp xếp hay theo một quy luật hay thứ tự nào cả)

• p2o2HuaGiaBao sẽ tặng cho anh ta \(2\) cái kẹo có độ ngọt lớn nhất và nhỏ nhất (Gọi là \(a\) và \(b\)) với điều kiện \(a+b\le K\)
• Trái với điều này, cậu ta chỉ giữ lại viên kẹo nhỏ hơn đang xét và sẽ ăn viên kẹo có độ ngọt lớn hơn.
  Chú ý: Mỗi lần cần bắt buộc phải xét \(2\) viên kẹo.

p2o2HuaGiaBao tặng kẹo hay ăn kẹo cho đến khi không còn cách chia nào thỏa mãn.

Nhiệm vụ của các bạn là hãy giúp p2o2HuaGiaBao đếm số lượng viên mà anh ta tặng cho dinh.

Input

• Dòng \(1\) gồm hai số nguyên dương \(n,k\) (\(n\le 10^5\), \(1\le k \le 10^9\))
• Dòng \(2\) gồm \(n\) số nguyên dương \(w_1,w_2,...,w_n\) (\(w_i\le 10^9\) với \(1\le i \le n\))

Output

• Gồm một dòng duy nhất là một số tự nhiên chính là kết quả của bài toán trên.

Example

7 10
1 2 3 7 8 9 10

6

Tại Thành phố Hồ Chí Minh, nơi phát triển kinh tế tốt nhất tại đất nước Việt Nam. Mỗi ngày, các coder phải tính toán như sau: Có \(N\) nhà máy điện đứng thẳng hàng, mỗi nhà máy \(i\) ban đầu sản xuất \(a_i\) megawatt (MW) điện. Chính quyền thành phố yêu cầu bạn xử lý \(q\) truy vấn thuộc \(3\) loại:

1. Truy vấn cập nhật đoạn: Tăng công suất của tất cả nhà máy từ vị trí \(l\) đến \(r\) thêm \(v\) MW.
2. Truy vấn cập nhật điểm: Thay đổi công suất của nhà máy tại vị trí \(pos\) thành \(v\) MW.
3. Truy vấn câu hỏi: Tìm nhà máy có công suất nhỏ nhất trong đoạn \([l, r]\).

Vì p2o2HuaGiaBao dẫn các học sinh có tiềm năng đến nơi làm việc của các coder đó. Anh ta thử thách các học sinh tính toán bài toán trên. Để thể hiện điều đó, các bạn cần AC bài tập này để tuyển chọn vào Đội Tuyển Học Sinh Giỏi HGBCpp_.

Input

• Dòng đầu tiên chứa \(2\) số nguyên dương \(1\le N, q \le 10^5\). (Với \(N\) là số lượng nhà máy, \(q\) là số lượng truy vấn).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,a_3,...,a_n\) (\(a_i \le 10^9\)) để biểu diễn giá trị công suất của nhà máy thứ \(i\).
• \(q\) dòng tiếp theo biểu diễn mỗi truy vấn như trên.
  • Đối với truy vấn loại \(1\): \(1\le l,r\le N,\) \(v\le 10^9\)
  • Đối với truy vấn loại \(2\): \(1\le pos\le N,\) \(v\le 10^9\)
  • Đối với truy vấn loại \(3\): \(1\le l,r\le N\)

Output

• In ra các kết quả trong truy vấn loại \(3\).

Example

5 4
3 3 5 7 9
1 2 4 2
2 3 10
3 1 5
3 2 4

3
5

Sau ngày đầu tiên của p2o2HuaGiaBao với chuyến đi thích thú. Vào đêm, anh ấy nhìn thấy biển báo nhắc nhở trong khách sạn và nhận thấy điều đặc biệt và viết nên bài toán như sau: Cho hai xâu ký tự \(S\) và \(T\) có cùng độ dài \(N\) chỉ gồm các chữ cái latin tiếng Anh viết thường. Với mỗi vị trí \(i\) (\(1 \le i \le N\)), gọi \(P(S, i)\) là tiền tố độ dài \(i\) của xâu \(S\). Hãy tìm giá trị \(L\) lớn nhất sao cho:

1. \(1 \le L \le N\).
2. \(P(S, L)\) khi viết ngược lại sẽ khớp hoàn toàn với một xâu con độ dài \(L\) nào đó của \(T\).

Nói cách khác, bạn cần tìm số \(L\) lớn nhất sao cho tồn tại ít nhất một chỉ số \(j\) (\(1 \le j \le N - L + 1\)) thỏa mãn: \(S[1 \dots L]\) đảo ngược bằng với \(T[j \dots j+L-1]\).

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa xâu \(S\).
• Dòng thứ ba chứa xâu \(T\).

Output

• Một số nguyên duy nhất là giá trị \(L\) lớn nhất tìm được. Nếu không có giá trị \(L\) nào thỏa mãn, in ra 0.

Example

7
abacaba
baabcde

2

5
abcde
edcba

5

Trong một ngày đêm u ám, p2o2HuaGiaBao bị bắt cóc vào khu tự trị nơi tồn tại khu lừa đảo lớn nhất Cam-pu-chia. Sếp bắt cóc anh ta vì thấy anh ấy có tiềm năng để lừa người nên mới bắt p2o2HuaGiaBao.
Bổng dưng, sếp maiphucthinhpika34 hỏi anh ấy đúng một câu:

Tôi cho bạn một trong 2 lựa chọn: Một là giải bài toán hóc búa này để được thả tự do vì chính sếp cũng chả biết giải (._.). Hai là sẽ giữ lại để làm việc cho hắn và sẽ cho ăn quả chích điện nếu không lừa được \(100\) người mỗi ngày.

Vì không muốn lừa chính người dân của mình nên p2o2HuaGiaBao chọn phương án số \(1\), vì bài toán dưới đây quá khó, mà không AC thì đẩy sang phương án số \(2\) nên đành nhanh trí nhờ sự trợ giúp bên ngoài. Các bạn hãy mau nhanh chóng giúp cậu ấy thoát khỏi ổ lừa đảo nhất quả đất Cam-pu-chia nhé!

Một dãy số (\(x_1,x_2,\ldots,x_m\)) được gọi là Teto nếu với mọi (\(1 \le i \le m-2\)): \(x_i \oplus x_{i+1} < x_{i+1} \oplus x_{i+2}\)

trong đó (\(\oplus\)) là phép \(\text{XOR bit}\).

Mọi dãy có độ dài \(1\) hoặc \(2\) đều là dãy Teto. Cho \(n\) đoạn \([l,r]\) (có thể trùng nhau).
Gọi \(P\) là tập hợp tất cả các số nguyên xuất hiện trong ít nhất một đoạn. Tạo dãy \(A\) gồm các phần tử của \(P\), sắp xếp tăng dần.

Cần đếm số lượng dãy con không rỗng của \(A\) là dãy Teto.
Kết quả lấy \(\text{mod}\) \(998244353\)
Sau đó có \(q\) thao tác động:

• 1 l r: thêm đoạn \([l,r]\).
• 2 l r: xóa một lần xuất hiện của đoạn \([l,r]\).

Sau trạng thái ban đầu và sau mỗi truy vấn, phải in ra số dãy con Teto hiện tại.

Input

• Dòng đầu chứa hai số nguyên \(n, q\) (\(1\le n\le 10^5\), \(0\le q\le 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_i, r_i\) mô tả một đoạn ban đầu \([l_i,r_i]\) (\(1\le l_i < r_i\le 10^9\)).
• \(q\) dòng tiếp theo mô tả các thao tác. (Lưu ý: Các dữ liệu trong mỗi truy vấn đều thỏa mãn tính hợp lí và yêu cầu đề bài)

Output

• In ra \(q+1\) dòng.
• Dòng đầu tiên là đáp án của trạng thái ban đầu.
• \(q\) tiếp theo là đáp án sau khi thực hiện xong thao tác tương ứng.

Example

2 4
6 7
10 10
1 6 7
2 6 7
1 9 9
2 6 7

7
7
7
12
3

3 3
10 12
15 15
100 101
1 12 13
1 14 14
2 10 12

39
60
84
39