Cho một cây vô hướng gồm ~n~ đỉnh. Đỉnh thứ ~i~ ~(1 \le i \le n)~ có trọng số là ~a_i~.

Định nghĩa hàm ~dist(u,v)~ là số cạnh trên đường đi đơn từ đỉnh ~u~ tới đỉnh ~v~.

Ta có: ~f(u) = \sum_{i=1}^{n} dist(u,i) \times a_i~

Hãy chọn ra một đỉnh ~u~ trên cây sao cho ~f(u)~ là lớn nhất.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên, số thứ ~i~ là ~a_i~ miêu tả trọng số của đỉnh thứ ~i~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~u_i,v_i~ miêu tả cạnh thứ ~i~ của cây.

Constraint

• ~1 \le n \le 2\times 10^5~
• ~1 \le a_i \le 2\times 10^5~

Subtask

• Subtask ~1~ ~(50\%)~: ~n \le 2000~.
• Subtask ~2~ ~(50\%)~: Không có ràng buộc gì thêm.

Output

• In ra kết quả của bài toán.

Sample Input 1:

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

Sample Output 1:

121

3 nàng tiên ánh sáng sau khi ăn xong quyết định ai rửa bát bằng trò chơi rút bài, ai thua sẽ phải rửa bát. Do ngày hôm qua Star Sapphire đã rửa bát nên chỉ có Sunny Milk và Luna Child chơi ngày hôm nay.

Bộ bài gồm không quá 400 lá bài, 2 người lần lượt chơi, mỗi lượt chọn 1 trong 2 lá ở 2 đầu bộ bài.

Bộ bài gồm các lá sau:

• # lá bài bình thường.
• 1, 2, 3, ... 9, lá bài cộng điểm, cộng số điểm tương ứng ghi trên lá bài.
• C, H, I, M, lá bài chìa khóa, là chìa khóa để mở các cánh cửa với chữ cái viết thường tương ứng ghi trên lá bài, một chìa khóa có thể được sử dụng nhiều lần.
• c, h, i, m, lá bài cánh cửa, cần lá bài chìa khóa để mở.

Trò chơi kết thúc khi có 1 người không thể rút bài hoặc hết bài (nếu còn bài thì bắt buộc phải rút). Do chơi 400 lá bài thì rất lâu nên 3 nàng tiên nhờ bạn xác đinh luôn ai là người phải rửa bát nếu cả Sunny Milk và Luna Child để chơi tối ưu. Sunny Milk là người đi trước.

Input:

• Gồm một xâu độ dài không quá 400 kí tự là các lá bài của bộ bài.

Output:

• In ra 2 dòng. Nếu phân định thằng thua in ra "SunnyMilk" hoặc "LunaChild" là người phải rửa bát, nếu hòa in ra "StarSapphire". Dòng tiếp theo in ra hiệu số điểm của Sunny Milk trừ đi điểm của Luna Child.

Sample Test 1

Input:

#4##

Output:

LunaChild
4

Sample Test 2

Input:

Ch#1#cH

Output:

SunnyMilk
-1

Reimu cần phong ấn một cuốn sách. Cô có ~n~ lá bùa, trên lá bùa thứ ~i~ có số nguyên dương ~a_i~. Để phong ấn cuốn sách cô cần chọn một số lá bùa trong số ~n~ lá bùa sao cho tích của chúng kết thúc bằng chữ số ~d~ và để đạt được hiệu quả cao thì tích phải là lớn nhất có thể. Bạn hãy giúp cô tìm ra những lá bùa cần sử dụng nhé!

Input

• Dòng đầu gồm 2 số nguyên dương ~n, d (1 \le n \le 100000, 0 \le d \le 9).~
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_i~.

Output

• Dòng đầu tiên là số tự nhiên ~k~ là số lượng lá bùa được chọn hoặc không có cách chọn in ra ~-1~.
• Nếu có cách chọn thì dòng tiếp theo số trên những lá bùa được chọn (có thể theo thứ tự ngẫu nhiên).

Sample Test

Input:

6 3
8 9 4 17 11 5

Output:

3
9 11 17 

Cho dãy ~a~ gồm ~n~ phần tử nguyên dương ~a_1,a_2,...,a_n~ và một số nguyên dương ~k~.

Một tập con không rỗng ~S~ của dãy ~a~ gồm các phần tử ~a_{i_1},a_{i_2},...,a_{i_t}~ sẽ có giá trị bằng ~f(S) = max(S) - min(S)~.

