Cho dãy số ~A~ gồm ~n~ số nguyên dương ~A_1, A_2, \dots, A_n~. Một bộ ba số được gọi là bộ số tam giác, nếu ba số này là độ dài ba cạnh của một tam giác.

Yêu cầu: Hãy đếm xem trong dãy ~A~ có bao nhiêu bộ số tam giác ~(A_i, A_j, A_k)~ với ~i, j, k~ đôi một khác nhau.

Input:

Vào từ file văn bản BSTG.INP gồm:

• Dòng đầu chứa số nguyên ~n\ (3 ≤ n ≤ 1000)~.
• Dòng tiếp theo chứa ~n~ số nguyên dương trong dãy ~A\ (A_i ≤ 10^9)~.

Output:

• Ghi ra file văn bản BSTG.OUT số lượng bộ số tam giác trong dãy đã cho.

Ví dụ:

BSTG.INP

5
4 3 1 5 7

BSTG.OUT

3

Giải thích

Có ~3~ bộ số tam giác là ~(4, 3, 5),\ (4, 5, 7)~ và ~(3, 5, 7)~.

Subtask:

• ~60\%~ số test có ~n \le 500~.
• ~40\%~ số test không có ràng buộc gì thêm.

Xét dãy số nguyên ~A=(a_1,a_2,\dots,a_n)~. Dãy chứa các phần tử ở các vị trí liên tiếp của ~A~ được gọi là dãy con. Hai dãy con được gọi là khác nhau nếu tồn tại ít nhất một vị trí mà phần tử của ~A~ ở vị trí đó tham gia vào dãy con này và không tham gia vào dãy con kia.

Yêu cầu: Cho số nguyên ~b~. Hãy xác định số lượng dãy con có giá trị lớn nhất của các phần tử trong dãy con đúng bằng ~b~.

Input:

Vào từ file văn bản NUMMAX.INP gồm:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~b~ ~(2 \le n \le 10^5;\ 1 \le b \le 10^9)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,\dots,a_n~ ~(1 \le a_i \le 10^9;\forall i \in [1;n])~

Output:

Ghi ra file văn bản NUMMAX.OUT một số nguyên duy nhất là số lượng dãy con tìm được.

Ví dụ:

NUMMAX.INP

4 5
1 3 5 2

NUMMAX.OUT

6

Subtask:

• Có ~20\%~ số test tương ứng ~20\%~ số điểm có ~n \le 10^3~ và không có dãy con thỏa mãn.
• Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~n \le 10^3~, đồng thời số ~b~ xuất hiện đúng ~1~ lần trong dãy và là số lớn nhất trong dãy đó.
• Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~n \le 5.10^3~
• ~40\%~ số test còn lại tương ứng ~40\%~ số điểm không có ràng buộc gì thêm.

Mạng giao thông của đất nước Peace xinh đẹp có ~n~ thành phố được nối với nhau bằng hệ thống các đường cao tốc. Vì lý do kinh tế nên nhà vua chỉ xây dựng ~n-1~ con đường đủ đảm bảo sự đi lại giữa hai thành phố bất kỳ. Tất nhiên, mỗi con đường có lệ phí riêng.

Công ty lữ hành ABC nhận được ~m~ yêu cầu thuê xe của ~m~ khách hàng. Mỗi yêu cầu thể hiện như là một cặp hai thành phố ~s, t~ - yêu cầu di chuyển từ thành phố ~s~ đến thành phố ~t~ chỉ bằng đường cao tốc. Tất nhiên, Ban Giám đốc công ty muốn rằng tổng lệ phí giao thông phải trả cho các con đường trên hành trình từ ~s~ đến ~t~ phải là nhỏ nhất.

Yêu cầu: Với mỗi yêu cầu thuê xe, hãy giúp Ban Giám đốc tính toán tổng lệ phí giao thông ít nhất phải trả để thực hiện yêu cầu này.

Input

Vào từ tệp MINCOST.INP:

