Cho hai số nguyên dương ~x,k~.

Tìm số nguyên dương ~y~ bé nhất sao cho ~x \times y~ chia hết cho ~k~.

Input

Gồm một dòng duy nhất chứa hai số nguyên ~x,k~ cách nhau bởi dấu cách (~x,k \le 10^{18}~).

Output

Gồm một số nguyên dương duy nhất là đáp án của đề bài.

Scoring

Sample Input 1

8 6

Sample Output 1

3

Sample Input 2

12 7

Sample Output 2

7

Cho dãy ~A~ gồm ~N~ phần tử nguyên dương và một số nguyên dương ~K~. Tìm hai dãy liên tiếp của dãy ~A~ gồm đúng ~K~ phần tử (hai dãy không được phép giao nhau), sao cho chênh lệch tổng các phần tử của hai dãy là lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~, ~K~ ~(2 \le N \le 10^6, 1 \le K \le N / 2)~.

• Dòng thứ hai gồm ~N~ số nguyên dương có giá trị không quá ~10^9~ mô tả dãy số ~A~.

Output

• In ra một số nguyên dương là giá trị chênh lệch lớn nhất tìm được.

Scoring

Sample Input 1

5 2
1 3 2 1 8

Sample Output 1

5

Notes

Đáp án lớn nhất có thể đạt được là chọn 2 đoạn ~[1, 2]~ và đoạn ~[3, 4]~. ~|(1 + 3) - (1 + 8)|~ = 5

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~

Cho dãy số gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~.

Bạn hãy tìm dãy số ~b_1, b_2, \ldots, b_k~ dài nhất thỏa mãn:

• ~1 \le b_1 < b_2 < \ldots < b_k \le n~.

• ~a_{b_1} + 1 = a_{b_2} + 2 = \ldots = a_{b_k} + k~.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ là số lượng phần tử của dãy ~a~ (~1 \le n \le 10^6~).

Dòng thứ hai chứa ~n~ số nguyên dương mô tả dãy ~a_1, a_2, \ldots a_n~. (~1 \le a_i \le 10^6~, ~1 \le i \le n~).

Output

Dòng thứ nhất in ra một số nguyên dương ~k~ là số lượng phần tử của dãy ~b~ dài nhất tìm được.

Dòng thứ hai in ra ~k~ số nguyên dương mô tả dãy ~b_1, b_2, \ldots, b_k~.

Nếu có nhiều dãy ~b~ thỏa mãn thì in ra một dãy bất kì.

Scoring

Sample Input 1

7
5 6 1 4 2 3 2

Sample Output 1

4
1 4 6 7

Marisa cần chia một cây nấm thành ba miếng nhỏ hơn. Mũ nấm có dạng hình tròn, được cấu tạo từ ~n~ phần, phần thứ ~i~ có kích cỡ ~a_i~.

Ví dụ với ~a = \{1, 3, 4, 4, 4, 2 ,5\}~

Một miếng nấm sẽ chỉ được gồm các phần liên tiếp. Hãy tìm cách chia sao cho miếng nấm có kích cỡ nhỏ nhất là lớn nhất.

Input

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

Output

• Một số nguyên là kích cỡ lớn nhất có thể của miếng nấm nhỏ nhất.

Giới hạn

• Trong mọi test, ~3 \le n \le 10^5, 1\le a_i \le 10^9~
  • Subtask 1 (25% số điểm): ~1 \le n \le 100~
  • Subtask 2 (25% số điểm): ~1 \le n \le 400~.
  • Subtask 3 (25% số điểm): ~1 \le n \le 8000~.
  • Subtask 4 (25% số điểm): Không có giới hạn gì thêm.

Ví dụ

Input:

7
1 3 4 4 4 2 5

Output:

7

~A~ quyết định sẽ đi hái nấm trong rừng.

