Cho số nguyên dương ~n~ có tập hợp các ước nguyên tố là ~A~, hỏi có bao nhiêu số chính phương không vượt quá ~n~ mà tập ước nguyên tố của nó là tập con của ~A~?

Input

Số nguyên dương ~n~ với ~1 \le n \le 10^{14}.~

Output

Số lượng cần tìm.

Sample input

36

Sample output

5

Giải thích: các số thỏa mãn là ~1, 4, 9, 16, 36~.

Cho hai chuỗi ký tự ~s, t~ có cùng độ dài. Mỗi bước cho phép chọn một vị trí ~i~ nào đó và thực hiện SHIFT ký tự ~s_i~ hoặc ~t_i~ lên ~1~ bước, theo thứ tự: ~a \to b \to ... \to x \to y \to z \to a.~ Hỏi cần ít nhất mấy thao tác để làm cho hai chuỗi bằng nhau?

Input

Hai dòng gồm thông tin của hai chuỗi, độ dài giống nhau và không quá ~10^5.~

Output

Số bước tối thiểu cần thực hiện.

Sample input 1

abc
def

Sample output 1

9

Sample input 2

aa
az

Sample output 2

1

Giải thích: ta thực hiện SHIFT vị trí 1 ở ~s~ tất cả ~3~ lần, tương tự với vị trí ~2,3~ nên cần có ~3.3=9~ lần; trong VD2, ta thực hiện SHIFT vị trí 2 ở ~t~ tất cả ~1~ lần thì ~z \to a~.

Mít và Xoài là các SV xuất sắc của thầy Luna. Sau khi dạy xong một tuyệt chiêu về phép đếm trong lập trình, thầy đã ra một bài rất tâm đắc cho Mít và Xoài làm. Hai bạn được cho bảng ô vuông kích thước ~n \times n~, mỗi ô được tô bởi một trong ba màu: xanh - đỏ - vàng sao cho không có hàng nào và không có cột nào được tô tất cả các ô bởi màu đỏ. Đánh số các hàng, cột theo thứ tự từ trái sang phải và dưới lên trên. Ban đầu có sẵn ~k~ ô được thầy Luna tô màu xanh hoặc vàng trước, cho biết danh sách tọa độ của chúng là thứ tự của hàng, cột của ô được tô. Nhiệm vụ của Mít và Xoài là đếm xem có tất cả bao nhiêu cách tô thỏa mãn điều kiện đề bài và kết quả có thể rất lớn nên lấy modulo ~10^9+7.~ Đã nhiều ngày nhưng các bạn vẫn chưa đếm xong, bạn có thể giúp hai bạn ấy được không?

Input

Dòng đầu tiên gồm hai số nguyên dương ~n,k~ trong đó ~1 \le n \le 10~ và ~0 \le k \le \min \{ n^2, 10 \}~. Các dòng tiếp theo mô tả tọa độ của các ô được tô màu trước với dạng ~x\, y \, z~ trong đó ~x,y~ là chỉ số hàng, cột, còn ~z~ là màu: ~z=1~ là xanh, ~z=2~ là vàng.

Output

Đáp số của bài toán.

Sample input

2 0

Sample output 1

56

Sample input 2

3 2
1 1 2
2 3 1

Sample output 2

2034

Cho một cây ~G=(V,E)~ có ~n~ đỉnh. Chia các cạnh của ~G~ thành ~k~ đường đi sao cho mỗi cạnh thì thuộc đúng một đường đi và hai đường đi tùy ý thì đều có đỉnh chung (các đường này có độ dài tùy ý, không nhất thiết phải đồng đều nhau). Hỏi có thể thực hiện được hay không, và nếu được thì số lượng lớn nhất, nhỏ nhất của số đường đi là bao nhiêu?

Input Dòng đầu tiên gồm số nguyên dương ~n~ với ~3 \le n \le 10^5.~ Trong ~n-1~ dòng tiếp theo, mỗi dòng gồm một cặp số ~(a,b)~ nguyên dương với ~1 \le a, b \le n~ cho biết đỉnh ~a,b~ nối nhau. Dữ liệu đảm bảo là một cây.

