Ngày mai lớp của ~Lona~ sẽ có buổi kiểm tra Tin học. ~Lona~ rất lo lắng vì đề thầy cho rất khó và hại não. Do đó để có thể được thêm điểm cộng cho bài kiếm tra này thì ~Lona~ đã quyết định sẽ xung phong giải bài tập về nhà.

Thầy giáo cho các bạn trong lớp một số nguyên dương ~n~ và yêu cầu đếm tất cả các số nguyên dương ~s~ thỏa mãn:

• ~s \le n~
• ~s = p^3 \times q^3~ với ~p~ và ~q~ là các số nguyên tố phân biệt.

Loay hoay mãi nhưng ~Lona~ vẫn chưa thể giải được nên đành nhờ các bạn giúp đỡ. Là một lập trình thiên tài, bạn hãy giúp đỡ ~Lona~ nhé.

Input

Dòng duy nhất nhập vào một số nguyên dương ~n~ ~(1 \le n \le 10^{18})~.

Output

In ra yêu cầu đề bài: số số nguyên dương ~s~ thỏa mãn.

Scoring

Sample Input 1

1000

Sample Output 1

2

Notes

Có ~2~ số thỏa mãn đề bài:

• ~216 = 2^3 \times 3^3~
• ~1000 = 2^3 \times 5^3~

Có ~N~ hòn đá, được đánh số từ ~1~ đến ~N~. Với mỗi chỉ số ~i~ (~1 \le i \le n~), phần thưởng khi nhảy vào hòn đá thứ ~i~ là ~p_i~.

Ban đầu, có một chú ếch đang ngồi ở hòn đá thứ nhất và chú sẽ thực hiện liên tục một loạt các hành động sau:

• Nếu chú đang ngồi ở hòn đá ~i~ chú có thể nhảy đến hòn đá thứ ~i + 1~, ~i + 2~, ~\ldots~, ~i + k~, hay chỉ có thể nhảy qua không quá ~k~ hòn đá liên tiếp.

Bạn hãy giúp chú ếch tối đa hóa phần thưởng để nhảy từ hòn đá thứ nhất đến hòn đá thứ ~N~ nhé.

Lưu ý: phần thưởng có thể có giá trị âm.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~k~ lần lượt là số lượng hòn đá và só bước tối đa chú ếch có thể nhảy. ~(1 \le k \le N \le 10^6)~
• Dòng thứ hai gồm ~n~ số nguyên dương ~p_i~ (~1 \le i \le N, |p_i| \le 10^9~), là phần thưởng khi nhảy đến hòn đá thứ i.

Output

• Gồm một số nguyên, là phần thưởng lớn nhất có thể khi nhảy từ hòn đá thứ nhất đến hòn đá thứ ~N~.

Subtask

• Subtask ~1~ (~30 \%~ số điểm): ~k \le 5~
• Subtask ~2~ (~70 \%~ số điểm): không có ràng buộc gì thêm.

Example

Sample Input

6 3    
-2 8 2 -4 -3 5

Sample Output

13

Note

Đi ~1, 2, 3, 6~.

Cho dãy ~a~ gồm ~n~ số nguyên. Tìm hãy con dài nhất (không nhất thiết liên tiếp) của dãy ~a~ sao cho ba số nguyên bất kỳ trong dãy con đều có thể là ba cạnh của một tam giác.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 10^{6})~.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_{1}, a_{2}, \ldots, a_{n}~ ~(1 \leq a_{i} \leq 10^{9})~.

Output

• Dòng đầu tiên chứa độ dài lớn nhất của dãy con.
• Dòng tiếp theo chứa chỉ số của những phần tử có trong dãy con theo thứ tự tăng dần. Nếu có nhiều đáp án, hãy in một đáp án bất kỳ.

Scoring

• Bạn sẽ được ~50\%~ số điểm của test nếu in đúng kích thước lớn nhất của dãy con và ~100\%~ số điểm của test nếu in đúng cả hai.
• Subtask ~1~ (~30\%~ số điểm): ~n \leq 15~.
• Subtask ~2~ (~30\%~ số điểm): ~n \leq 10^{3}~.
• Subtask ~3~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test

Input

5
1 2 3 4 5

Output

3
2 3 4

Input

2
1 2

Output

2
1 2

Cho dãy ~n~ số nguyên ~a_1, a_2, …, a_n~ và một số nguyên ~k~. Mức độ đẹp của một dãy con liên tiếp ~a_i, a_{i+1}, …, a_j~ được đánh giá bằng ~GCD(a_i, a_{i+1}, …, a_j).(a_i + a_{i+1} + … + a_j)~, tức là độ đẹp bằng ước chung lớn nhất của các phần tử trong dãy con nhân với tổng các phần tử trong dãy con đó.

Yêu cầu: Tìm dãy con liên tiếp có ít nhất ~k~ phần tử và có mức độ đẹp là lớn nhất.

Input

• Dòng 1: Hai số nguyên ~n, k\ (1 ≤ k ≤ n ≤ 10^6)~;
• Dòng 2: ~n~ số nguyên ~a_1, a_2, …, a_n\ (1 ≤ a_i ≤ 10^6)~.

Output

• Ghi ra một số nguyên duy nhất là mức độ đẹp tìm được.

Subtask

• 10% số điểm tương ứng với 10% số test có ~n, k ≤ 100~;
• 20% số điểm tương ứng với 20% số test có ~n, k ≤ 5000~;
• 25% số điểm tương ứng với 25% số test có ~a_i ≤ 100~;
• 20% số điểm tương ứng với 20% số test có ~n, k ≤ 5.10^4~;
• 25% số điểm tương ứng với 25% số test không có ràng buộc gì thêm

