Cho một cây gồm ~n~ đỉnh có gốc là ~1~.

Bạn được cho ~m~ truy vấn, truy vấn thứ ~i~ như sau:

• Truy vấn bao gồm ~k_i~ số đỉnh phân biệt ~v_{1},v_{2},...,v_{k_i}~. Bạn cần kiểm tra xem liệu có tồn tại một đường đi từ gốc tới một đỉnh ~u~ sao cho mỗi đỉnh trong ~k_i~ đỉnh đã cho đều thuộc vào đường đi này hoặc có khoảng cách bằng ~1~ với một số đỉnh trên đường đi này.

Input

• Dòng đầu chứa hai số nguyên ~n, m~ ~(n \le 10^5, m \le 2\times 10^5)~.
• ~n-1~ dòng sau, mỗi dòng sau gồm hai số ~u,v~ miêu tả cạnh ~(u,v)~ của cây,
• ~m~ dòng sau miêu tả ~m~ truy vấn có dạng:
  • Đầu tiên là một số nguyên dương ~k_i~ miêu tả số đỉnh. Tiếp theo là ~k_i~ đỉnh phân biệt miêu tả truy vấn.
• Tổng ~k_i~ trong tất cả các truy vấn không vượt quá ~4 \times 10^5~.

Output

• Với mỗi kết quả, nếu có đường đi từ gốc thỏa mãn thì in ra "1", ngược lại in ra "0".

Sample Input 1

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

Sample Output 1

1
1
1
1
0
0

Bạn có một xâu ~A~ và cần thực hiện các bước sau để mã hóa xâu:

• ~Reverse(A)~: đảo ngược các kí tự trong xâu ~A~. Ví dụ ~Reverse("abc") = "cba"~.
• ~Shuffle(A)~: đổi chỗ các kí tự trong xâu ~A~. Ví dụ, ~Shuffle("god")~ có thể là ~"god", "dog", "dgo", ...~
• ~Merge(A,B)~: Trộn hai xâu ~A,B~ với nhau và giữ nguyên thứ tự của các kí tự trong từng xâu. Ví dụ ~Merge("abc","def")~ có thể là ~"abcdef", "adebcf", ...~

Xâu ~A~ (gồm các kí tự Latin in thường) ban đầu đã được mã hóa thành xâu ~S = Merge(Reverse(A),Shuffle(A))~.

Cho xâu ~S~, hãy xác định xâu ~A~ trước khi mã hóa. Do có thể có nhiều kết quả, hãy in ra xâu ~A~ có thứ tự từ điển nhỏ nhất.

Input

• Gồm một dòng chứa xâu ~S~.

Output

• In ra xâu ~A~ thỏa mãn.

Constraints .

• ~|S| \le 10^5~.

Subtask

• Sub ~1~ (~50\%~): ~n \le 1000~.
• Sub ~2~ (~50\%~): ~n \le 10^5~.

Sample Input 1

abbabb

Sample Output 1

abb

Cho một dãy số gồm ~n~ phần tử ~a_1~, ~a_2~, ..., ~a_n~. Với một dãy số gồm ~m~ phần tử ~b_1~, ~b_2~, ..., ~b_m~, trọng số của dãy ~b~ được định nghĩa là tích của giá trị lớn nhất và nhỏ nhất của dãy. Hãy tìm tổng trọng số của các dãy con của dãy ~a~.

Dãy con của dãy ~a~ được định nghĩa là một tập ~a_{i_1}~, ~a_{i_2}~, ..., ~a_{i_k}~ với 1 ~\le~ ~i_1~ < ~i_2~ < ... < ~i_k~ ~\le~ ~n~.

INPUT

• Dòng đầu chứa số nguyên dương ~n~ (~1~ ~\le~ ~n~ ~\le~ ~10^5~).
• Dòng thứ hai chứ ~n~ số nguyên không âm ~a_i~ (~0~ ~\le~ ~a_i~ ~\le~ ~10^9~).

OUTPUT

• In ra một số nguyên duy nhất là tổng trọng số của tất cả các dãy con. Do output có thể rất lớn nên hãy in ra kết quả mod ~10^9 + 7~.

SAMPLE TEST

Input:

5
4 2 1 3 4

Output:

208

SUBTASKS

• ~30\%~ số điểm có ~n~ ~\le~ ~20~.
• ~30\%~ số điểm có ~n~ ~\le~ ~10^3~.
• ~40\%~ số điểm còn lại có ~n~ ~\le~ ~10^5~.

Cho một cây vô hướng ~n~ đỉnh. Trên mỗi đỉnh ~i~ sẽ có một trọng số nguyên ~a_i~. Định nghĩa ~g(u,v)~ là giá trị lớn nhất của trọng số các đỉnh trên đường đi ngắn nhất từ ~u~ đến ~v~. Hãy tính tổng ~g(u,v)~ với mọi cặp ~(1 \le u < v \le n)~.

Input:

• Dòng đầu là số nguyên dương ~n~. ~(2 \le n \le 10^5)~.
• Dòng sau gồm n số nguyên ~a_i. (|a_i| <= 10^6)~.
• ~n-1~ dòng sau mỗi dòng gồm 2 số nguyên ~u,v~ miêu tả cạnh nối giữa 2 đỉnh ~u,v~.