Output

Nếu không thể thực hiện được thì in ra ~-1~. Còn nếu tồn tại cách thực hiện thì lần lượt in ra giá trị lớn nhất, nhỏ nhất của ~k~, số đường đi có thể phân chia được.

Sample input

3
1 2
1 3

Sample output

2 1

Giải thích Trong Ví dụ, ta thấy rằng có thể phân hoạch thành ~2~ đường đi gồm ~(1,2),(1,3)~ hoặc ~1~ đường đi là ~(2,1,3).~

Ta gọi ~k~ thanh gỗ độ dài ~l_1, l_2, ... , l_k~ là đẹp nếu có cách phân chia chúng thành ba tập khác rỗng, sau đó ghép nối các thanh gỗ trong cùng một tập thành một đoạn có độ dài là tổng độ dài các thanh gỗ trong tập, khi đó độ dài của ba đoạn đó là độ dài ba cạnh của một tam giác.

Hiện có ~n~ thanh gỗ xếp thành một hàng từ trái sang phải với độ dài tương ứng là ~d_1, d_2, ... , d_n~, các thanh gỗ có độ dài đôi một khác nhau. Với số nguyên ~k \ge 3~, ta cần đếm xem có bao nhiêu cách chọn ~k~ thanh gỗ liên tiếp nhau mà ~k~ thanh gỗ này là đẹp.

Input

Dòng đầu tiên gồm các số ~n,k~ với ~3 \le k \le n \le 10^5.~

Dòng tiếp theo gồm ~n~ số nguyên dương đôi một khác nhau và không vượt quá ~10^9.~

Output

Số cách chọn thỏa mãn đề bài.

Sample input

6 3
1 3 4 2 5 9

Sample output

2

Subtasks

• Có ~20\%~ số test có ~k = n = 3;~

• Có ~20\%~ số test khác có ~k = n = 4;~

• Có ~20\%~ số test khác có ~k = n \le 10;~

• Có ~20\%~ số test khác có ~k \le n \le 1000;~

• Có ~20\%~ số test còn lại là theo giới hạn ban đầu.

Mùa này IUH rất hay cúp điện. Ở IUH có ~N~ tòa nhà được đánh số từ ~1~ đến ~N~. Có ~M~ đường dây dẫn có thể xây dựng được, đường dây dẫn thứ ~i~ kết nối hai tòa nhà ~U_i~ và ~V_i~ với chi phí xây dựng là ~W_i~.

Các sếp của IUH có kế hoạch xây dựng lưới điện riêng để cung cấp điện cho toàn bộ các tòa nhà. Họ dự định sẽ đặt hai trạm phát điện tại hai tòa nhà khác nhau, và xây dựng một số đường dây dẫn để các tòa nhà đều được cung cấp điện. Một tòa nhà ~u~ được cung cấp điện nếu như tòa nhà ~u~ được đặt trạm phát điện, hoặc có một đường dây dẫn nối tòa nhà ~u~ với một tòa nhà khác được cung cấp điện.

Họ đã đề xuất ~Q~ phương án đặt hai trạm phát điện. Với phương án thứ ~j~, hai trạm phát điện sẽ được đặt lần lượt tại hai tòa nhà ~A_j~ và ~B_j~. Với mỗi phương án, họ cần tính tổng chi phí tối thiểu để xây dựng các đường dây dẫn sao cho các tòa nhà đều được cung cấp điện. Yêu cầu: bạn hãy giúp chính phủ thực hiện các phương án trên để phục vụ nhu cầu của SV IUH nhé.

Input

Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ với ~1≤N≤4×10^3, 1≤M≤4 \times 10^5~ là số tòa nhà của IUH và số lượng đường dây dẫn có thể xây dựng.