Bạn cần đếm số cách chọn ra một số tập ~S_i~ không giao nhau (một phần tử chỉ nằm trong một tập duy nhất) sao cho ~\sum f(S_i) \le k~.

Hai cách chọn được coi là khác nhau nếu như tồn tại một cặp phần tử nằm ở chung nhóm ở cách này nhưng khác nhóm ở cách kia.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~.
• Dòng thứ hai gồm ~n~ số nguyên, số thứ ~i~ là ~a_i~.

Constraint

• ~1 \le n \le 200~
• ~0 \le k \le 1000~
• ~1 \le a_i \le 100~.

Subtask

• Subtask ~1~ ~(20\%)~: ~n \le 5~.
• Subtask ~2~ ~(30\%)~: ~n \le 16~.
• Subtask ~3~ ~(50\%)~: Không có ràng buộc gì thêm.

Output

• In ra số cặp thỏa mãn, lấy phần dư cho ~10^9+7~.

Sample Input 1:

3 2
2 4 5

Sample Output 1:

3

Explanation 1

• ~S_1 = \{1,2\}, S_2 = \{3\}~. Tổng là ~2 + 0 = 2~.
• ~S_1 = \{1\}, S_2 = \{2,3\}~. Tổng là ~0 + 1 = 1~.
• ~S_1 = \{1\}, S_2 = \{2\}, S_3 = \{3\}~. Tổng là ~0~.

Trong một lần cắm trại trên núi, trưởng đoàn tổ chức một trò chơi bốc sỏi. Trò chơi gồm có ~n~ người tham gia và có tổng số ~m~ viên sỏi. Người thứ ~i~ được phép bốc tối đa ~a_i~ viên. Những người tham gia cũng có thể không bốc viên nào. Tất cả mọi người thống nhất sẽ bốc sao cho tổng số sỏi của họ là bội của ~9~.

Yêu cầu: Hãy giúp đoàn trưởng đếm số cách bốc sỏi khác nhau để tổng số sỏi không vượt quá ~m~ và là bội của ~9~ . Hai cách được gọi là khác nhau nếu tồn tại một người bốc số khác nhau.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~.
• Dòng thứ hai gồm ~n~ số nguyên, số thứ ~i~ là ~a_i~.

Constraint

• ~1 \le n \le 5~
• ~0 \le m \le 10^9~
• ~1 \le a_i \le m~.

Subtask

• Subtask ~1~ ~(20\%)~: ~m \le 10~.
• Subtask ~2~ ~(30\%)~: ~m \le 1000~.
• Subtask ~3~ ~(50\%)~: Không có ràng buộc gì thêm.

Output

• In ra số cách đếm được lấy phần dư cho ~10^9~.

Sample Input 1:

2 10
10 10

Sample Output 1:

11

Một số ~X~ được gọi là "xuất hiện" trong số ~Y~ nếu trong hệ thập phân, các chữ số của ~X~ thiết lập nên một dãy con (không nhất thiết liên tục) của dãy gồm các chữ số của ~Y~.

Ví dụ: ~X = 246~ xuất hiện trong ~Y = 1234567~, ~X = 212~ xuất hiện trong ~Y = 212~. Ngược lại số ~X = 1223~ không xuất hiện trong ~Y = 123~, số ~X = 31~ không xuất hiện trong ~Y =123~.

Yêu Cầu: Cho số nguyên dương ~B~, hỏi có bao nhiêu số xuất hiện trong ~B~ và chia hết cho ~N~.

Input

• Dòng đầu thứ nhất chứa số ~t~ ~(1 \le t \le 50)~ - thể hiện số test case.
• ~t~ block tiếp theo có dạng như sau:
• Dòng đầu tiên chứa số nguyên dương ~B~ và số ~B~ này có lượng chữ số không quá ~5000~ kí tự, số ~B~ không bắt đầu bằng số ~0~.
• Dòng thứ hai chứa số nguyên ~N~ ~(1 \le N \le 1000)~.

Output

• Với mỗi test case, in ra đáp án cần tìm theo ~mod~ ~10^9+7~.

Sample Input 1

1
1020402
24 

Sample Output 1

6

Với ~p = p_1, p_2, . . . , p_n~ là một hoán vị của ~n~ số nguyên dương từ ~1~ đến ~n~, gọi ~\beta(p)~ là số vị trí ~i~ có ~p_i < i~.

Cho ~n~ và ~k~, hãy đếm số hoán vị ~p~ của ~n~ số từ ~1~ đến ~n~ có ~\beta(p) = k~.

