Sau khi thi VOI xong, vì xõa hơi lố nên LeVanThuc đã hết tiền tiêu tết. Vì vậy, anh quyết định rủ huynhchiton981 cùng đi cướp ngân hàng.

Thành phố QN có ~n~ ngân hàng nằm cạnh nhau, nếu cướp ngân hàng thứ ~i~ sẽ được số tiền là ~a_i~, tuy nhiên, nếu cướp một mình thì chắc chắn anh bạn LeVanThuc của chúng ta sẽ được ăn cơm nhà nước ngay và luôn, vì vậy bọn họ lập ra kế hoạch như sau: chọn ra ~k~ ngân hàng liên tiếp, LeVanThuc sẽ cướp ngân hàng có ~a[i]~ cao nhất còn huynhchiton981 sẽ nghi binh vào ~k-1~ ngân hàng còn lại. Vì để có một cái tết ấm no, LeVanThuc sẽ liệt kê lần lượt ra toàn bộ ~n-k~ kế hoạch để hành động. Bạn hãy giúp anh ấy nhé.

INPUT

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n, k ( n \leq 10^6, k \leq n)~ .
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i(a_i \leq 10^9)~ .

OUTPUT

• ~1~ dòng gồm ~n-k~ số nguyên dương là số tiền lớn nhất trong đoạn từ ~i~ đến ~i+k-1~.

Sample Input

7 3
1 4 2 3 6 5 9

Sample Output

4 4 6 6 9

Subtask

• ~30~% số test với ~n \leq 10^3~
• ~70~% số test còn lại không có ràng buộc thêm

---

~5~ người bạn tên T lại trốn học đội tuyển rồi. Để trốn khỏi sự truy tìm của cô Vang và cô Kiều, họ đã trốn trong một dãy nhà gồm ~n~ căn phòng cùng ~n-1~ hành lang sao cho phòng nào cũng có đường đi đến nhau. Đặc biệt hơn, ~5~ người bọn họ trốn trong ~5~ căn phòng kề nhau và tạo thành một hình chữ T. Để tiện cho việc tìm kiếm thì bạn hãy giúp ~2~ cô đếm có bao nhiêu bộ phòng thỏa mãn điều kiện trên nhé.

INPUT

• Dòng đầu tiên gồm ~1~ số nguyên dương n là số căn phòng ~(n \leq 10^5)~
• Trong ~n-1~ dòng tiếp theo, mỗi dòng gôm ~2~ số ~u, v~ là ~2~ phòng mỗi hành lang nối.

OUTPUT

• ~1~ số nguyên là số vị trí thỏa mãn.

Sample Input

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

Sample Output

16

Minh Họa

Các tập {~1,2,3,4,5~}, {~3,2,4,6,7~} là một số tập thõa mãn.

Subtask

• ~30~% số test có ~n \leq 10^2~.
• ~70~% số test còn lại không có ràng buộc thêm

Sau khi LeVanThuc đột nhập thành công vào ngân hàng, anh ấy tìm thấy ~n~ cái két sắt liên tiếp nhau, két thứ ~i~ chứa số tiền ~a_i~. Anh ta cũng có 1 chiếc chìa khóa có thể kích hoạt một lần. Nếu kích hoạt chìa khóa với mật mã là ~k~ thì số tiền lấy được ở mỗi két sẽ là ~gcd(a_i,k)~. Đụng đến ~gcd~ anh ấy lại bắt đầu ngứa nghề và tự hỏi bản thân rằng, nếu giả sử chìa khóa được kích hoạt mật mã là ~k~ thì tổng số tiền lấy được ở đoạn từ ~l~ đến ~r~ sẽ là bao nhiêu? Bạn hãy cùng anh ấy giải quyết bài toán này nhé.

INPUT

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n, q ( n \leq 10^5, q \leq 10^5)~ .
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i(a_i \leq 10^7)~ .
• ~q~ dòng tiếp theo mỗi dòng gồm ~3~ số nguyên dương tương ứng là ~l_i~, ~r_i~ và ~k_i~ ~(l_i,r_i \leq n, k \leq 10^4)~.

OUTPUT

• ~q~ dòng gồm ~q~ số nguyên dương là số tiền lấy được với mỗi giả sử của LeVanThuc.

Sample Input

10 5
16 100 51 21 31 32 65 88 1 95 
10 10 10
2 4 4
5 8 6
9 10 5
9 10 3

Sample Output

5
6
6
6
2

Subtask

• ~30~% số test với ~n,q \leq 10^3~
• ~70~% số test còn lại không có ràng buộc thêm

Công ty LQĐ gồm có ~n~ người tạo thành một mạng lưới liên thông gồm ~n-1~ mối liên hệ với nhau. Trong công ty có ~m~ người là nhân viên chủ chốt. Độ hiệu quả quan hệ của một người với hệ số ~k~ là số nhân viên chủ chốt có khoảng cách đến nhân viên này chia hết cho hệ số đó. Nhân dịp cuối năm, tổng giám đốc sẽ đánh giá hiệu quả quan hệ của một số người. Với hi vọng được lên chức, huynhchiton981 quyết định nhận việc này, bạn hãy giúp anh ấy nhé.

INPUT

• Dòng đầu tiên gồm ~3~ số nguyên dương ~n, m, q ~ là số nhân viên, số nhân viên chủ chốt, và số kế hoạch khảo sát. ~( n \leq 2*10^4, m \leq n, q \leq 5*10^6)~ .
• Dòng tiếp theo gồm ~m~ số nguyên dương là các nhân viên đặc biệt.
• ~n-1~ dòng tiếp theo mỗi dòng gồm ~2~ số ~u,v~ là một cặp nhân viên có quan hệ với nhau.
• ~q~ dòng tiếp theo, mỗi dòng gồm ~2~ số ~u, k~ là nhân viên cần khảo sát và hệ số khảo sát.

OUTPUT

• ~q~ dòng với dòng ~i~ là hiệu quả quan hệ của khảo sát thứ ~i~.

Sample Input

15 5 6
15 7 3 8 1 
2 3
11 9
12 8
6 14
9 15
12 10
9 13
3 11
6 4
9 6
6 5
7 12
9 1
14 10
4 4
5 5
2 4
5 5
1 5
2 1

Sample Output

1
2
4
2
1
5

Minh Họa

Các nhân viên thỏa khảo sát ~3~ là : ~1,15~ với khoảng cách ~4~ và ~8,7~ với khoảng cách ~8~

Subtask

• ~20~% số test có ~n,m \leq 10^3~.
• ~30~% số test khác có thỏa mỗi nhân viên ~i~ khác ~1~ đều có quan hệ với nhân viên thứ ~i/2~.
• ~50~% số test còn lại không có ràng buộc thêm