Có ~m~ con đường một chiều nối giữa ~n~ cây trong khu rừng. Ở mỗi con đường sẽ được trồng một số lượng nấm. Khi ~A~ đi qua một con đường, cậu ấy có thể thu thập tất cả loại nấm trên con đường đó. Khu rừng có một vùng đất màu mỡ kỳ diệu, nơi nấm phát triển với tốc độ chóng mặt. Nấm mới mọc lại ngay sau khi ~A~ hái xong nấm trên một con đường. Cụ thể hơn, sau khi ~A~ đi qua một con đường lần thứ ~i~, sẽ có ~i~ cây nấm mọc ít hơn trước đó có trên đường đi này. Ban đầu, nếu trên đường đi có ~x~ cây nấm, thì ~A~ thu thập được ~x~ cây nấm ở lần đầu tiên, ~x-1~ cây nấm ở lần thứ hai, ~x-1-2~ cây nấm ở lần thứ ba, ... , ~x-1-2-...-i~ cây nấm ở lần thứ ~i~. Tuy nhiên, số lượng cây nấm trên con đường không bao giờ được nhỏ hơn ~0~.

Ví dụ, ban đầu có ~9~ cây nấm trên đường đi. Số lượng cây nấm mà ~A~ có thể thu thập được sau các lần đi qua là ~9, 8, 6, 3~. Ở lần thứ năm ~A~ sẽ không thể thu thập thêm nấm nữa (tuy nhiên vẫn có thể đi qua được con đường này).

~A~ quyết định bắt đầu hành trình của mình ở cây ~s~. Vậy ~A~ có thể thu thập được tối đa bao nhiêu cây nấm?

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ là số lượng cây nấm và đường đi trong khu rừng.
• ~m~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~x, y, w~ cho biết đường đi từ ~x~ đến ~y~ ban đầu có ~w~ cây nấm. Có thể tồn tại đường đi từ một cây đến chỉnh nó, hoặc tồn tại nhiều đường đi giữa hai cây.
• Dòng cuối gồm số nguyên dương ~s~ là vị trí xuất phát của ~A~.

Constraints

• ~1 \le n, m \le 10^6~
• ~1 \le x, y \le n~, ~0 \le w \le 10^8~
• ~1 \le s \le n~

Subtasks

• Subtask ~1~ ~(30\%)~: Không có đường đi nào tạo thành chu trình.
• Subtask ~2~ ~(70\%)~: Không có điều kiện gì thêm.

Output

• Gồm một số nguyên duy nhất là lượng cây nấm tối đa mà ~A~ thu thập được

Sample Input 1:

2 2
1 2 4
2 1 4
1

Sample Output 1:

16

Explanation 1:

~A~ lần lượt đi từ ~1...2...1...2~ cho đến khi không còn nấm để thu hoạch. Đáp án là ~4 + 4 + 3 + 3 + 1 + 1 = 16~.

Sample Input 2:

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

Sample Output 2:

8

Explanation 2:

~A~ có thể đi từ ~1~ đến ~3~ để thu được ~8~ cây nấm.

Vào một ngày đẹp trời, bỗng dưng Thinkies đi lạc vào một mê cung. Mê cung được biểu diễn dưới dạng một ma trận ~n*m.~ Ô hàng ~i~, cột ~j~ của mê cung được gọi là ô ~(i,j)~. Mê cung này rất đặc biệt, có ~p~ ô lối vào và ~q~ ô lối ra. Thinkies có thể xuất phát từ một ô bất kì trong ~p~ ô lối vào đó, và có thể thoát ra bằng cách đi tới một ô bất kì trong ~q~ ô lối ra. Mỗi ô đều chứa những giá trị riêng, ô ~(i,j)~ có giá trị ~a(i,j)~. Từ một ô ~(i,j)~ bất kì, Thinkies có thể di chuyển theo 2 cách (đều mất một đơn vị thời gian):