Example

Sample Input

6 2
4 4 4 3 1 3

Sample Output

48

Cho một số nguyên, nhiệm vụ của bạn là tìm số lượng, tổng và tích của các ước số của nó. Ví dụ, chúng ta hãy xem xét số ~12~:

• số lượng ước số là ~6~ (chúng là ~1 , 2, 3, 4, 6, 12~)
• tổng của các ước số là ~1 + 2 + 3 + 4 + 6 + 12 = 28~
• tích của các ước số là ~1 \cdot 2 \cdot 3 \cdot 4 \cdot 6 \cdot 12 = 1728~

Vì số đầu vào có thể rất lớn, nó sẽ được cho dưới dạng phân tích thừa số nguyên tố.

Input

• Dòng đầu tiên có một số nguyên ~n~: số phần trong dạng phân tich thừa số nguyên tố.
• Sau đó, gồm ~n~ dòng mô tả dạng phân tích. Mỗi dòng có hai số ~x~ và ~k~, trong đó ~x~ là số nguyên tố và ~k~ là lũy thừa của nó.

Output

• In ba số nguyên chia lấy dư cho ~10 ^ 9 + 7~: số lượng, tổng và tích của các ước số.

Constraints

• ~1 \leq n \leq 10^5~
• ~2 \leq x \leq 10^6~
• mỗi ~x~ là một số nguyên tố riêng biệt
• ~1 \leq k \leq 10^9~

Example

Sample Input

2 
2 2
3 1

Sample Output

6 28 1728

Cho một dãy ngoặc ~s~ độ dài ~n~, sở dĩ gọi là dãy ngoặc bởi nó chỉ chứa hai loại kí tự là ( và ). Ta định nghĩa về dãy ngoặc đúng như sau:

• () là một dãy ngoặc đúng
• Nếu ~A~ là một dãy ngoặc đúng thì ~(A)~ cũng là một dãy ngoặc đúng
• Nếu ~A~ và ~B~ là hai dãy ngoặc đúng thì ~AB~ cũng là dãy ngoặc đúng

Dãy ngoặc ~s~ của chúng ta có thể không phải là dãy ngoặc đúng, nhưng nó không sai. Bởi nó có thể chứa nhiều dãy ngoặc đúng trong mình, thậm chí có thể chứa dãy ngoặc đúng đẹp.

Một dãy ngoặc đúng gọi là đẹp nếu quay dãy đó ~180~ độ, ta thu được chính nó. Ví dụ, ~()()~ hay ~(())~ là dãy ngoặc đúng đẹp; còn ~)()(~ và ~()(())~ thì không, bởi ~)()(~ không phải dãy ngoặc đúng, ~()(())~ thực hiện quay ~180~ độ thu được ~(())()~

Yêu cầu: Đếm số dãy ngoặc đẹp là dãy con (không cần liên tiếp) của ~s~. Hai dãy con được gọi là khác nhau nếu có một kí tự ~s_i~ của ~s~ xuất hiện trong dãy này mà không xuất hiện trong dãy kia. Vì đáp án có thể rất lớn nên hãy in ra số dư khi chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 500~).
• Dòng thứ hai chứa chứa một xâu kí tự mô tả ~s~.

Output

• Một số nguyên duy nhất là số dãy ngoặc đúng đẹp của dãy con ~s~.

Subtasks

Example

Sample Input

6
)))())

Sample Output

2

Note

• Có hai dãy con ~(4, 5)~ và ~(4, 6)~.

Aaron sở hữu một sở thú với các lồng thú được nối bởi những con đường, tạo thành một đồ thị cây gồm ~N~ đỉnh được nối bởi ~N-1~ cạnh (mọi lồng thú đều có thể tới được nhau, và không tồn tại chu trình). Mỗi lồng thứ ~i~ có một loại con vật là ~a_i~

Sắp tới sẽ có ~Q~ lượt khách đến thăm sở thú của Aaron. Trong chuyến thăm của lượt khách thứ ~j~, khách sẽ đi trên các con đường từ lồng ~u_j~ đến lồng ~v_j~ và được tự do vào xem các con vật trên đường đi đó. Tuy nhiên, mỗi lượt khách chỉ thích ngắm nhìn một loại thú nhất định. Các lượt khách của sở thú Aaron sẽ chỉ được thỏa mãn nếu như họ có thể ngắm nhìn con vật từ loại họ thích.

Hãy xác định liệu khách của Aaron có được thỏa mãn sau chuyến thăm.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~Q~ (~1 \le N, Q \le 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_i~ ~(1 \le a_i \le N)~.
• ~N - 1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~X~, ~Y~ (~1 \le X, Y \le N~) phân biệt, thể hiện có một con đường nối hai thành phố ~X~ và ~Y~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~u_j, v_j, c_j~ với ~c_j~ là loại thú người khách thứ ~j~ thích. ~(1 \le c_j \le N)~.

Output

• In ra xâu nhị phân độ dài ~Q~. Kí tự thứ ~i~ của xâu là ~1~ nếu khách thứ ~i~ thỏa mãn, ngược lại là không thỏa mãn.

Subtask

• Subtask ~1~ (~10 \%~ số điểm): (~N \le 10^3~, ~M \le 2 \times 10^3~).
• Subtask ~2~ (~40 \%~ số điểm): (~C_i \le 10~).
• Subtask ~3~ (~50 \%~ số điểm): Không có ràng buộc nào thêm.

Example

Sample Input

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

Sample Output

10110