Chọn ĐT HSG QG Đà Nẵng 2024 Ngày 1

Cho một xâu \(S\) có độ dài \(n\) chỉ gồm các ký tự số. Hãy tìm cách cắt xâu \(S\) thành các đoạn liên tiếp nhau khác rỗng để tạo thành một dãy số (trong đó mỗi đoạn con tương ứng một số và số này có thể chứa số 0 ở đầu) sao cho độ dài của dãy con không giảm của dãy số đó là lớn nhất.

• Đoạn con liên tiếp là đoạn con thu được bằng cách xoá đi một số phần tử ở đầu và cuối xâu (có thể là không xoá phần tử nào).
• Dãy con tăng không giảm có độ dài lớn nhất là khi ta xoá đi một số phần tử của dãy ban đầu thì phần thu được sẽ là một dãy không giảm và có độ dài lớn nhất.

Input

• Dòng đầu chứa số nguyên dương \(n\) (\(1 \le n \le 2 \cdot 10^3\)).
• Dòng tiếp theo chứa xâu \(S\) gồm \(n\) kí tự.

Output

• Ghi một số nguyên duy nhất là độ dài dãy con không giảm dài nhất.

Example

8
13220131

4

Scoring

• Subtask \(1\) (\(10\%\) số test): xâu \(S\) chỉ gồm các ký tự 0 và 1.
• Subtask \(2\) (\(20\%\) số test): \(1 \le n \le 20\).
• Subtask \(3\) (\(20\%\) số test): \(1 \le n \le 200\).
• Subtask \(4\) (\(50\%\) số test): Không có ràng buộc gì thêm.

Vào ngày sinh nhật của Nobita, Doraemon quyết định tặng cho cậu một trò chơi thực tế ảo và cậu rất thích với trò chơi này. Trong trò chơi Nobita sẽ được hoá thân thành một siêu anh hùng giải cứu trái đất. Có \(n\) chiếc UFO (Unidentified Flying Object - vật thể bay không xác định) đang lần lượt tấn công vào trái đất theo thứ tự từ \(1 \dots n\), và nhiệm vụ của Nobita là tiêu diệt toàn bộ các UFO trên để đảm bảo sự bình yên của trái đất. Nobita phải tiêu diệt lần lượt các UFO vì nếu nó đã vượt qua cậu ấy thì cậu ấy sẽ bị mất bình tĩnh và không bắn được nữa.

Trò chơi có \(t\) màn và phải chơi lần lượt theo thứ tự tăng dần. Ban đầu Nobita được trang bị duy nhất một khẩu súng thường, loại này có tầm ngắm bằng \(1\) với không giới hạn số lần sử dụng và mỗi lần bắn tốn chi phí là \(a\).

Trước mỗi màn thứ \(i\) (\(1 \le i \le t\)) sẽ có thêm một khẩu súng đặc biệt có tầm ngắm \(d_i\) và tốn chi phí \(c_i\) xuất hiện ngay sau khi UFO thứ \(u_i\) được tiêu diệt, và nếu không dùng ngay thì nó sẽ biến mất khi UFO thứ \(u_i+1\) được tiêu diệt.

Giả sử đã tiêu diệt được \(i\) UFO và sử dụng một khẩu súng có tầm ngắm \(X\) thì nó có thể tiêu diệt tất cả các UFO từ \(i + 1\) đến vị trí \(j\) bất kì sao cho \(j - i \le X\). Nobita là một tay súng thiện xạ nên tỉ lệ bắn trúng của cậu ta là \(100\%\). Việc tiêu diệt hết các UFO đối với Nobita là quá đơn giản, tuy nhiên cậu khá lười biếng nên cậu có \(q\) câu hỏi sau:

Với câu hỏi thứ \(i\) (\(1 \le i \le q\)), nếu cậu đã chơi được tới màn thứ \(x_i\) và đã tiêu diệt được \(y_i\) UFO thì chi phí thấp nhất để cậu tiêu diệt \(z_i\) UFO tiếp theo là bao nhiêu.

Nobita tính toán không nhanh nên cậu ấy quyết định nhờ các bạn giúp đỡ.

Input

• Từ file văn bản CHIENDAU.INP:
  • Dòng đầu: \(n, a, t, q\) (\(1 \le n, t, q \le 5 \cdot 10^4\), \(1 \le a \le 10^9\)).
  • \(t\) dòng tiếp theo là các khẩu súng đặc biệt sẽ được thêm vào: Với màn thứ \(i\) có dạng \(u_i, d_i, c_i\) (\(1 \le u_i \le n\), \(1 \le d_i \le 5\), \(1 \le c_i \le 10^9\)).
  • Tiếp theo \(q\) câu hỏi: Câu hỏi thứ \(i\) có dạng \(x_i, y_i, z_i\) (\(1 \le x_i \le t\), \(0 \le y_i \le n\), \(0 \le z_i \le n - y_i\)).

Output

• Ghi ra file văn bản CHIENDAU.OUT là kết quả bài toán.