• Di chuyển sang ô kề cạnh với nó (từ ô ~(i,j)~ có thể tới ô ~(u,v)~ nếu ~(u,v)~ kề cạnh với ~(i,j)~ và ~a(u,v) \neq 0~).
• Sử dụng phép teleport, di chuyển sang ô ~(u,v)~ nếu ~u*v = a(i,j)~ và ~a(u,v) \neq 0~. Tuy nhiên, Thinkies chỉ có thể sử dụng được ~k~ lần phép teleport này mà thôi. Lưu ý, nếu trên các ô lối vào hoặc lối ra có giá trị a(u,v) = 0 thì ta sẽ không thể nào xuất phát hoặc đi vào ô đó. Hãy tìm cách đưa Thinkies ra khỏi mê cung sớm nhất có thể!

Input

• Dòng đầu gồm 3 số ~n,m,k (1 \le n, m \le 1000, k \le 3)~
• ~n~ dòng sau, mỗi dòng gồm m số ~a(i,j)~ biểu hiện mê cung
• Dòng tiếp theo gồm 2 số tự nhiên ~p,q (p+q \le n*m)~.
• ~p~ dòng tiếp theo mỗi dòng gồm một cặp số ~(i,j)~ thể hiện các ô là lối vào.
• ~q~ dòng tiếp theo mỗi dòng gồm một cặp số ~(i,j)~ thể hiện các ô là lối ra.

Output:

Số đơn vị thời gian ít nhất để Thinkies có thể ra khỏi mê cung, nếu không thể thoát ra in ra số ~-1~.

Ràng buộc

~a(i, j) \le 6 * 10 ^ 6~

• Subtask 1: ~n \le 50, m \le 50, k = 0~. (20%)
• Subtask 2: ~n \le 1000, m \le 1000, k = 0~. (30%)
• Subtask 3: ~n \le 50, m \le 50.~ (20%)
• Subtask 4: ~n,m \le 1000, k \le 3.~ (30%)

Sample Test 1

Input:

3 3 1
6 1 1
1 1 1
1 1 1
1 1
1 1
3 3

Output:

2

Sample Test 2

Input:

2 2 3
0 1 
2 1
1 1
1 1
2 1 

Output:

-1

Sample Test 3

Input:

2 2 3
2 1 
0 1
1 1
1 1
2 1 

Output

-1

Giải thích

• Ở test 2, do ô ~(1,1)~ có ~a(1,1) = 0~ nên ta không thể xuất phát từ ô đó, nên sẽ không thể đi ra.
• Ở test 3, do ô ~(2,1)~ có ~a(2,1) = 0~ nên ta không thể đi vào ô đó, nên không thể thoát ra mê cung.

Cho một biểu đồ được vẽ với ~n~ cột đánh số từ ~1~ đến ~n~ từ trái sang phải, mỗi cột có độ rộng bằng ~1~, cột thứ ~i~ có độ cao là ~h_i~.

Yêu cầu: Cho biểu đồ và một số nguyên ~p~, xác định số hình chữ nhật khác nhau thỏa mãn điều kiện sau:

Các đỉnh của hình chữ nhật là các tọa độ nguyên, có một cạnh nằm trên trục ~Ox~, hình chữ nhật này phải được phủ hoàn toàn bởi biểu đồ, và diện tích của nó không nhỏ hơn ~p~.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~p~. (~1 \le n \le 10^5, 1 \le p \le 10^{14}~) — số cột của biểu đồ và diện tích yêu cầu.

Dòng tiếp theo chứa ~n~ số nguyên ~h_1, h_2, \cdots, h_n~ (~1 \le h_i \le 10^5~) — độ cao của cột thứ ~i~.

Output

Một số nguyên duy nhất là số hình chữ nhật khác nhau thỏa mãn điều kiện trên.

Scoring

Sample Input 1

2 4
2 4

Sample Output 1

2

Sample Input 2

3 1
1 4 2

Sample Output 2

11

Notes

Trong ví dụ thứ nhất, có duy nhất hai hình chữ nhật có diện tích không nhỏ hơn ~4~ là ~[2, 2]~ và ~[0, 4]~.

Trong ví dụ thứ hai, bất kỳ hình chữ nhật nào cũng có diện tích không nhỏ hơn ~1~, và có tổng cộng ~11~ hình chữ nhật khác nhau.