Dòng thứ ~i~ trong ~M~ dòng tiếp theo chứa ba số nguyên ~U_i, V_i~ và ~W_i~ với ~1≤U_i, V_i≤N, U_i≠V_i, 1≤W_i≤10^9~ mô tả đường dây dẫn thứ ~i~. Dữ liệu vào đảm bảo rằng nếu xây dựng toàn bộ ~M~ đường dây, từ tòa nhà bất kì đều có thể truyền điện đến một tòa nhà khác thông qua các đường dây dẫn.

Dòng tiếp theo chứa một số nguyên ~Q~ với ~1≤Q≤2 \times 10^5~ là số lượng phương án mà chính phủ đã đề xuất. Dòng thứ ~j~ trong ~Q~ dòng tiếp theo chứa hai số nguyên ~A_j~ và ~B_j~ với ~1≤A_j, B_j≤N, A_j≠B_j~ mô tả phương án thứ ~j~.

Output

Kết quả gồm ~Q~ dòng, dòng thứ ~j~ in ra một số nguyên duy nhất là tổng chi phí tối thiểu xây dựng các đường dây dẫn sao cho mỗi tòa nhà đều được cung cấp điện với phương án thứ ~j~.

Sample input

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

Sample output

14
13

Hình ảnh bên minh họa phương án thứ nhất và thứ hai của test ví dụ (cạnh nét đứt là các đường dây dẫn có thể xây dựng, cạnh nét liền là các đường dây dẫn cần xây dựng, đỉnh đen là các thành phố được đặt trạm phát điện).

Subtasks

• 10% số điểm ứng với ~𝑁, 𝑀 ≤ 15, 𝑄 ≤ 100~
• 25% số điểm ứng với ~𝑄 = 1~
• 40% số điểm ứng với ~𝑄 ≤ 3000~
• 25% số điểm ứng với giới hạn đề bài.

Bạn được tham gia trò chơi với dãy gồm ~n~ số nguyên không âm. Trong trò chơi này bạn phải chia dãy đã cho ra thành ~k+1~ đoạn khác rỗng. Để thu được ~k+1~ đoạn như thế, bạn cần lặp lại các bước sau đây ~k~ lần:

1. Chọn một đoạn tuỳ ý với nhiều hơn một phần tử (đầu tiên bạn chỉ có một đoạn - đó chính là dãy ban đầu).

2. Chọn một vị trí nào đó giữa hai phần tử của đoạn đã chọn để chia nó ra làm hai đoạn mới khác rỗng.

Mỗi lần thực hiện xong hai bước này bạn nhận được một điểm số bằng tích của hai tổng các số trong hai đoạn mới chia ra. Yêu cầu: Với cách chơi như trên, bạn hãy tìm cách chơi để đạt được tổng điểm lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ với ~k+1≤n ≤3000~;

• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ với ~0 ≤ a_i ≤ 10^4, 1 ≤ i ≤ n~ là các phần tử của dãy số.

Output

Một số nguyên duy nhất là tổng điểm lớn nhất mà bạn đạt được.

Sample input

7 3
1 3 4 0 2 3 4

Sample output

108

Giải thích

Trong ví dụ bạn có thể giành được 108 điểm theo cách sau:

• Đầu tiên bạn có dãy số (1, 3, 4, 0, 2, 3, 4) gồm 1 đoạn. Bạn chia dãy ra thành hai đoạn sử dụng điểm chia sau phần tử thứ sáu và nhận được: ~(1 + 3 + 4 + 0 + 2 + 3) × 4 = 52~ điểm.
• Bạn đang có hai đoạn (1, 3, 4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ hai và nhận được: ~(1 + 3) × (4 + 0 + 2 + 3) = 36~ điểm.
• Bạn đang có ba đoạn (1, 3), (4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ tư và nhận được: ~(4 + 0) × (2 + 3) = 20~ điểm.

Như vậy, sau 3 bước thực hiện nói trên bạn chia dãy số thành 4 đoạn (1, 3), (4, 0), (2, 3), (4) và nhận được: ~52 + 36 + 20 = 108~ điểm.

Subtasks

• Có 70% số test tương ứng với 70% số điểm của bài có ~n ≤ 300;~
• Có 30% số test còn lại tương ứng với 30% số điểm của bài có ~n ≤ 3000.~