Input

• Dòng đầu ghi số nguyên dương ~n,k~.

Constraints

• ~1 \le n \le 1000, 0 \le k \le n~

Subtask

• ~30\%~ số test: ~n \le 10~
• ~30\%~ số test: ~n \le 20~
• ~40\%~ số test: không ràng buộc gì thêm.

Output

• Ghi một số nguyên duy nhất là số bộ đẳng cấu thứ tự với ~p~ sau khi chia lấy dư cho ~10^9 + 7~.

Sample Input 1

4 1 

Sample Output 1

11

Một ngân hàng có ~n~ chi nhánh, mỗi chi nhánh có một máy chủ, các máy chủ ở các chi nhánh được đánh số từ ~1~ đến ~n~. Nhằm bảo đảm việc truyền thông giữa các chi nhánh, ngân hàng đã thuê ~n-1~ kênh truyền tin trực tiếp từ một nhà máy cung cấp dịch vụ mạng để kết nối ~n~ máy chủ thành một mạng máy tính và bảo đảm từ máy chủ của một chi nhánh bất kì có thể truyền tin đến tất cả các máy chủ của các chi nhánh còn lại theo kênh truyền tin trực tiếp giữa chúng hoặc thông qua đường truyền đi qua một số máy chủ của các chi nhánh nào đó.

Trong thời gian tới, ngân hàng muốn lựa chọn ~k~ máy chủ trong ~n~ máy chủ để cài đặt phần mềm kiểm soát. Phần mềm khi hoạt động sẽ làm tăng lưu lượng truyền trên các kênh giữa ~k~ máy chủ này. Với mỗi phương án chọn ~k~ máy chủ để cài đặt phần mềm, trong số ~n-1~ kênh truyền tin, nhà cung cấp dịch vụ mạng đã xác định một số ít nhất các kênh đủ để kết nối ~k~ máy chủ này và khuyến cáo ngân hàng cần phải nâng cấp các kênh đó. Vì lí do kĩ thuật cũng như kinh phí, ngân hàng muốn lựa chọn ~k~ máy chủ để cài đặt phần mềm mà số lượng kênh ít nhất cần nâng cấp có giá trị nằm trong đoạn ~[a,b]~. Cụ thể, với mỗi cách chọn ~k~ máy chủ, gọi ~s~ là số kênh ít nhất cần chọn ra trong ~n-1~ kênh truyền tin nhằm đảo bảo liên thông giữa ~k~ máy chủ được chọn ngay cả khi các kênh còn lại bị đứt kết nối, ~s~ kênh này sẽ được khuyến cáo nâng cấp, khi đó, cách chọn ~k~ máy chủ thỏa mãn yêu cầu của ngân hàng nếu ~a \le s \le b~.

Yêu Cầu: Cho ~n-1~ kênh truyền tin và các giá trị ~k,a,b~ hãy đếm số lượng cách chọn ~k~ máy chủ để cài đặt phần mềm mà số lượng kênh ít nhất cần nâng cấp nằm trong đoạn ~[a,b]~.

Input

• Dòng đầu ghi bốn số nguyên dương ~n,k,a,b~ ~(k < n; 1 < a \le b < n)~.
• Dòng thứ ~i~ trong số ~n-1~ dòng tiếp theo chứa hai số nguyên dương ~u_i~ và ~v_i~ cho biết kênh truyền tin trực tiếp giữa hai máy chủ ~u_i,v_i~.

Constraints

• ~1 \le n \le 10^5~

Subtask

• ~20\%~ số test: ~n \le 100~ và ~k = 2~.
• ~30\%~ số test: ~n \le 100~ và ~k = 3~.
• ~20\%~ số test: ~n \le 100~ và ~k = 4~.
• ~20\%~ số test: ~n \le 1000~ và ~k = 3~.
• ~10\%~ số test: ~n \le 1000~ và ~k = 4~.

Output

• Ghi một số nguyên duy nhất là số cách chọn ~k~ máy chủ để cài đặt phần mềm thỏa mãn yêu cầu của ngân hàng.

Sample Input 1

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

Sample Output 1

14

Explanation 1

Có ~5~ cách với số đường truyền cần nâng cấp là ~2~: ~(1,2,3); (2,3,4); (2,3,6); (3,4,5); (3,4,6)~

Có ~9~ cách với số đường truyền cần nâng cấp là ~3~.