• Dòng đầu chứa hai số nguyên ~n, m\ (1\le n,m \le 10^5)~;
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i, v_i, w_i~ thể hiện có tuyến đường cao tốc hai chiều nối thành phố ~u_i~ với thành phố ~v_i~ và có lệ phí giao thông là ~w_i\ (1\le u_i,v_i \le n;\ w_i \le 10^5)~
• ~m~ dòng tiếp theo, dòng thứ ~j~ ghi hai số nguyên ~s_i, t_i\ (1\le s_j, t_j \le n)~ thể hiện yêu cầu thứ ~j~ đối với công ty: Thuê xe đi từ thành phố ~s_j~ tới thành phố ~t_j~.

Output

Ghi ra tệp MINCOST.OUT:

• Gồm ~m~ dòng, dòng thứ ~j~ ghi một số nguyên là chi phí ít nhất phải trả khi thực hiện yêu cầu ~j\ (j \in [1;m])~

Ví dụ

MINCOST.INP

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

MINCOST.OUT

9
6
11
14

Nhảy lò cò là trò chơi dân gian của Việt Nam. Người trên hành tinh X cũng rất thích trò chơi này và họ đã cải biên trò chơi này như sau: Trên mặt phẳng vẽ ~n~ vòng tròn được đánh số từ ~1~ đến ~n~. Tại vòng tròn ~i~ người ta điền số nguyên dương ~a_i~. Hai số trên hai vòng tròn tùy ý không nhất thiết phải khác nhau. Tiếp đến người ta vẽ các mũi tên, mỗi mũi tên hướng từ một vòng tròn đến một vòng tròn khác. Quy tắc vẽ mũi tên là: Nếu có ba số ~a_i, a_j, a_k~ thỏa mãn ~a_k = a_i + a_j~ thì vẽ mũi tên hướng từ vòng tròn ~i~ đến vòng tròn ~k~ và mũi tên hướng từ vòng tròn ~j~ đến vòng tròn ~k~. Người chơi chỉ được di chuyển từ một vòng tròn đến một vòng tròn khác nếu có mũi tên xuất phát từ một trong số các vòng tròn, di chuyển theo cách mũi tên đã vẽ để đi đến các vòng tròn khác. Người thắng cuộc sẽ là người tìm được cách di chuyển qua nhiều vòng tròn nhất.

Ví dụ: Với 5 vòng tròn và các số trong vòng tròn là ~1, 2, 8, 3, 5~, trò chơi được trình bày trong hình dưới đây:

Khi đó có thể di chuyển được nhiều nhất qua 4 vòng tròn (tương ứng với đường di chuyển được tô đậm trên hình vẽ).

Yêu cầu: Hãy xác định xem trong trò chơi mô tả ở trên, nhiều nhất có thể di chuyển được qua bao nhiêu vòng tròn.

Input:

Vào từ file văn bản "NKJUMP.INP":

• Dòng đầu chứa số nguyên ~n\ (3\ \le\ n\ \le\ 1000)~;
• Dòng thứ hai chứa dãy số nguyên dương ~a_1,a_2,\ \dots,\ a_n\ (a_i\ \le\ {10}^9,\ i=1,\ 2,...,\ n)~. Các số trên cùng dòng viết cách nhau ít nhất một dấu cách.

Output:

Ghi ra file văn bản "NKJUMP.OUT" số lượng vòng tròn trên đường di chuyển tìm được.

Ví dụ:

NKJUMP.INP

5
1 2 8 3 5

NKJUMP.OUT

4

Subtasks

• 60% số tests ứng với 60% số điểm của bài có ~3\ \le\ n\ \le\ 100~.
• 40% số tests còn lại không có giới hạn gì thêm.

Loli là một cô bé 5 tuổi và đang được học bảng chữ cái. Điều kiện tiên quyết để Loli viết được một xâu ký tự bất kỳ là Loli phải học hết ký tự trong xâu ký tự đó đã.

