Cho một dãy gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Hãy đếm số đoạn con ~[l, r]~ ~(1 \le l < r \le n)~ sao cho ~a_l + a_{l+1} + ... + a_r~ chia hết cho ~d~

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~d~ ~(1 \le n, d \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(-10^9 \le a_i \le 10^9)~

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Sample Input

5 4
1 3 -2 3 -5

Sample Output

4

Cho một dãy ~a~ gồm ~n~ phần tử nguyên không âm và ~q~ thao tác, thao tác thứ ~i~ có dạng ~(l_i,r_i,d_i)~, nghĩa là tăng giá trị của các phần tử trong mảng ~a~ từ vị trí ~l_i~ tới ~r_i~ thêm ~d_i~ đơn vị.

Bạn cần thực hiện ~k~ truy vấn, truy vấn thứ ~i~ có dạng ~(x_i,y_i)~, có nghĩa là thực hiện các thao tác ~x_i,x_{i+1},...,y_i~.

Hãy in ra giá trị của các phần tử trong mảng ~a~ sau khi thực hiện ~k~ truy vấn.

Input

• Dòng đầu tiên chứa ~3~ số nguyên dương ~n,q,k~.
• Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả dãy ~a~.
• ~q~ dòng sau, dòng thứ ~i~ gồm ~3~ số nguyên dương ~l_i,r_i,d_i~ miêu tả thao tác thứ ~i~.
• ~k~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên dương ~x_i,y_i~ miêu tả truy vấn thứ ~i~.

Output

• Gồm một dòng in ra ~n~ số, số thứ ~i~ là giá trị của phần tử ~a_i~ sau khi thực hiện ~k~ truy vấn.

Điều kiện

• ~1 \le n \le 10^5~.
• ~0 \le a_i,d_i \le 10^5~.

Subtask

• ~50\%~ số điểm: ~n \le 1000~.
• ~50\%~ số điểm: ~n \le 10^5~.

Ví dụ

Input 1:

3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3

Output 1:

9 18 17

Input 2:

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

Output 2:

5 18 31 20

Cho một dãy xâu ~S~ gồm ~n~ kí tự từ ~1~ đến ~9~. Hãy đếm số lượng cặp ~(i, j)~ ~(1 \le i \le j \le n)~ thỏa mãn các chữ số trong đoạn ~[i, j]~ tạo thành một số nguyên chia hết cho ~2023~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - độ dài xâu ~(1 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ kí tự của xâu ~S~.

Output

Gồm số nguyên duy nhất là kết quả bài toán.

Sample Test

Input:

10
2427624276

Output:

3

Note

Các cặp ~(i, j)~ thỏa mãn là: ~(1, 5)~ ~(6, 10)~, ~(1, 10)~.

Đất nước Mirinda tươi đẹp được mô tả bằng một ma trận ~n \times m~ ô vuông, ô ở dòng thứ ~i~ từ trên xuống và cột thứ ~j~ từ trái sang gọi là ô ~(i, j)~. Khoảng cách giữa ô ~(x,y)~ với ô ~(i,j)~ là ~|x - i| + |y - j|~. Ô ~(i, j)~ có giá trị tài sản là ~a_{i,j}~.

Do biến đổi khí hậu, những cơn bão ngày một nhiều hơn và mạnh hơn. Mỗi cơn bão được đặc trưng bởi:

• ~w~ - cấp bão,
• ~R_1~ - bán kính bão,
• ~R_2~ - bán kính mắt bão,
• ~(x, y)~ - tọa độ bão sẽ đổ bộ.

Theo đó, các ô ~(i, j)~ có khoảng cách đến ô ~(x, y)~ thuộc đoạn ~[R_2, R_1]~ sẽ bị tác động, đồng thời giá trị tài sản ở ô đó sẽ giảm đi min(w, b[i][j]), với ~b_{i,j}~ là giá trị tài sản hiện có ở ô ~(i, j)~.

Là một nước giáp biển, hằng năm đất nước Mirinda phải đón ~k~ trận bão. Do đặc trưng địa hình, bão sẽ chỉ đổ bộ vào một trong ~q~ ~(q < 5)~ điểm phân biệt. Rút kinh nghiệm từ siêu bão Fanta, ủy ban chống bão muốn biết sau khi ~k~ trận bão đó tàn phá thì nước này phải chịu tổng thiệt hại là bao nhiêu?

(Tổng thiệt hại của nước này được tính bằng tổng mức giảm giá trị tài sản của tất cả các ô).

Input

• Dòng đầu tiên chứa ~4~ số nguyên dương ~n,m,q,k~ (~1 < n, m < 500, k \leq 10^5~).
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên ~a_{i,j}~ (~0 < a_{i,j} < 10^9~).
• Dòng tiếp theo ghi ~2 \times q~ số nguyên là tọa độ của ~q~ điểm đặc biệt: ~x_1, y_1, x_2, y_2, \ldots, x_q, y_q~.
• ~k~ dòng cuối, mỗi dòng ghi ~5~ số nguyên mô tả cơn bão: ~w, R_1, R_2, x, y~ (~0 < R_2 < R_1 < 1000, 0 < w < 1000~). Dữ liệu đảm bảo ~x,y~ là ~1~ trong ~q~ điểm đã cho.

(Các trận bão sẽ được liệt kê theo đúng thứ tự đổ bộ).

Output

In ra tổng thiệt hại sau ~k~ cơn bão.

Sample Test

Input:

3 4 2 4
10 11 12 15
20 10 11 25
30 32 35 40
1 1 3 4
2 2 0 3 4
2 2 0 1 1
2 4 2 1 1
2 3 1 3 4

Output:

56

Ta có định nghĩa ~div(i)~ là số lượng ước số của số nguyên dương ~i~. Ví dụ ~div(3) = 2; div(6) = 4~.

Gọi ~S(n,m)~ là tập các số nguyên dương thỏa mãn ~div(i) = n~ và các thừa số nguyên tố của ~i~ đều bé hơn hoặc bằng số nguyên tố thứ ~m~. Ví dụ, ~S(2,3) = \{2,3,5\}~ vì số nguyên tố thứ ~3~ là ~5~.

Bạn hãy in ra số lượng phần tử trong tập ~S(n,m)~. Con số này có thể rất lớn nên hãy in ra theo modulo ~10^9+7~.

Input

• Dòng đầu chứa hai số nguyên dương ~t~ ~(1 \le 2 \times 10^5)~.
• ~t~ dòng sau, mỗi dòng gồm hai số nguyên dương ~n,m~ thể hiện truy vấn ~(1 \le n \le 2 \times 10^6, 1 \le m \le 10^9)~.

Output

• Với mỗi truy vấn, in ra kết quả.

Subtask:

• Subtask ~1~: ~t,n,m \le 10~ ~(30\%)~
• Subtask ~2~: ~t = 1, m \le 10^5~ ~(30\%)~
• Subtask ~3~: Không có ràng buộc gì thêm. ~(40\%)~

Sample Input 1

3
2 3
4 4
3 5

Sample Output 1

3
10
5

Dãy con của một dãy là dãy thu được bằng cách xóa đi một số phần tử của dãy ban đầu (có thể không xóa phần tử nào) và giữ nguyên thứ tự của các phần tử còn lại. Một dãy số được gọi là dãy tăng kép nếu có thể tách nó ra thành hai dãy con khác rỗng, sao cho mỗi phần tử của dãy ban đầu thuộc vào đúng dãy con đó, và các phần tử trong cùng một dãy con thì tăng nghiêm ngặt.

Cho dãy số nguyên ~a~ có ~n~ phần tử, hãy đếm số dãy con của ~a~ là dãy tăng kép.

Input

• Dòng đầu tiên gồm số nguyên ~n~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ ~(1 \le a_i \le n)~

Output

• In ra số lượng dãy tăng kép là dãy con của ~a~, sau khi chia lấy dư cho ~1000000007~

Subtask :

• Subtask ~1~: ~n \le 20~ ~(20\%)~
• Subtask ~2~: ~n \le 200~ ~(20\%)~
• Subtask ~3~: ~n \le 2000~ và ~a_i \le 200~ ~(25\%)~
• Subtask ~4~: ~n \le 2000~ ~(35\%)~

Sample Input 1:

4
3 3 4 2

Sample Output 1:

9

Cho đồ thị đơn vô hướng gồm ~n~ đỉnh và ~m~ cạnh.

Có ~q~ câu hỏi, mỗi câu hỏi bạn nhận được một giá trị ~k~, tìm cách thêm đúng ~k~ cạnh vào đồ thị sao cho số cạnh cầu của đồ thị mới là ít nhất. Lưu ý rằng bắt đầu mỗi truy vấn, chúng ta chỉ xem xét với đồ thị gốc.

Input

• Dòng đầu chứa ba số nguyên ~n,m,q~ ~(1 \le n,q \le 10^5)~ và ~(1 \le m \le 2 \times 10^5)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u_i, v_i~ ~(1 ≤ u_i, v_i ≤ n; u_i ≠ v_i)~.
• ~q~ dòng sau, mỗi dòng gồm một số nguyên ~k~ miêu tả truy vấn.

Output

• Dòng đầu chứa một số ~d~ là đường đi ngắn nhất, nếu không có hãy in ra ~-1~.
• Dòng sau in ra ~d~ số nguyên là thứ tự đi của kết quả tìm được.

Subtask

• Subtask ~1~: ~q = 1~ và đồ thị là cây. ~(20\%)~
• Subtask ~2~: ~q = 1, k = 1, n \le 10^3~. ~(20\%)~
• Subtask ~3~: ~q = 1, k = 1, n \le 10^5~. ~(20\%)~
• Subtask ~4~: ~q = 1~ ~(20\%)~.
• Subtask ~5~: Không có ràng buộc gì thêm ~(20\%)~.

Sample Input 1

3 2 1
1 2
2 3
1

Sample Output 1

2

Cho ba số nguyên dương ~c~, ~d~, ~x~. Bạn cần phải tìm số cặp ~(a,b)~ thỏa mãn ~c*lcm(a,b) - d*gcd(a,b) = x~. Ở đây, ~lcm(a,b)~ là bội chung nhỏ nhất của ~(a,b)~, ~gcd(a,b)~ là ước chung lớn nhất của ~(a,b)~.

Input

• Dòng đầu gồm số nguyên dương ~t~ ~(t \le 10^4)~ là số lượng test case.
• ~t~ dòng sau, mỗi dòng gồm ba số nguyên dương ~c~, ~d~, ~x~ miêu tả test case. ~(1 \le c,d,x \le 10^7)~

Output

• Với mỗi test case, in ra số lượng cặp ~(a,b)~ thỏa mãn.

Sample Test

Input

4
1 1 3
4 2 6
3 3 7
2 7 25

Output

4
3
0
8

Giải thích: Ở test case thứ nhất, có ~4~ cặp thỏa mãn là ~(1,4), (4,1), (3,6), (6,3)~

Cho dãy ~A~ gồm ~n~ số nguyên dương: ~a_1,a_2,...,a_n~. Hãy tính:

• ~\prod_{S \subseteq A}^{S \neq 0}gcd(S)~.

Ở đây, ~gcd(S)~ là kí hiệu ước chung lớn nhất của tập ~S~.

Input

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

Constraint

• ~1 \le n \le 10^5~
• ~1 \le a_i \le 10^6~.

Subtask

• Subtask ~1~ ~(30\%)~: ~1 \le n \le 20~.
• Subtask ~2~ ~(30\%)~: ~a_i~ đôi một phân biệt.
• Subtask ~3~ ~(40\%)~: Không có ràng buộc gì thêm.

Output

• In ra kết quả bài toán sau khi chia lấy dư cho ~10^9+7~.

Sample Input 1:

3
1 4 6

Sample Output 1:

48

Cho dãy ~a_1,a_2,...,a_n~ gồm các số nguyên dương. Bạn được thực hiện thao tác sau trong khoảng từ ~0~ đến ~k~ lần:

• Chọn ra hai vị trí ~i,j~ ~(1 \le i, j \le n; i \neq j)~. Tăng ~a_i~ lên ~1~ và giảm ~a_j~ đi ~1~.

Bài toán đặt ra là cần tìm số nguyên dương ~D~ lớn nhất sao cho sau khi thực hiện các thao tác, ~a_i~ chia hết cho ~D~ ~\forall i \in [1,n]~.

Input

• Dòng đầu tiên gồm hai số nguyên ~n,k~ ~(2 \le n \le 500, 0 \le k \le 10^9)~
• Dòng thứ hai gồm ~n~ số nguyên, số thứ ~i~ là ~a_i~ ~(1 \le a_i \le 10^6)~.

Output

• In ra số nguyên ~D~ tìm được.

Sample Input 1:

8 7
7 1 6 5 2 8 6 5

Sample Output 1:

5

Đếm số cách chia ~n~ cái kẹo cho ~k~ người sao cho số kẹo của mỗi người nhận được đều thuộc đoạn ~[L,H]~. Hai cách chia kẹo được coi là khác nhau nếu tồn tại một người nhận được số kẹo khác nhau trong hai cách.

Nói cách khác, đếm số nghiệm nguyên của phương trình: ~x_1 + x_2 + ... + x_k = n~, sao cho ~\forall i \in [1,n]: L \le x_i \le H~.

Input

• Gồm bốn số nguyên dương: ~n~ ~k~ ~L~ ~H~ ~(0 \le L \le H \le n)~

Constraint

• ~1 \le k \le n \le 10^6~

Subtask

• Subtask ~1~ ~(30\%)~: ~1 \le n \le 10~.
• Subtask ~2~ ~(30\%)~: ~k \le n \le 1000~
• Subtask ~3~ ~(40\%)~: ~k \le n \le 10^6~

Output

• In ra kết quả bài toán sau khi chia lấy dư cho ~10^9+7~.

Sample Input 1:

6 3 0 6 

Sample Output 1:

28

Sample Input 2:

6 4 0 2 

Sample Output 2:

10

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

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 13~
• ~0 \le m \le 10^9~
• ~1 \le a_i \le m~.

Subtask

• Subtask ~1~ ~(20\%)~: ~n \le 5, m \le 10~.
• Subtask ~2~ ~(20\%)~: ~m \le 1000~.
• Subtask ~3~ ~(30\%)~: ~a_i = m~
• Subtask ~4~ ~(30\%)~: 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

Cho ~t~ truy vấn và giá trị ~mod~ ~(1 \le mod \le 2*10^9)~, mỗi truy vấn gồm hai số nguyên dương ~n~, ~k~. Kí hiệu ~C(k,n)~ là tổ hợp chập ~k~ của ~n~, hãy in ra ~C(k,n)~ cho mỗi truy vấn tương ứng. Do kết quả có thể rất lớn nên hãy in nó sau khi lấy phần dư cho ~mod~.

Subtask

• Sub ~1~: ~t \le 10^5~, ~1 \le k \le n \le 2000~. (30%)
• Sub ~2~: ~t = 1~, ~1 \le k \le n \le 10^5~. (30%)
• Sub ~3~: ~t \le 10^5~, ~1 \le k \le n \le 10^5~, ~mod = 10^9+7~. (40%)

Input

• Dòng đầu tiên gồm một số nguyên dương ~sub~ miêu tả subtask mà test này tương ứng. (~1 \le sub \le 3~)
• Dòng thứ hai gồm hai số nguyên dương ~t~ và ~mod~.
• ~t~ dòng sau, mỗi dòng gồm hai số nguyên dương ~n~, ~k~ (~k \le n~) miêu tả truy vấn tương ứng.

Output

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

Sample Test

Input:

1
3 2345
6 4
8 4
15 8

Output:

15
70
1745

Sơ đồ quân đội của đế chế ~X~ được thiết lập ở dạng cây. Có ~n~ sĩ quan được đánh số từ ~1~ tới ~n~, mỗi người đều có một cấp trên trực tiếp, riêng sĩ quan ~1~ - là chỉ huy tối cao - thì không.

Sĩ quan ~x~ được coi là cấp dưới (trực tiếp hoặc gián tiếp) của sĩ quan ~y~ nếu một trong hai điều kiện sau đúng:

• Sĩ quan ~y~ là cấp trên trực tiếp của sĩ quan ~x~.
• Cấp trên trực tiếp của sĩ quan ~x~ là cấp dưới của sĩ quan ~y~.

Quân đội có cách truyền lệnh rất riêng, nó được miêu tả giống thuật toán ~DFS~.

Giả sử, ta có sơ đồ quan hệ sau:

• Nếu sĩ quan ~1~ truyền lệnh, các sĩ quan sẽ nhận được lệnh theo thứ tự: ~[1,2,3,5,6,8,7,9,4]~.
• Nếu sĩ quan ~3~ truyền lệnh, các sĩ quan sẽ nhận được lệnh theo thứ tự: ~[3,5,6,8,7,9]~.
• Nếu sĩ quan ~9~ truyền lệnh, các sĩ quan sẽ nhận được lệnh theo thứ tự: ~[9]~.

Có một lưu ý quan trọng, đó là nếu sĩ quan ~u~ có ~k~ cấp dưới trực tiếp: ~v_1,v_2,...,v_k~ thì sẽ truyền lệnh cho ~v_i~ theo thứ tự từ bé đến lớn.

Bạn cần giúp chỉ huy tối cao trả lời ~q~ truy vấn, truy vấn thứ ~i~ có dạng ~(u_i,k_i)~, hỏi rằng nếu sĩ quan ~u_i~ truyền tin, sĩ quan nhận tin thứ ~k_i~ là ai.

Input

• Dòng đầu chứa hai số nguyên ~n, q~ ~(n,q \le 2 \times 10^5)~.
• Dòng sau gồm ~n-1~ số, ~p_2,p_3,...,p_n~, ~p_i~ miêu tả cấp trên trực tiếp của nhân viên thứ ~i~.
• ~q~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương ~u_i,k_i~, miêu tả truy vấn thứ ~i~.

Output

• Gồm ~q~ dòng trả lời cho ~q~ truy vấn, in ra sĩ quan thứ ~k_i~ nhận tin nếu người truyền tin là sĩ quan ~u_i~, ngược lại nếu không đủ ~k_i~ người nhận được tin thì in ra ~-1~.

Sample Input 1

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

Sample Output 1

3
6
8
-1
9
4

Cho cây gồm ~n~ đỉnh, đỉnh thứ ~i~ có trọng số là ~s_i~.

Hãy tìm một đường đi sao cho tổng trọng số các đỉnh trên cây là lớn nhất.

Input

• Dòng đầu chứa hai số nguyên ~n~ ~(n \le 10^5)~.
• Dòng thứ hai gồm ~n~ số, số thứ ~i~ là ~s_i~ tương đương với trọng số của đỉnh thứ ~i~ ~(|s_i| \le 10^9)~.

• ~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,

  Output

• Gồm một dòng chứa một số là tổng trọng số lớn nhất tìm được.

Sample Input 1

5
-1 2 3 4 -5
1 2
1 3
1 4
4 5

Sample Output 1

6

Cho một cây có trọng số gồm ~n~ đỉnh, được đánh số từ ~1~ đến ~n~, trọng số của đỉnh thứ ~i~ là ~a_i~. Gọi ~S(i)~ là dãy các trọng số của các đỉnh trên đường đi từ ~1~ tới ~i~.

Với mỗi ~i~, hãy tìm độ dài dãy con tăng dài nhất của ~S(i)~.

Input

• Dòng đầu chứa số nguyên ~n~ ~(n \le 2 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ miêu tả trọng số của các đỉnh ~(1 \le a_i \le 10^9)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1≤u,v≤n; u≠v)~ mô tả một cạnh của cây nối hai đỉnh ~u~ và ~v~.

Output

• In ra ~n~ số nguyên là độ dài của dãy con tăng dài nhất của ~S(i)~.

Subtask

• Subtask ~1~: ~a_i \le 100~. ~(30\%)~
• Subtask ~2~: Không có đỉnh nào có quá hai cạnh nối. ~(30\%)~
• Subtask ~3~: Không có ràng buộc gì thêm. ~(40\%)~

Sample Input 1

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

Sample Output 1

1
2
3
3
4
4
5
2
2
3

Cho một cây có trọng số gồm ~n~ đỉnh, được đánh số từ ~1~ đến ~n~. Dễ thấy là với mỗi cặp đỉnh ~(u,v)~ ta luôn có duy nhất một đường đi đơn từ đỉnh ~u~ đến ~v~.

Hãy đếm xem trong ~n^2~ cặp đỉnh ~(u,v)~, có bao nhiêu cặp đỉnh mà trọng số trên đường đi từ ~u~ đến ~v~ tạo thành một dãy tăng chặt?

Input

• Dòng đầu chứa hai số nguyên ~n~ ~(n \le 2 \times 10^5)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u, v, w~ ~(1≤u,v≤n; u \neq v ; 0≤w≤10^9)~ mô tả một cạnh của cây nối hai đỉnh ~u~ và ~v~ với trọng số ~w~.

Output

• In ra một số nguyên duy nhất là số cặp cần tìm.

Sample Input 1

3
1 2 3
2 3 8

Sample Output 1

5

Sample Input 2

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

Sample Output 2

9

Có ~k~ con mèo sống ở trên một cái cây do Ivan Tèo quản lý. Cái cây gồm ~n~ đỉnh được đánh số từ ~1~ tới ~n~, mỗi đỉnh chứa nhiều nhất một chú mèo.

Do lo sợ Khoi sẽ tới và ăn thịt các chú mèo của mình, Ivan Tèo quyết định thuê các robot MDuc về để bảo vệ các chú mèo. Cơ chế bảo vệ của robot MDuc rất đặc biệt, khi đặt robot ở một nút trên cây, robot ấy sẽ chỉ bảo vệ các chú mèo có khoảng cách gần nhất với cậu. MDuc cũng có thể được đặt ở chung nút với chú mèo, và trong trường hợp đó, tất nhiên anh ta sẽ chỉ bảo vệ chú mèo chung nút.

Do giá của một robot MDuc khá cao, hãy giúp Ivan Tèo tìm cách đặt ít robot nhất có thể sao cho tất cả các chú mèo đều được bảo vệ.

Input

• Dòng đầu chứa hai số nguyên ~n,k~ ~(k \le n \le 2 \times 10^5)~.
• ~n-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1≤u,v≤n; u≠v)~ mô tả một cạnh của cây nối hai đỉnh ~u~ và ~v~.
• Dòng cuối cùng gồm ~k~ số nguyên dương phân biệt ~a_i~ là các nút có một chú mèo.

Output

• In ra số robot nhỏ nhất cần dùng.

Subtask

• Subtask ~1~: ~n \le 3\times 10^5~ và nút ~i~ nối với nút ~i+1~ trên cây. ~(20\%)~
• Subtask ~2~: ~k \le 15, n \le 3 \times 10^5~. ~(30\%)~
• Subtask ~3~: ~n \le 2000~. ~(25\%)~
• Subtask ~3~: ~n \le 3 \times 10^5~. ~(25\%)~

Sample Input 1

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

Sample Output 1

2

Explanation 1

Đặt ở đỉnh ~1~ và ~3~.

Sau khi không thể tiếp cận các chú mèo của Ivan Tèo, Khoi đã tới một nơi khác để hái nấm.

Các cây nấm cũng được mọc trên một cái cây gồm ~n~ đỉnh và ~n-1~ cạnh. Cạnh thứ ~i~ nối hai đỉnh ~u_i~ và ~v_i~ mang trọng số là ~w_i~. Mỗi nút sẽ chứa một cây nấm. Do là nấm hoang nên không có ai thuê robot MDuc canh gác, vậy nên Khoi có thể tới hái nấm bất cứ khi nào.

Vì sức lực có hạn, Khoi sẽ đi hái nấm trong ~q~ lần, lần hái thứ ~i~ cậu sẽ tới vào ngày ~d_i~ và khởi hành từ đỉnh ~u_i~ của cây, sau đó hái các cây nấm với khoảng cách không quá ~k_i~, biết rằng khoảng cách giữa hai đỉnh ~u~ và ~v~ là max trọng số các cạnh của đường đi ngắn nhất từ ~u~ tới ~v~.

Do không muốn Khoi quay lại bắt những chú mèo của mình, Ivan Tèo đã làm phép để cho sau khi bị hái, các cây nấm sẽ tự động sinh trưởng trở lại và sẽ mọc lại hoàn toàn trong ~X~ ngày nếu như nó không bị Khoi tới hái. Điều này có nghĩa, nếu cây nấm bị hái ở ngày ~d~ và trong ~X~ ngày sau đó nó không bị tìm đến lần nữa, thì ở ngày ~d+X~ nó sẽ mọc lại thành một cây nấm mới.

Khoi không để ý lắm tới điều này, vậy nên bạn hãy giúp Khoi tính được số nấm mà mình hái được trong mỗi lần nhé!

Input

• Dòng đầu chứa số nguyên ~n~ ~( n \le 3 \times 10^5)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i, v_i, w_i~ ~(1≤u,v≤n; u≠v; w_i \le 10^9)~ mô tả một cạnh của cây nối hai đỉnh ~u_i~ và ~v_i~ với độ dài ~w_i~.
• Dòng tiếp theo gồm hai số nguyên dương ~q~ và ~X~ miêu tả số lần hái nấm và số ngày để nấm mọc lại ~(q \le 3 \times 10^5, X \le 10^9)~.
• ~q~ dòng sau, dòng thứ ~i~ gồm ba số nguyên ~d_i,u_i,k_i~ miêu tả truy vấn thứ ~i~ ~(d_i \le 10^9, k_i \le 10^9)~.
• Các ~d_i~ tăng dần.

Output

• Với mỗi truy vấn, in ra số nấm mà Khôi hái được trong lần đó.

Subtask

• Subtask ~1~: ~n,q \le 2000 ~. ~(20\%)~
• Subtask ~2~: ~n \le 3\times 10^5~ và nút ~i~ nối với nút ~i+1~ trên cây. ~(30\%)~
• Subtask ~3~: ~X = 1~. ~(20\%)~
• Subtask ~4~: Không có giới hạn gì thêm. ~(30\%)~

Sample Input 1

3
1 2 4
3 1 7
3 3
4 2 7
6 1 15
15 2 3

Sample Output 1

3
0
1

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

Với mỗi đỉnh ~u~, hãy xác định xem có bao nhiêu đỉnh ~v~ là tổ tiên của ~u~ thỏa mãn ~a_v~ > ~a_u~.

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~ miêu tả giá trị ~a_i~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~x,y~ miêu tả cạnh của cây.

Constraint

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

Subtask

• Subtask ~1~ ~(40\%)~: ~n \le 2000~.
• Subtaks ~2~ ~(60\%)~: Không có điều kiện gì thêm.

Output

• Gồm ~n~ số nguyên trên một dòng, số thứ ~i~ là kết quả của đỉnh thứ ~i~.

Sample Input 1:

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

Sample Output 1:

0 1 0 2 1

Cho một dãy số ~a_1, a_2, ... a_N~. Một nghịch thế là một cặp số ~u, v~ sao cho ~u < v~ và ~a_u > a_v~. Nhiệm vụ của bạn là đếm số nghịch thế.

Input

• Dòng đầu ghi số nguyên dương ~N~ ~(N \leq 10^5)~.
• Dòng sau gồm ~N~ số nguyên dương ~a_i~ ~( 1 ≤ a_i ≤ 10^5 )~.

Output

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

Subtasks

• Subtask 1: ~n \leq 5000~. (50%)
• Subtask 2: Không giới hạn gì thêm.

Sample Input 1

3
3 1 2

Sample Output 1

2

Cho một cây vô hướng gồm ~n~ đỉnh.

Hãy tìm đường đi dài nhất ở trên cây, biết rằng độ dài đường đi từ ~u~ tới ~v~ chính bằng số cạnh trên đường đi đơn từ ~u~ tới ~v~.

Input

• Dòng đầu chứa hai số nguyên ~n~ ~(1 \le n \le 10^5)~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ miêu tả cạnh của cây.

Output

• Đưa ra khoảng cách xa nhất của hai đỉnh bất kì trên cây.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

3

Cho một cây vô hướng gồm ~n~ đỉnh.

Định nghĩa "bán kính của một đỉnh" hay ~R(u)~ là số cạnh ít nhất cần dùng để đỉnh này có thể tới thăm bất kì đỉnh nào trên cây.

Hãy tìm ~R(u)~ nhỏ nhất, nếu có nhiều đỉnh ~u~ thỏa mãn, in ra tất cả các đỉnh đó theo thứ tự từ bé tới lớn.

Input

• Dòng đầu chứa hai số nguyên ~n~ ~(1 \le n \le 10^5)~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ miêu tả cạnh của cây.

Output

• Dòng đầu tiên gồm hai số nguyên dương ~r~ và ~k~ lần lượt là bán kính nhỏ nhất và số đỉnh thỏa mãn.
• Dòng thứ hai gồm ~k~ số nguyên dương là các đỉnh thỏa mãn theo thứ tự tăng dần.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

2 2
1 3

Cho một cây vô hướng gồm ~n~ đỉnh. Đỉnh thứ ~i~ có giá trị là ~a_i~.

Hai đỉnh ~u~ và ~v~ được gọi là chung nhóm nếu như giá trị ~a_u~ và ~a_v~ của chúng có chung số lượng bit ~1~. Ví dụ, nếu ~a_u = 6 = (110)_2~ và ~a_v = 9 = (1001)_2~ thì chúng chung nhóm do cùng có ~2~ bit ~1~. Ngược lại nếu cặp giá trị là ~(7,8)~ thì không.

Hãy tìm ra khoảng cách dài nhất giữa hai đỉnh bất kì chung nhóm, biết rằng độ dài đường đi từ ~u~ tới ~v~ chính bằng số cạnh trên đường đi đơn từ ~u~ tới ~v~.

Input

• Dòng đầu chứa hai số nguyên ~n~ ~(1 \le n \le 2 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả giá trị dãy ~a~, ~(a_i \le n)~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ miêu tả cạnh của cây.

Output

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

Sample Input 1

4
4 3 2 2
2 1
2 3
2 4

Sample Output 1

2

Cho một cây vô hướng gồm ~n~ đỉnh ~(1 \le n \le 1e5)~ và ~m~ đỉnh đặc biệt ~(1 \le m \le n)~, kèm một số ~k~ nguyên dương bất kì ~(1 \le k \le n)~. Một đỉnh ~u~ được gọi là tốt nếu như với mọi đỉnh ~v~ thuộc tập ~m~ đỉnh đặc biệt, ta luôn có ~dist(u,v) \le k~. Ở đây, ~dist(u,v)~ là khoảng cách của đỉnh ~u~ và ~v~ trên cây, hay bằng số cạnh trên đường đi ngắn nhất từ đỉnh ~u~ tới đỉnh ~v~. Hãy đếm xem có bao nhiêu đỉnh được coi là "tốt".

Input:

• Dòng đầu gồm 3 số ~n,m,k. (1 \le m \le n \le 10^5, 1 \le k \le 10^5).~
• ~n-1~ dòng sau mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ là cạnh nối từ đỉnh ~u~ tới ~v~.
• Dòng cuối gồm ~m~ số miêu tả các đỉnh đặc biệt.

Output:

• Số đỉnh tốt.

Sample Test

Input:

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

Output:

3

Giải thích:

• 3 đỉnh tốt là đỉnh 3,4,5.

Ràng buộc

• Subtask 1: ~n <= 500.~ (50%)
• Subtask 2: Với mỗi thành phố, chỉ có tối đa 2 con đường nối tới các thành phố khác.
• Subtask 3: Không giới hạn gì thêm. (20%).

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~, cạnh thứ ~i~ ~(1 \le i \le n-1)~ có trọng số là ~w_i~.

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

Hãy tìm ~max(dist(u,v) \times gcd(a_u,a_v)) \forall u,v \in [1,n]~.

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 ba số nguyên dương ~u_i,v_i,w_i~ miêu tả cạnh thứ ~i~ của cây.

Constraint

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

Subtask

• Subtask ~1~ ~(30\%)~: ~n \le 2000~.
• Subtask ~2~ ~(20\%)~: ~a_i = 1; \forall i \in [1,n]~
• Subtask ~3~ ~(30\%)~: ~n,a_i \le 4 \times 10^4~
• Subtask ~4~ ~(20\%)~: 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:

2
10 10
1 2 10

Sample Output 1:

100

Cho một cây gồm ~n~ đỉnh và số nguyên dương ~k~.

Bạn cần xóa một vài cạnh ở trên cây. Sau đó, cây sẽ trở thành một "rừng" với nhiều cây con, tập cạnh bạn xóa được gọi là tốt nếu như tất cả các cây con đều có đường kính không lớn hơn ~k~.

Hãy đếm số tập cạnh thỏa mãn.

Input

• Dòng đầu gồm hai số nguyên dương ~n,k~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ miêu tả cạnh của cây.

Output

• In ra số tập cạnh thỏa mãn theo module ~998244353~.

Constraints

• ~1 \le n,k \le 5 \times 10^3~.

Subtask

• ~30\%~ số điểm có ~n \le 20~.
• ~30\%~ số điểm có ~n \le 100~.
• ~40\%~ số điểm có ~n \le 5000~

Sample Input 1

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

Sample Output 1

24

Cho một cây gồm ~n~ đỉnh với các trọng số trên cạnh.

Bạn có ~q~ truy vấn có dạng như sau:

• Nhân thử các cạnh nối với đỉnh ~u_i~ lên ~x_i~ lần, hỏi đường kính của cây mới có độ dài là bao nhiêu.
• Lưu ý là ta chỉ nhân thử, sau truy vấn này thì cây về nguyên bản.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ và ~w~ miêu tả cạnh ~(u,v)~ có độ dài ~w~ của cây.
• Dòng tiếp theo gồm số nguyên dương ~q~.
• ~q~ dòng sau, mỗi dòng gồm hai số nguyên dương ~u_i,y_i~ miêu tả truy vấn.

Output

• Với mỗi truy vấn, in ra độ dài đường kính của cây mới trong giả định.

Constraints

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

Subtask

• ~30\%~ số điểm thỏa mãn ~n \le 2000~.
• ~30\%~ số điểm thỏa mãn cây là đường thẳng.
• ~40\%~ số điểm thỏa mãn ~n \le 10^5~

Sample Input 1

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

Sample Output 1

11
18
27