Cho một cây ~n~ đỉnh, các đỉnh được đánh số từ ~1~ đến ~n~. Một bộ ~k~ đỉnh ~(x_1, x_2, . . . , x_k)~ được gọi là đẳng cấu thứ tự với hoán vị ~(p_1, p_2, . . . , p_k)~ nếu tồn tại một đường đi đơn đi qua các đỉnh ~x_1, x_2, . . . , x_k~ theo đúng thứ tự đó, và với mọi ~1 \le i < j \le k~ thì ~x_i < x_j~ khi và chỉ khi ~p_i < p_j~ . Cho ~p = (p_1, p_2, p_3)~ là một hoán vị của ~(1, 2, 3)~, hãy đếm số bộ ~3~ đỉnh đẳng cấu thứ tự với ~p~.

Input

• Dòng đầu ghi số nguyên dương ~n~.
• Dòng sau gồm ~3~ số nguyên dương ~p_1,p_2,p_3~.
• ~n-1~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương ~u,v~ là một cạnh của cây.

Constraints

• ~1 \le n \le 10^5~

Subtask

• ~30\%~ số test: ~n \le 500~.
• ~30\%~ số test: ~n \le 5000~.
• ~20\%~ số test: mỗi đỉnh đều kề với nhiều nhất hai đỉnh khác.
• ~20\%~ số test: không có ràng buộc gì thêm.

Output

• Ghi một số nguyên duy nhất là số bộ đẳng cấu thứ tự với ~p~.

Sample Input 1

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

Sample Output 1

6

Cho dãy số nguyên dương ~𝐴~ có ~𝑁~ phần tử ~𝑎_1, 𝑎_2, … , 𝑎_N~. Có ~𝑄~ truy vấn có dạng ~𝐿, 𝑅, 𝐾~ với ý nghĩa như sau:

• Xét dãy con ~𝐵~ là dãy con của ~𝐴~ gồm các phần tử liên tiếp từ vị trí ~𝐿~ đến vị trí ~𝑅~ : ~𝑎_L, 𝑎_{L+1}, … , a_R~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑁)~, ta xây dựng dãy số ~𝐶~ bằng cách coi ~𝐶~ là tập hợp tất cả các dãy con liên tiếp của ~B~. Ví dụ: dãy ~𝐵 = \{1, 2, 1\}~ các dãy con của ~B~ là ~\{1\}, \{2\}, \{1\}, \{1,2\}, \{2,1\}, \{1,2,1\}~ ta sẽ có dãy ~𝐶 = \{1, 2, 1, 1, 2, 2,1, 1,~~ 2, 1\};~
• Sắp xếp dãy ~𝐶~ theo thứ tự không giảm và đưa ra phần tử thứ ~𝐾~. Ví dụ: với dãy ~𝐶~ trên ta sắp xếp thành ~\{1, 1, 1, 1, 1, 1, 2, 2, 2, 2\}~ và phần tử thứ ~8~ là ~2~.

Yêu cầu: Cho dãy số ~𝐴~ và ~𝑄~ truy vấn như trên, hãy đưa ra kết quả phần tử thứ ~𝐾~ của dãy số ~𝐶~ tương ứng trong mỗi truy vấn.

Dữ liệu nhập vào từ file văn bản DLT.INP:

• Dòng đầu tiên gồm hai số nguyên dương ~𝑁~ và ~𝑄~ ~(1 ≤ 𝑁, 𝑄 ≤ 5 \times 10^5)~ là số phần tử của dãy số ~𝐴~ và số lượng truy vấn~;~
• Dòng thứ hai gồm ~𝑁~ số nguyên dương ~𝑎_1, 𝑎_2, … , 𝑎_N~ ~(1 ≤ 𝑎_i ≤ 5 \times 10^5; \ 1 ≤ 𝑖 ≤ 𝑁);~
• ~𝑄~ dòng sau, mỗi dòng chứa ba số ~𝐿, 𝑅, 𝐾~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑁)~ mô tả truy vấn.

Dữ liệu đảm bảo đúng đắn, luôn có kết quả.

Kết quả ghi ra file văn bản DLT.OUT:

~𝑄~ dòng là kết quả tương ứng của mỗi truy vấn.

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄 ≤ 100;~
• ~10\%~ số test khác ứng với ~10\%~ số điểm của bài thoả mãn: ~𝑁, 𝑎_i ≤ 100;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄, 𝑎_i ≤ 5000;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄 ≤ 10^5; 𝑎_i ≤ 100;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄, 𝑎_i ≤ 10^5;~
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5 2
1 2 1 3 2
1 3 8
1 4 18

Output

2
3