Cô giáo giao cho Loli một xâu ~S~ và muốn Loli viết lại xâu đó. Vì Loli lười không muốn học hết bảng chữ cái nên Loli thắc mắc rằng mình cần học ít nhất bao nhiêu chữ cái liên tiếp trong bảng chữ cái tiếng Anh để viết lại xâu ~S~ đó.

Input:

Lấy từ tệp ALPHABET.INP gồm:

• Một dòng duy nhất ghi xâu ~S~ chứa các chữ cái tiếng Anh in thường (độ dài xâu không quá ~10^4~).

Output:

Ghi ra tệp ALPHABET.OUT gồm:

• Một số nguyên là số chữ cái liên tiếp ít nhất Loli cần học.

Ví dụ 1:

ALPHABET.INP

zzzzz

ALPHABET.OUT

1

Ví dụ 2:

ALPHABET.INP

bcf

ALPHABET.OUT

5

Giải thích

• Ở test đầu, Loli chỉ cần học ~1~ ký tự 'z' để viết lại xâu.
• Ở test thứ 2, Loli cần học ~5~ ký tự liên tiếp 'b', 'c', 'd', 'e', 'f' để viết lại xâu.

Pha lê Swarovski được dùng làm đồ trang sức vô cùng đẹp và vô cùng giá trị. Các hạt pha lê gồm rất nhiều loại khác nhau, mỗi loại được ký hiệu đại diện bởi một số nguyên dương không vượt quá ~10^9~. Trong một lần thám hiểm vùng rừng rậm Amazon, đoàn thám hiểm đã tìm thấy một chuỗi rất dài gồm ~n~ hạt pha lê được gắn liên tiếp nhau. Trước khi đưa về nghiên cứu, người ta quyết định cắt chuỗi hạt tìm thấy thành các chuỗi con gồm các hạt liên tiếp có cùng độ dài. Khi đó độ đa dạng của từng chuỗi hạt là số lượng loại hạt khác nhau tồn tại trong chuỗi hạt đó. Độ đa dạng trong một cách cắt chuỗi ban đầu là độ đa dạng nhỏ nhất của các chuỗi tạo thành.

Yêu cầu: Hãy xác định số lượng cách cắt chuỗi hạt, độ dài chuỗi hạt con và độ đa dạng của từng cách cắt tương ứng.

Input:

Vào từ file văn bản PEARL.INP gồm:

• Dòng đầu tiên chứa số nguyên dương ~n\ (n \le 5.10^5)~ xác định số lượng hạt trong chuỗi ban đầu.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,a_3,\dots,a_n\ (1 \le i \le n)~ xác định loại của các hạt trong chuỗi theo thứ tự.

Output:

Ghi ra file văn bản PEARL.OUT gồm:

• Dòng đầu chứa số nguyên dương ~k~ – số lượng cách cắt chuỗi ban đầu thành các chuỗi con cùng độ dài.
• ~k~ dòng tiếp theo, dòng thứ ~i\ (1 \le i \le k)~ chứa 2 số nguyên dương ~x_i\ \ y_i~ với ~x_i~ là kích thước các chuỗi con mới theo cách cắt thứ ~i~ và ~y_i~ là độ đa dạng của cách cắt tìm được. Các cách cắt liệt kê theo thứ tự tăng dần của của kích thước chuỗi hạt con.

Ví dụ:

PEARL.INP

6
1 2 2 4 3 3

PEARL.OUT

4
1 1
2 1
3 2
6 4

Subtasks:

• Có ~30\%~ số test tương ứng ~30\%~ số điểm có ~a_1=a_2=\dots=a_n \le 2;\ n \le 100~
• Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~a_i \le 2;\ 1 \le i \le n \le 100~
• Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~n \le 5.10^4~
• ~30\%~ số test còn lại tương ứng ~30\%~ số điểm không có ràng buộc gì thêm.

Một ông già rảnh hơi nào đó đã viết cho Loli ~Q~ số nguyên và bảo Loli phải kiểm tra xem số đó có phải là số nguyên tố không. Nếu Loli trả lời đúng hết thì ông già sẽ mời Loli về nhà riêng của mình…

Input:

Vào từ file văn bản NTO.INP gồm:

• Dòng ~1~: chứa số nguyên dương ~Q~ ~(1 \le Q \le 10^5)~.
• Dòng ~2~ đến dòng ~Q+1~: dòng ~i+1~ chứa số nguyên ~a[i]~ cần kiểm tra ~(|a[i]| \le 10^6)~.

Output:

Ghi ra file văn bản NTO.OUT gồm:

• ~Q~ dòng, dòng ~i~ là kết quả kiểm tra tính nguyên tố của số nguyên ~a[i]~. Nếu không là số nguyên tố, in ra Yes, ngược lại, in ra No.

Ví dụ:

NTO.INP

1
3

NTO.OUT

No

Xét bảng hình chữ nhật kích thước ~m \times n~ ô. Các hàng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái qua phải. Ô nằm trên hàng ~i~ và cột ~j~ được ghi một số nguyên không âm ký hiệu ~C_{ij}~. Ở góc trên trái bảng có một quân cờ. Ta phải chuyển quân cờ về ô dưới phải của bảng theo quy tắc sau:

• Tại mỗi bước nhảy, chỉ được di chuyển sang phải trên cùng một hàng hoặc di chuyển xuống dưới theo cùng một cột
• Kích thước bước nhảy không được vượt quá số ghi trên ô có quân cờ hiện tại
• Chỉ được di chuyển trong phạm vi bảng đang xét

Kích thước của bước nhảy từ ô ~(i,j)~ tới ô ~(u,v)~ được tính bằng giá trị ~u+v-i-j~.

Yêu cầu: Cho dãy ~a_1,a_2,\dots,a_m;\ b_1,b_2,\dots,b_n~ và số nguyên dương ~k~. Bảng ~C~ kích thước ~m \times n~ được xác định với ~C_{ij}=1+[(a_i+b_j)\ mod\ k];\ \forall i \in [1;m],\ j \in [1;n]~. Hãy tính số lượng cách di chuyển quân cờ từ ô trên trái ~(1,1)~ xuống ô dưới phải ~(m,n)~.

Input:

Vào từ file văn bản JUMP.INP gồm:

• Dòng đầu chứa ~3~ số nguyên dương ~m, n, k\ (m,n,k \le 4.10^3)~
• Dòng thứ hai chứa ~m~ số nguyên ~a_1,a_2,a_3,\dots,a_m~ ~(0 \le a_i \le 10^9)~
• Dòng thứ ba chứa ~n~ số nguyên ~b_1,b_2,b_3,\dots,b_n~ ~(0 \le b_i \le 10^9)~

Output:

Ghi ra file văn bản JUMP.OUT một số nguyên duy nhất là số cách di chuyển tìm được lấy theo module ~10^9 + 7~.

Ví dụ 1:

JUMP.INP

3 2 1
3 4 11
2 5

JUMP.OUT

3

Ví dụ 2:

JUMP.INP

3 2 2
3 4 11
2 5

JUMP.OUT

4

Subtask:

• ~15\%~ số test tương ứng ~15\%~ số điểm có ~m,n \le 10,\ k=1~
• ~15\%~ số test khác tương ứng ~15\%~ số điểm có ~m,n \le 10^3,\ k=1~
• ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~m,n \le 10^3,\ k \le 10~
• ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~m,n \le 10^3~
• ~30\%~ số test còn lại tương ứng ~30\%~ số điểm không có ràng buộc gì thêm.

HD sáng tạo ra một phương pháp nén dữ liệu mới như sau:

• Cho dãy ~N~ phần tử bằng ~1~.
• Sử dụng các chữ số từ ~1~ đến ~A~ để nén dãy phần tử ban đầu sao cho tổng các phần tử sau khi nén bằng ~N~.

Ví dụ: Với ~N = 5, A = 3~ ta có thể các cách nén như sau: ~(1,1,1,1,1)~ thành ~(1,2,1,1); (1,2,2); (2,1,2); (3; 2); \dots~.

