Bài tập

Bạn được cung cấp một bức ảnh có kích thước \(n \times m\) điểm ảnh. Mỗi điểm ảnh là màu trắng hoặc đen.

Nhiệm vụ của bạn là thay đổi càng ít điểm ảnh càng tốt để bức ảnh trở thành một mã vạch hợp lệ.

Một bức ảnh được xem là mã vạch nếu thỏa mãn hai điều kiện sau:

• Mỗi cột chỉ có một màu duy nhất (hoặc toàn trắng, hoặc toàn đen).
• Khi nhóm các cột liền kề có cùng màu lại, kích thước của mỗi nhóm phải nằm trong đoạn \([x, y]\).

Mục tiêu: Tìm số điểm ảnh ít nhất cần tô lại để bức ảnh trở thành mã vạch hợp lệ.

\InputFile

• Dòng đầu tiên chứa bốn số nguyên \(n, m, x, y\) (\(1 \le n \times m \le 10^6, x \le y \le 10^6\)).
• Tiếp theo là \(n\) dòng, mỗi dòng gồm đúng \(m\) ký tự, mô tả bức ảnh ban đầu.
• Mỗi ký tự là '.' (điểm trắng) hoặc # (điểm đen).

\OutputFile

In ra một số nguyên duy nhất --- số điểm ảnh ít nhất cần tô lại. Đảm bảo rằng luôn tồn tại cách làm thỏa mãn yêu cầu.

\Scoring

• Subtask 1 (22 điểm): \(n \cdot m \le 20\)
• Subtask 2 (18 điểm): Tất cả các ô đều có màu trắng.
• Subtask 3 (30 điểm): \(m \le 1000\)
• Subtask 4 (30 điểm): Không có giới hạn gì thêm

Example

6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..

11

2 5 1 1
#####
.....

5

Có $ N $ video clip với thời lượng $ a_{i} $ giây. Tìm số video liên tiếp ít nhất có tổng thời lượng $ \geq S $. Nếu không tồn tại in ra -1.

Input

File VIDEO.INP gồm:

• Dòng 1: $ N, S $ \(( N \leq 10^6, S \leq 2 \times 10^9 )\)
• Dòng 2: $ N $ số $ a_1, a_2, ..., a_N $ \(( 1 \leq a_i \leq 10^9 )\)

Output

File VIDEO.OUT chứa số video tìm được.

Example

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

2

Scoring

• \(40\%\) số test \(( N \leq 100 )\) chiếm \(40\%\) điểm
• \(30\%\) số test \(( 100 < N \leq 1000 )\) chiếm \(30\%\) điểm
• \(30\%\) số test \(( 1000 < N \leq 10^6 )\) chiếm \(30\%\) điểm

Bạn có một dãy số nguyên gồm \(n\) phần tử. Trải qua thời gian, dãy số này liên tục thay đổi và bạn cần xử lý một loạt các truy vấn được đưa ra.

Có tổng cộng \(q\) truy vấn, mỗi truy vấn là một trong hai loại sau:

• Loại 1: 1 $k$ $u$ --- Cập nhật giá trị phần tử ở vị trí \(k\) thành \(u\).
• Loại 2: 2 $a$ $b$ --- Trong tất cả các đoạn con bắt đầu tại \(a\) và kết thúc tại \(i\) với \(a \le i \le b\), hãy tìm đoạn con có tổng lớn nhất.

Cụ thể hơn, với truy vấn loại 2, bạn cần xét các đoạn \([a, a], [a, a+1], \dots, [a, b]\) và chọn ra đoạn có tổng lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)) --- độ dài ban đầu của dãy và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \dots, x_n\) (\(-10^9 \le x_i \le 10^9\)) --- các phần tử ban đầu của dãy.

• \(q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn theo một trong hai dạng:

• 1 $k$ $u$ --- cập nhật \(x_k \leftarrow u\), với \(1 \le k \le n\), \(-10^9 \le u \le 10^9\).

• 2 $a$ $b$ --- truy vấn tổng lớn nhất của một đoạn con bắt đầu tại \(a\) và kết thúc tại một vị trí bất kỳ trong đoạn \([a, b]\), với \(1 \le a \le b \le n\).

Output

Với mỗi truy vấn loại 2, in ra một dòng chứa kết quả tương ứng --- tổng lớn nhất của đoạn con được yêu cầu.

Example

8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4

5
2
0

Trong một lễ hội điện ảnh hoành tráng, một danh sách dài gồm \(n\) bộ phim đã được công bố. Bạn, một người yêu điện ảnh cuồng nhiệt, muốn xem càng nhiều bộ phim càng tốt. Tuy nhiên, bạn chỉ có thể xem trọn vẹn một bộ phim và không thể xem hai bộ phim cùng lúc. Bạn phải lên một lịch trình xem phim thông minh để tối đa hóa số lượng phim có thể thưởng thức.

Bạn được cung cấp danh sách \(n\) bộ phim. Đối với mỗi bộ phim, bạn biết chính xác thời gian bắt đầu (\(a_i\)) và thời gian kết thúc (\(b_i\)) của nó. Bạn chỉ có thể xem một bộ phim tại một thời điểm, nghĩa là nếu bạn xem một bộ phim kết thúc vào lúc \(t\), bạn chỉ có thể bắt đầu xem bộ phim tiếp theo vào thời điểm \(t\) hoặc muộn hơn.

Với danh sách các bộ phim đã cho, hãy xác định số lượng bộ phim tối đa bạn có thể xem trọn vẹn.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)), là tổng số bộ phim.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) (\(1 \le a < b \le 10^9\)), lần lượt là thời gian bắt đầu và kết thúc của một bộ phim.

Output

In ra một số nguyên duy nhất là số lượng phim tối đa có thể xem.

Example

3
3 5
4 9
5 8

2