Example

8 10 5 4
3 4 4
1 5 2
5 3 1
2 5 3
6 2 3
5 0 8
5 5 3
3 2 5
4 3 4

13
1
14
4

Ràng buộc

• Subtask 1 (\(50\%\) số test đầu tiên): \(1 \le n, t, q \le 2000\).
• Subtask 2 (\(20\%\) số test tiếp theo): \(x_i = t\) với mọi \(1 \le i \le q\).
• Subtask 3 (\(30\%\) số test còn lại): Không có ràng buộc gì thêm.

ông có ràng buộc gì thêm.

Nobita đang ngồi làm bài tập ở nhà, nhưng được một lát cậu ta lại chán chỉ muốn đi ngủ. Doraemon thấy vậy liền nảy ra một ý tưởng để giúp Nobita phấn chấn hơn - đó là đưa Nobita đến vùng đất táo đỏ thần kỳ về hạnh phúc. Nghe xong, Nobita liền bật dậy và cùng Doraemon bước vào cánh cửa thần kỳ để đến với vùng đất táo đỏ kia. Khi đến nơi, Nobita choáng ngợp với một cánh đồng mênh mông chỉ toàn táo màu đỏ. Doraemon dẫn Nobita đến trước một cây táo khổng lồ và nói với Nobita rằng đây là cây táo tình yêu; nếu ăn được một cặp táo hợp nhau trên cây thì tình cảm giữa hai người ăn táo sẽ trở nên khăng khít hơn. Nghe đến đây Nobita liền sáng mắt lên và hỏi Doraemon làm sao để hái được cặp táo hợp nhau đó, vì cậu rất muốn đem cặp táo đó tặng ngay cho Shizuka.

Để dễ tưởng tượng, cây táo được biểu diễn dưới dạng một đồ thị dạng cây với mỗi đỉnh đại diện cho một quả táo, cây gồm \(n\) đỉnh được đánh số từ \(1, 2, 3, \dots, n\) và \(n - 1\) cạnh. Mỗi quả của cây đều có một chỉ số hạnh phúc, tương ứng \(a_1, a_2, a_3, \dots, a_n\) lần lượt là chỉ số hạnh phúc của các đỉnh từ \(1\) đến \(n\).

Ta định nghĩa một số \(X\) được gọi là số siêu hạnh phúc bậc \(k\) nếu số đó có căn bậc \(k\) là một số tự nhiên (hay nói cách khác: số đó có thể biểu diễn dưới dạng \(y^k\) với \(y\) là một số tự nhiên).

Ví dụ:

• \(k = 2\): Các số siêu hạnh phúc có thể là \(4\) (vì \(2^2 = 4\)), \(81\) (vì \(9^2 = 81\)).
• \(k = 3\): Các số siêu hạnh phúc có thể là \(8\) (vì \(2^3 = 8\)), \(8000\) (vì \(20^3 = 8000\)).

Ta gọi một cặp quả táo là hợp nhau nếu tích của \(2\) chỉ số hạnh phúc của \(2\) quả táo đó là số siêu hạnh phúc bậc \(k\).

Nobita quyết định sử dụng tài năng bắn súng của mình, nhưng cậu chỉ có khả năng bắn rơi tất cả các trái táo nằm trên một đường đi đơn bất kì trên cây. Cậu có \(q\) câu hỏi như sau:

Nobita lo lắng nên cậu ấy nhờ các bạn giải đáp các câu hỏi để có thể chọn ra được cặp táo phù hợp nhất dành tặng cho Shizuka.

Input

• Dòng đầu chứa ba số nguyên: \(n, k, q\) (\(1 \le n, q \le 10^5\), \(1 \le k \le 5\)).
• Dòng tiếp theo là dãy số nguyên dương \(a_1, a_2, a_3, \dots, a_n\) (\(1 \le a_i \le 10^6\)).
• \(n - 1\) dòng tiếp theo lần lượt là các cạnh của đồ thị (đảm bảo đồ thị đã cho là đồ thị dạng cây).
• Tiếp theo là \(q\) dòng chứa các câu hỏi của Nobita, mỗi câu hỏi có dạng \((u, v)\) với \(1 \le u, v \le n\).

Output

• Ghi ra \(q\) dòng, mỗi dòng tương ứng với kết quả của một câu hỏi.

Example

6 3 4
1 15 30 7 49 10
1 4
4 2
4 3
4 5
6 5
4 5
1 6
2 4
1 1

1
1
0
0

Scoring

• Subtask \(1\) (\(10\%\) số test): \(1 \le n \le 100\), \(k = 2\), \(1 \le q \le 100\).
• Subtask \(2\) (\(20\%\) số test): \(1 \le n \le 1000\), \(1 \le q \le 1000\).
• Subtask \(3\) (\(20\%\) số test): Mỗi đỉnh thuộc đồ thị có bậc tối đa là \(2\).
• Subtask \(4\) (\(50\%\) số test): Không có ràng buộc gì thêm.