Output:

In ra một số nguyên là kết quả của bài toán.

Subtasks

• Subtask 1: ~n \leq 5000~.
• Subtask 2: Không có điều kiện gì thêm.

Sample Test

Input:

3
3 2 4
1 2
1 3

Output:

11

Giải thích:

Ta có : ~g(1,2) + g(1,3) + g(2,3) = 3 + 4 + 4 = 11.~

Cho dãy ~a~ gồm ~n~ phần tử nguyên và một số nguyên dương ~k~. Hãy in ra đoạn con liên tiếp có tổng lớn thứ ~k~. (Có ~n*(n+1)/2~ đoạn con liên tiếp trong dãy).

Input

• Dòng đầu gồm 2 số nguyên dương ~n~ ~(1 \le n \le 10^5)~ và ~k~ ~(1 \le k \le n*(n+1)/2)~.
• Dòng thứ 2 gồm ~n~ số nguyên miêu tả dãy ~a~. ~(-10^9 \le a_i \le 10^9)~.

Ouput

• In ra giá trị của đoạn con liên tiếp có tổng lớn thứ ~k~.

Sample Test

Input

4 3
1 -1 2 -2

Output

1

Giải thích: đoạn con ~[1,3], [3,3]~ là hai đoạn con có giá trị lớn nhất với tổng bằng ~2~. Tiếp đến là hai đoạn con ~[1,1], [2,3]~ có tổng bằng ~1~ có giá trị lớn thứ ~3~ và ~4~. Vậy đoạn con có giá trị lớn thứ ~k~ sẽ có giá trị bằng ~1~.

Hôm nay 3 nàng tiên ánh sáng đi tìm kho báu. Khi đến trước cửa hang động, họ nhìn thấy ~n~ cây nấm với màu sắc và kích cỡ khác nhau. Theo như truyền thuyết muốn mở cánh cửa hang động thì cần sắp xếp các cây nấm này theo thứ tự tăng dần của kích cỡ, chỉ được đổi chỗ 2 cây nấm ở cạnh nhau. Mỗi lần đổi chỗ 2 cây nấm cho nhau sẽ tốn 1 ma lực, nhưng nếu 2 cây nấm cùng màu thì không tốn chút sức nào cả.

Hãy giúp Sunny Milk và đồng bọn tính số ma lực tối thiểu để có thể mở cánh cửa hang động nhé!

Input

• Dòng đầu tiên gồm số nguyên dương ~n \le 10^5~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~1 \le c_i \le n~ là màu của cây nấm thứ ~i~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~1 \le s_i \le n~ là kích cỡ của cây nấm thứ ~i~.

Output

• In ra một số nguyên duy nhất là lượng ma lực tối thiểu cần để mở cánh cửa.

Sample Test

Input:

5
1 5 2 2 1
3 2 1 2 1

Output:

6

Chim là loài động vật đại diện cho sự tự do. Châu có nuôi 1 con chim tên là Ển, hiện đang sống tại tọa độ ~(0, 0)~ trên mặt phẳng Descartes và hướng về phía dương của trục ~Ox~. Châu đang có một chuỗi thao tác gồm một số thao tác xác định và chưa xác định:

• ~F~ là 1 thao tác cố định yêu cầu chim đi chuyển 1 đơn vị về hướng hiện tại.
• ~T~ là 1 thao tác chưa xác định. Bạn có thể chọn T là cho chim quay theo chiều kim đồng hồ 90 độ hoặc cho chim quay theo ngược chiều kim đồng hộ 90 độ.

Có ~Q~ truy vấn tương ứng là ~Q~ tọa độ ~(x,y)~. Châu muốn biết xem có thể chọn các thao tác ~T~ tương ứng để chim đến được tọa độ ~(x,y)~ không.

Input:

• Dòng đầu tiên là ~Q~ – số lượng truy vấn.
• Dòng thứ hai là xâu biểu diện các thao tác.
• ~Q~ dòng tiếp theo mỗi dòng chứa tọa độ ~(x,y)~.

Output:

• Dòng thứ ~i~ trả về YES nếu chim có thể đến được ~(x,y)~ ở truy vấn thứ ~i~, ngược lại NO.

Sample Test

Input:

2
FTFFTFF
3 2
0 1

Output:

Yes
No

Giới hạn:

• Subtask 1 (20% số điểm): Độ dài các xâu không vượt quá ~20~ kí tự, ~Q \le 20~.
• Subtask 2 (40% số điểm): Độ dài các xâu không vượt quá ~100~ kí tự, ~Q \le 100~.
• Subtask 3 (40% số điểm): Độ dài các xâu không vượt quá ~4000~ kí tự, ~Q \le 10^5~.

Cho dãy ~a~ gồm ~n~ phần tử nguyên dương.

Hãy chọn ra một tập nhiều nhất các phần tử sao cho chúng đôi một không phải là ước hoặc bội của nhau.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~. ~(1 \le n \le 300)~
• Dòng tiếp theo gồm ~n~ số nguyên dương miêu tả dãy ~a~ ~(1 \le a_i \le 10^4)~.

Output

• In ra độ dài của dãy dài nhất tìm được.

Subtask

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

Sample Input 1

6
2 4 5 6 7 420

Sample Output 1

4