Yêu cầu: Cho ~N~ và ~A~. Hãy đếm số cách nén khác nhau?

Input:

Vào từ file văn bản COMPRESS.INP:

• Một dòng duy nhất chứa ~2~ số nguyên ~N~ và ~A~ ~(1 ≤ A ≤ N ≤ 50)~.

Output:

Ghi ra file văn bản COMPRESS.OUT:

• Một số duy nhất là số cách nén khác nhau.

Ví dụ:

COMPRESS.INP

2 1

COMPRESS.OUT

1

Ví dụ:

MONEY.INP

5 7 4
1 4
1 100 4 50 3 10 2 55
1 2 10
5 3 42
1 3 30
2 4 50
3 4 70
2 5 24
4 5 21

MONEY.OUT

103

Subtask:

• ~60\%~ số test có ~N \le 100~.
• ~40\%~ số test không có ràng buộc gì thêm.

Có hai sỹ quan chơi một trò chơi. Đầu tiên người thứ nhất đưa cho người thứ hai một số nguyên dương ~n~. Nhiệm vụ của người thứ hai là thực hiện nhiều vòng chơi nhất có thể. Mỗi vòng chơi, anh ta chọn ra một số nguyên ~x > 1~ sao cho ~n~ chia hết cho ~x~ và thay thế ~n~ bởi ~\dfrac{n}{x}~. Khi ~n~ bằng ~1~ thì trò chơi kết thúc và điểm mà người chơi nhận được là số lần lấy được số ~x~.

Để trò chơi trở nên thú vị hơn, số ~n~ được chọn có dạng ~\dfrac{a!}{b!}~ với hai số nguyên dương ~a, b\ (a > b)~. Ở đây ~k! = 1 \times 2 \times \dots \times k~.

Yêu cầu: Hãy xác định số điểm lớn nhất mà người thứ hai nhận được.

Input:

Vào từ file văn bản NGAME.INP gồm:

• Dòng đầu tiên ghi số nguyên dương ~t\ (1 ≤ t ≤10^6)~ là số lần chơi
• ~t~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương ~a, b\ (1≤b≤a≤5\times 10^6)~ mô tả dạng của số ~n~ trong ván chơi.

Output:

Ghi ra file văn bản NGAME.OUT: Với mỗi lân chơi in ra số điểm lớn nhất nhận được

Ghi chú:

• Subtask 1 (50%): ~1 ≤ b ≤ a ≤ 14;\ T ≤ 10~
• Subatsk 2 (50%): ~20 ≤ b ≤ a ≤ 5\times 10^6;\ T ≤ 10^6~

Ví dụ:

NGAME.INP

2
3 1
6 3

NGAME.OUT

2
5

Nam là một người mới bắt đầu học lập trình. Hôm nay Nam học về mảng. Anh ấy có một mảng ~n~ số nguyên dương là ~a_1, a_2, \dots, a_n~. Giáo viên của anh cho một nhiệm vụ, tìm một số ~x~ trong mảng thoả mãn: tất cả các số khác trong mảng đều chia hết cho số ~x~ đó. Hãy giúp anh ấy tìm ra số ~x~ đó!

Input:

File "SNUM.INP" gồm:

• Dòng đầu chứa số nguyên ~n\ (1\le n \le 10^5)~, cho biết số lượng số nguyên dương trong mảng.
• Dòng thứ hai gồm các số nguyên ~a_1, a_2, \dots, a_n\ (1 \le a_i \le 10^9)~, là các phần tử của mảng.

Output:

File "SNUM.OUT":

• Ghi một số nguyên ~x~ duy nhất, sao cho tất cả các số khác trong mảng đều chia hết cho số ~x~ đó.
• Nếu số đó không tồn tại, đưa ra ~-1~.

Ví dụ 1:

SNUM.INP

3
2 2 4

SNUM.OUT

2

Ví dụ 2:

SNUM.INP

5
2 1 3 1 6

SNUM.OUT

1

Ví dụ 3:

SNUM.INP

3
2 3 5

SNUM.OUT

-1