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.

Yêu cầu: Tìm độ dài dãy con không giảm dài nhất sau khi cắt xâu.

Input

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

Output

• Ghi ra độ dài dãy con không giảm dài nhất.

Sample Input 1

8
13220131

Sample Output 1

4

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. 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 đ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. 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ứ ~i~ bị tiêu diệt, và nếu không dùng ngay thì nó sẽ biến mất khi UFO thứ ~i+1~ bị tiêu diệt. Giả sử đã tiêu diệt được ~j~ 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ừ ~j+1~ đến vị trí ~j+x~ bất kì sao cho ~j+x \le n~.

Yêu cầu: Với mỗi câu hỏi, tính chi phí thấp nhất để tiêu diệt ~z_i~ UFO tiếp theo nếu đã chơi được tới màn thứ ~x_i~ và đã tiêu diệt được ~y_i~ UFO.

Input

• Dòng đầu: ~n, a, t, q~ (~1 \le n, t, q \le 5 \times 10^4~, ~1 \le a \le 10^9~).
• ~t~ dòng tiếp theo là các khẩu súng đặc biệt: ~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: ~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 kết quả của các câu hỏi.

Sample Input 1

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

Sample Output 1

13
1
14
4

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. 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ăn khít hơn.

Để 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 ~x^k~ với ~x~ là một số tự nhiên). Ta gọi một cặp quả táo được gọi 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.

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: Nếu gọi ~S~ là tập các quả táo thuộc đường đi đơn từ ~u~ đến ~v~, thì sẽ có bao nhiêu cặp quả táo ~(a, b)~ sao cho ~a~ và ~b~ đều thuộc ~S~, ~a < b~ và cặp ~(a, b)~ hợp nhau bậc ~k~.

Yêu cầu: Giải đáp các câu hỏi của Nobita.

Input

• Dòng đầu chứa ba số nguyên: ~n, q, k~ (~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ị.
• 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, tương ứng với kết quả của các câu hỏi.

Sample Input 1

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

Sample Output 1

1
1
0
0

Tí có một đồ thị ~G~ vô hướng gồm ~n~ đỉnh và ~m~ cạnh. Ta gọi một đỉnh thuộc đồ thị là cô đơn nếu nó chỉ có thể đến được không quá 1 đỉnh khác nó. Hai đỉnh ~u, v~ được gọi là đến được nhau nếu tồn tại một dãy các đỉnh ~v_1 = u, v_2, \dots, v_k = v~, sao cho ~∀1 \le i < k~ thì cạnh ~(v_i, v_{i+1})~ thuộc đồ thị.

Ta có ~G(l, r)~ là đồ thị ~G~ nhưng chỉ giữ lại các đỉnh có chỉ số trong đoạn ~[l, r]~ và các cạnh nối giữa các đỉnh trong đoạn ~[l, r]~; độ cô đơn ~f(l, r)~ sẽ là số lượng đỉnh cô đơn có trong đồ thị ~G(l, r)~. Nhiệm vụ của Tí là tính tổng: ~ \sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) ~

Yêu cầu: Tính tổng độ cô đơn của tất cả ~G(l, r)~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ (~1 \le n \le 10^5~), ~m~ (~0 \le m \le 2 \times 10^5~).
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~u_i, v_i~ (~1 \le u_i, v_i \le n~) mô tả hai đỉnh nối bởi cạnh thứ ~i~. Dữ liệu đảm bảo ~∀i \ne j: u_i \ne u_j~ hoặc ~v_i \ne v_j~.

Output

• Ghi kết quả trên một dòng, là tổng độ cô đơn của tất cả ~G(l, r)~.

Sample Input 1

5 3
2 4
1 2
2 3

Sample Output 1

18

Cho dãy ~a~ gồm ~n~ phần tử, được đánh số từ 1 tới ~n~. Ta gọi ~f(l, r)~ là số lớn nhất có dạng ~2^x~ sao cho tổng của các số ~a_l, a_{l+1}, \dots, a_r~ chia hết cho ~2^x~. Nhiệm vụ của bạn là tính tổng của tất cả các ~f(l, r)~ với ~1 \le l \le r \le n~.

Yêu cầu: Tính tổng các ~f(l, r)~ và lấy phần dư khi chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 2 \times 10^5~) tương ứng là độ dài của dãy ~a~.
• Dòng thứ hai chứa ~n~ số nguyên mô tả dãy ~a~, số nguyên thứ ~i~ là giá trị của ~a_i~ (~1 \le a_i \le 10^6~, ~\sum_{i=1}^{n} a_i \le 10^6~).

Output

• Ghi kết quả trên một dòng, là kết quả của bài toán sau khi lấy phần dư khi chia cho ~10^9 + 7~.

Sample Input 1

3
1 2 3

Sample Output 1

8

Cho cây gồm ~n~ đỉnh, mỗi cạnh của cây có thể được tô một màu nào đó. Một đường đi đơn trên cây là đường đi không lặp lại cạnh, một đường đi đơn gọi là xấu khi và chỉ khi các cạnh trên đường đi đó có màu phân biệt. Một cây được gọi là xấu khi và chỉ khi tồn tại ít nhất một đường đi đơn độ dài ~k~ là xấu. Ta sẽ tìm cách tô màu các cạnh của cây, sao cho cây không là một cây xấu, độ đẹp của cây là số lượng màu khác nhau ta sử dụng để tô các cạnh. Hãy tìm cách tô sao cho độ đẹp là lớn nhất.

Yêu cầu: Tìm độ đẹp lớn nhất của cây.

Input

• Dòng đầu tiên chứa lần lượt hai số nguyên ~n, k~ (~1 \le k \le n \le 10^5~, ~k \le 30~) tương ứng là số đỉnh của cây đồ thị và số ~k~ như mô tả bài toán.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ (~1 \le u, v \le n~) tương ứng với hai cạnh nối cặp đỉnh ~(u, v)~ trên cây.

Output

• Ghi ra trên một dòng là độ đẹp lớn nhất của cây.

Sample Input 1

6 3
1 2
2 3
3 4
4 5
5 6

Sample Output 1

3