Bài tập

Mọi người đều đã quen thuộc với bài toán tìm LIS (Longest Increasing Subsequence) của một dãy số. Tuy nhiên, Ami lại có một sở thích hơi khác. Thay vì nghiên cứu một dãy số, cậu chỉ nhìn vào các chữ số của một số nguyên.

Ami định nghĩa LIDS (Longest Increasing Digit Subsequence) của một số nguyên là độ dài của dãy con tăng dài nhất được tạo bởi các chữ số của số đó.

Ví dụ:

• LIDS của \(1234\) có độ dài \(4\).
• LIDS của \(12234\) có độ dài \(4\).
• LIDS của \(456123\) có độ dài \(3\).

Một số ví dụ về dãy chữ số tăng hợp lệ là:

Trong khi đó,

không phải là dãy tăng.

Cho hai số nguyên \(L\) và \(R\).

Yêu cầu. Trong tất cả các số nguyên thuộc đoạn \([L,R]\):

• Tìm giá trị lớn nhất của LIDS.
• Đếm số cách tạo ra LIDS lớn nhất đó.

Hai cách được coi là khác nhau nếu:

• Hai dãy chữ số thu được khác nhau; hoặc
• Chúng được lấy từ các vị trí khác nhau trong cùng một số.

\InputFile

Dòng đầu chứa số nguyên \(T\) \((1 \le T \le 10^4)\) là số lượng bộ dữ liệu.

Mỗi bộ dữ liệu gồm một dòng chứa hai số nguyên

thỏa mãn

\OutputFile

Với mỗi bộ dữ liệu, in ra một dòng theo định dạng

\begincenter
Case x: a b
\endcenter

trong đó:

• \(x\) là số thứ tự bộ dữ liệu (bắt đầu từ \(1\));
• \(a\) là độ dài lớn nhất của LIDS trong đoạn;
• \(b\) là số cách tạo ra LIDS có độ dài lớn nhất.

\Examples

\beginexample
\exmp
2
111 114
15432 15432

Case 1: 2 6
Case 2: 2 4

\endexample

\Note

Ở bộ dữ liệu thứ nhất:

• LIDS của \(111\) có độ dài \(1\).
• LIDS của \(112\), \(113\) và \(114\) đều có độ dài \(2\).

Do đó, độ dài LIDS lớn nhất là \(2\) và có tổng cộng \(6\) cách tạo ra các dãy con tăng có độ dài này.

Ở bộ dữ liệu thứ hai, số \(15432\) có LIDS bằng \(2\). Có bốn cách đạt được giá trị này:

\endproblem

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

Một dãy gồm \(n\) số nguyên \(a_1, a_2,..., a_n\) được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả \((n-1)\) khoảng trắng. Người ta muốn đặt \(k\) dấu cộng và \((n-1-k)\) dấu trừ vào \((n-1)\) khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất.

Ví dụ, với dãy gồm 5 số nguyên \(28, 9, 5, 1, 69\) và \(k = 2\) thì cách đặt \(28+9-5-1+69\) là biểu thức có giá trị lớn nhất.

Yêu cầu: Cho dãy gồm n số nguyên \(a_1, a_2,..., a_n\) và số nguyên dương \(k\), hãy tìm cách đặt \(k\) dấu cộng và \((n-1-k)\) dấu trừ vào \((n-1)\) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(n, k \; (k \lt n)\);

• Dòng thứ hai chứa n số nguyên \(a_1, a_2,\ldots, a_n\) (\(a_n \le 10^6\))

Output

• Một số nguyên là giá trị của biểu thức đạt được.

Example

5 2
28 9 5 1 69

100

Scoring

\begin itemize

• Có \(50\%\) số test ứng với \(50\%\) số điểm có \(n ≤ 10^5\) và \(k = 1\);

• Có \(50\%\) số test còn lại ứng với \(50\%\) số điểm có \(n ≤ 10^5\);

\end itemize