Cho một dãy gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Hãy tìm một đoạn con ~[l, r]~ ~(1 \le l \le r \le n)~ của dãy ~a~ sao cho đoạn con đó có tổng lớn nhất.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(-10^9 \le a_i \le 10^9)~

Output

Gồm một số nguyên duy nhất là kết quả của bài toán.

Sample Test

Input:

5
1 3 -2 3 -5

Output

5

Đường Hà Nội có ~n~ cái cột đèn được đánh số từ ~1~ đến ~n~. Tuy nhiên, trận bão tàn khốc vừa qua đã khiến ~t~ ~(t \leq n)~ cây đèn này bị đổ.

Sắp tới thầy Tùng cần tổ chức một lễ hội ẩm thực tại đây, và yêu cầu cần tổ chức tại nơi có ít nhất ~k~ cái đèn còn nguyên vẹn liên tiếp. Vì thời gian gấp rút, bạn được thầy yêu cầu tìm xem cần phải sửa chữa ít nhất bao nhiêu cây đèn để có thể tổ chức lễ hội.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n, k, t~ ~(1 \le t, k \le n \le 10^5)~.
• ~t~ dòng tiếp theo, mỗi dòng gồm một số nguyên dương là vị trí có cây đèn bị đổ.

Output

• In ra một số nguyên duy nhất là số cây đèn cần được sửa chữa.

Sample Test

Input:

10 6 5
2
10
1
5
9

Output:

1

Note:

Sửa cây đèn tại vị trí ~5~ và chọn các cây ~3, 4, 5, 6, 7, 8~ để tổ chức lễ hội.

Cho một dãy gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Hãy đếm số đoạn con ~[l, r]~ ~(1 \le l < r \le n)~ sao cho ~a_l + a_{l+1} + ... + a_r~ chia hết cho ~d~

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~d~ ~(1 \le n, d \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(-10^9 \le a_i \le 10^9)~

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Sample Input

5 4
1 3 -2 3 -5

Sample Output

4

Cho một dãy gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Hãy đếm số đoạn con ~[l, r]~ ~(1 \le l \le r \le n)~ sao cho trung bình cộng của đoạn con ~[l, r]~ là ~k~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~ ~(1 \le n \le 10^5, |k| \le 10^6)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(-10^6 \le a_i \le 10^6)~

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Sample Input

5 2
1 3 -2 3 -5

Sample Output

1

Cho một bảng ~n \times m~, mỗi ô ~(i, j)~ của bảng được gán một giá trị riêng biệt ~a_{i, j}~. Bạn được yêu cầu trả lời ~q~ truy vấn, mỗi truy vấn gồm bốn số nguyên dương ~u, v, x, y~ tương đương với việc bạn cần tìm tổng các giá trị nằm trong bảng con có góc trái trên là ô ~(u, v)~ và góc phải dưới là ô ~(x, y)~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ ~(1 \le n, m \le 1000)~.
• ~n~ dòng tiếp tiếp, mỗi dòng gồm ~m~ số nguyên dương ~a_{i, j}~ là các giá trị của các ô trong bảng. ~(a_{i, j} \le 10^9)~.
• Dòng tiếp theo gồm số nguyên dương ~q~ ~(1 \le q \le 10^5)~.
• ~q~ dòng tiếp theo, mỗi dòng gồm bốn số nguyên dương ~u, v, x, y~ ~(1 \le u \le x \le n, 1 \le v \le y \le m)~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ là đáp án của kết quả truy vấn thứ ~i~.

Sample Input

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

Sample Output

18
54
5
18

Cho dãy gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Bạn được phép thay đổi bất kì một số trong dãy trên thành một số nguyên dương khác bất kì. Hãy tìm cách thay đổi tối ưu để ước chung lớn nhất của dãy trên lớn nhất có thể, hay ~gcd(a_1, a_2, ..., a_n)~ là lớn nhất.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.

Output

• Gồm một số nguyên duy nhất là kết quả bài toán.

Sample Input

3
4 3 8

Sample Output

4

Note

Có thể thay đổi ~a_2=3~ thành ~a_2 = 16~. Từ đó ~gcd(a_1, a_2, a_3) = gcd(4, 16, 8) = 4~.

Cho một dãy xâu ~S~ gồm ~n~ kí tự từ ~1~ đến ~9~. Hãy đếm số lượng cặp ~(i, j)~ ~(1 \le i \le j \le n)~ thỏa mãn các chữ số trong đoạn ~[i, j]~ tạo thành một số nguyên chia hết cho ~2023~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - độ dài xâu ~(1 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ kí tự của xâu ~S~.

Output

Gồm số nguyên duy nhất là kết quả bài toán.

Sample Test

Input:

10
2427624276

Output:

3

Note

Các cặp ~(i, j)~ thỏa mãn là: ~(1, 5)~ ~(6, 10)~, ~(1, 10)~.

Cho hai dãy ~a~ và ~b~ cùng có ~n~ phần tử nguyên. Ta định nghĩa hàm ~sum(x,y)~ ~(1 \le x,y \le n)~ như sau:

• Nếu ~x \le y~ thì ~sum(x,y) = a_x + a_{x+1} + a_{x+2} + ... + a_y~.
• Nếu ~x > y~ thì ~sum(x,y) = b_x + b_{x-1} + b_{x-2} + ... + b_y~.

Nhiệm vụ của bạn là, hãy chọn ra hai đoạn ~[x,y]~ ~(1 \le x \le y \le n)~ và ~[c,d]~ ~(1 \le c \le d \le n)~ sao cho ~S = \sum sum(i,j)~ với mọi ~x \le i \le y~ và ~c \le j \le d~ là lớn nhất.

Constraint

• ~1 \le n \le 400~.
• ~-10^6 \le b_i, a_i \le 10^6~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên miêu tả dãy ~a~.
• Dòng thứ ba gồm ~n~ số nguyên miêu tả dãy ~b~.

Output

• In ra ~S~ lớn nhất tìm được.

Subtask

• ~30\%~ số test có ~n \le 10~
• ~40\%~ số test có ~n \le 50~.
• ~30\%~ số test có ~n \le 400~.

Sample Input 1

5
1 4 2 -1 -2
-2 -1 1 2 -1

Sample Output 1

45

Explanation 1

• Chọn đoạn ~[1,5]~ và ~[2,5]~.

There are ~N~ pictures delivered for the exhibition. The ~i~-th painting has a beauty value of ~A_i~.

The exhibition organizer wants to make a triptych by choosing three paintings having indices of ~x, y, z~ such that ~1\le x\lt y\lt z\le N~ and ~A_x = P, A_y = Q, A_z = R~.

Write a program to help the organizer count the number of different triples of paintings that can be made into triptychs. Two triples of paintings are considered different if they do not contain the same set of paintings.

Input Specification

• The first line of input contains an integer ~N~;

• The following line of input contains ~N~ integers ~A_1, A_2, ..., A_N~;

• The third line of input contains three integers ~P, Q, R~.

Output Specification

• Output the number of distinct triptychs the organizer can make.

Examples

Input

5
1 2 2 1 2
1 2 1

Output

2

Explanation

Such triples of indices of paintings are: ~(1, 2, 4), (1, 3, 4)~.

Input

5
1 2 2 1 2
2 1 1

Output

0

Explanation

There are no ways to make a triptych.

Constraints

For all subtasks:

• ~3\le N\le 2\times 10^6~

• ~1\le A_i\le 10^9~

• ~1\le P, Q, R \le 10^9~

Subtask 1 [30%]

• ~3\le N\le 200~

Subtask 2 [30%]

• ~200\lt N\le 3\times 10^4~

Subtask 3 [40%]

• No additional constraints

Cho số nguyên dương ~n~ ~(2 \leq n \leq 10^{14})~.

Yêu cầu: Phân tích ~n~ thành tích của ít nhất các số ~square-free~.

Số ~square-free~ là số nguyên dương không chia hết cho số chính phương nào ngoại trừ ~1~.

Input

• Mỗi dòng gồm ba số nguyên dương ~n~

Output

• In ra các số nguyên dương, mỗi số là một số ~square-free~ nằm trên một dòng, theo thứ tự giảm dần.

Sample Input 1

108

Sample Output 1

6
6
3

Sample Input 2

19

Sample Output 2

19

Có hai thao tác như sau:

1. Tăng số lên ~1~ đơn vị, nếu số có giá trị ~m~ thì quay về ~1~;
2. Gán số đó thành số ~X~.

Cho dãy gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(a_i \ne a_{i+1}; a_i \le m)~. Ban đầu ở giá trị ~a_1~, sử dụng các thao tác để từ ~a_1~ đi đến ~a_2~, từ ~a_2~ đi đến ~a_3~, ..., sao cho đi qua tất cả các giá trị theo thứ tự từ ~a_1~ đến ~a_n~. Hãy chọn số ~X~ để số thao tác cần sử dụng là nhỏ nhất có thể. In ra số lượng thao tác ít nhất tìm được.

Input

• Dòng đầu chứa hai số nguyên ~n~, ~m~ (~2 \le n, m \le 10^5~).

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le m~).

Output

In ra kết quả của bài toán.

Scoring

• Subtask 1 (~25~ điểm): ~1 \le a_1 < a_2 < \dots < a_n \le m~.
• Subtask 2 (~25~ điểm): ~n, m \le 10^3~.
• Subtaks 3 (~50~ điểm): Không có ràng buộc gì thêm.

Example

Input

4 5
1 2 4 5

Output

3

Note

Chọn X = 4

Input

2 3
2 1

Output

1

Note

Chọn X = 1

Hè đã tới, ~mrtee~ muốn cho các học sinh của mình vận động một chút. Thầy đã lập ra một cuộc thi nhảy xa, tuy nhiên điều luật của nó thì rất lạ.

Nếu chiếu trên trục ~OX~, đường nhảy sẽ bắt đầu từ điểm ~1~ và kết thúc tại điểm ~n~. Bạn sẽ xuất phát từ điểm ~0~ và được nhảy bao nhiêu lượt tùy thích, miễn là không ra khỏi phạm vi ~[1,n]~. Tuy nhiên, mỗi lượt bạn phải nhảy một quãng đường nguyên dương và ở lần nhảy thứ ~i~, bạn phải nhảy một quãng đường có độ chia hết cho ~k+i-1~. Tất nhiên, bạn sẽ được cung cấp trước ~2~ giá trị ~n~ và ~k~.

Là một ~coder~ yêu thích toán học, bạn không quan tâm tới việc thắng thua trong cuộc thi này lắm, mà chỉ hứng thú với việc đếm xem với mỗi vị trí ~i~ thuộc đoạn ~[1,n]~, có bao nhiêu cách nhảy khác nhau từ điểm xuất phát tới đó.

Hãy thử lập trình và giải đáp câu hỏi ấy!

Input

• Gồm một dòng chứa hai số nguyên dương ~n, k~.
  
  

Output

• In ra ~n~ số nguyên, số thứ ~i~ là số cách để nhảy từ điểm ~0~ tới điểm ~i~, vì kết quả có thể rất lớn nên hãy lấy phần dư với modulo ~10^9+7~.
  
  

Constraints

• ~1 \le k \le n \le 2*10^5~
  
  

Subtasks

• ~35\%~ số điểm: ~n \le 300~.
• ~40\%~ số điểm: ~n \le 4000~.
• ~25\%~ số điểm: ~n \le 2*10^5~.
  
  

Sample Test 1

Input:

12 1

Output:

1 1 2 2 3 4 5 6 8 10 12 15

Sample Test 2

Input:

15 3

Output:

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

Giải thích

• Ở ví dụ ~1~, các cách để đến điểm ~6~ là ~[0,6],[0,4,6],[0,2,6],[0,1,3,6]~.
• Ở ví dụ ~2~, các cách để đến điểm ~15~ là ~[0,15],[0,3,12],[0,6,10,15]~

Do tuyển tin bạn nào cũng thích chơi điện tử nên thầy Tùng phải đặt gấp thuốc chống nghiện điện tử của Marisa.

Marisa có ~n~ lọ thuốc, mỗi lọ thuốc có dạng hình trụ có chiều cao là ~h~ và bán kính đáy là ~r~. Thuốc có dạng lỏng và coi như vỏ lọ thuốc không đáng kể.

~m~ bạn học sinh sẽ quyết định mỗi bạn sẽ uống một lượng thuốc giống nhau là ~X~. Lần lượt từng bạn sẽ chọn chính xác một lọ thuốc và uống một lượng ~X~ trong lọ nếu còn đủ. Để hiệu quả chống nghiện tốt nhất, ~X~ phải là lớn nhất, hãy giúp các bạn học sinh tìm giá trị này để tất cả các bạn cùng nhau cai nghiện thành công.

Input: nhập vào từ file "CAINGHIEN.INP"

• Dòng đầu tiên gồm hai số nguyên ~n,m~.
• ~n~ dòng tiếp theo, mỗi dòng gồm hay số nguyên ~h,r~.

Output: ghi ra file "CAINGHIEN.OUT"

• In ra một số thực là đáp án của bài toán. Đáp án được coi là đúng khi chênh lệch với đáp án của hệ thống không quá ~10^{-6}~.

Điều kiện

• ~1 \le n \le 10^5~.
• ~1 \le m \le 10^9~.
• ~1 \le h,r \le 10^4~.

Ví dụ

Input:

3 4
3 2
1 1
2 3

Output:

18.849556

Giới hạn

• Subtask 1 (20% số điểm): ~m = 2~.
• Subtask 2 (30% số điểm): ~n,m \le 8~.
• Subtask 3 (50% số điểm): Không có giới hạn gì thêm.

Cho ~3~ số nguyên tố ~a~, ~b~, ~c~ và số nguyên dương ~n~, hãy đếm xem trong khoảng từ ~1~ tới ~n~, có bao nhiêu số chia hết cho ít nhất một trong ~3~ số ~a,b,c~.

Input

• Gồm một dòng chứa ~4~ số ~a,b,c,n~, trong đó ~a,b,c~ là số nguyên tố và đôi một khác nhau, ~n~ là một số nguyên dương.

Output

• In ra số số nguyên dương trong khoảng ~[1,n]~ chia hết cho ít nhất một trong ~3~ số ~a,b,c~.

Điều kiện

• ~1 \le a,b,c \le 10^6~.
• ~1 \le n \le 10^{18}~.

Subtask

• ~50\%~ số điểm: ~n \le 10^6~.
• ~50\%~ số điểm: Không ràng buộc gì thêm.

Ví dụ

Input 1:

2 3 5 9

Output 1:

7

Input 2:

3 5 7 20

Output 2:

11

Cho mảng ~A~ gồm ~n~ số nguyên.

Bạn phải thay đổi ít nhất bao nhiêu số để mảng ~A~ chỉ gồm các số nguyên liên tiếp?

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

• In ra số lượng số nguyên ít nhất phải thay.

Điều kiện

• ~1 \le n \le 10^5~.
• ~1 \le A_i \le 10^9~.

Ví dụ

Input:

3
4 10 5

Output:

1

Chú ý: Thay ~10~ bằng ~6~.

Ràng buộc

• Subtask 1 ~(50\%)~: ~n \le 1000~.
• Subtask 2 ~(50\%)~: Không có ràng buộc gì thêm.

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 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~ ~(k+1 \le n \le 3000)~

• Dòng thứ hai chứa n số nguyên không âm ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 10^4 , 1 \le i \le 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.

Subtask

• 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.

Nhà máy sữa CodeMilk có ~N~ đại lý được xây dựng trên một con đường thẳng. Có thể mô tả con đường là một trục tọa độ, nhà máy sữa nằm tại vị trí gốc tọa độ, ~N~ đại lý ở tại các vị trí có tọa độ ~x_1,x_2,…,x_N~ ~(0 <x_1<x_2<⋯<x_N < 10^9)~, đại lý thứ ~i~ ~(i = 1,2,3,...,N)~ có vị trí tại tọa độ ~x_i~. Nhà máy có M chiếc xe dùng để vận chuyển sữa. Chiếc xe thứ ~i~, chuyển sữa từ đại lý ~s_i~ đến đại lý ~f_i~ ~(1 ≤s_i<f_i≤N)~, lượng xăng cần di chuyển cho ~1~ (đơn vị độ dài) là ~c_i~ (đơn vị thể tích) và số lần đổ xăng tối đa là ~r_i~, xe đi từ tọa độ ~x~ đến tọa độ ~y~ sẽ mất một lượng xăng ~|x-y|×c_i~. Các xe chỉ được di chuyển theo chiều dương của trục tọa độ và chỉ có thể đổ xăng khi đến vị trí của một đại lý nào đó. Xe không thể di chuyển nếu không còn xăng. Bình chứa xăng của ~M~ chiếc xe đều có dung tích giống nhau và bằng ~V~ (đơn vị thể tích). Khi bắt đầu xuất phát, bình xăng của tất cả các xe đã đầy xăng (không tính là một lần đổ xăng), mỗi lần đổ xăng, bình xăng được đổ đầy (tức là có ~V~ (đơn vị thể tích) xăng trong bình).</p>

Yêu cầu: Hãy tính xem, giá trị ~V~ nhỏ nhất bằng bao nhiêu để với mọi chiếc xe đều có thể vận chuyển được sữa, tức là chiếc xe thứ ~i~ có thể chuyển sữa được từ đại lý ~s_i~ đến đại lý ~f_i~ với mọi ~i=1,2,3,...,M~.

Input

• Dòng ~1~ ghi ~2~ số nguyên dương ~N~ và ~M~ tương ứng là số đại lý và số xe chở sữa.
• Dòng ~2~ ghi ~N~ số nguyên dương ~x_1,x_2,…,x_N~ ~(0<x_1<x_2<⋯<x_N<10^9)~ tương ứng là tọa độ của ~N~ đại lý.</li>
• ~M~ dòng cuối, dòng thứ ~i,(i=1,2,...,M)~ ghi ~4~ số nguyên ~s_i,f_i,c_i,r_i (1 ≤s_i<f_i≤N, 1 ≤c_i≤10^9;0≤r_i≤N)~ là thông tin của chiếc xe thứ i.</li>

Output

• Một số nguyên là giá trị nhỏ nhất của ~V~ để tất cả các xe đều có thể vận chuyển được sữa.

Subtask

• Có ~25\%~ số test ứng với ~1\le N \le 10^5, M = 1~.
• Có ~25\%~ số test ứng với ~2 \le N \le 100, 2 \le M \le 10~.
• ~50~ số test còn lại ứng với ~100 < N \le 400~, ~2 \le M \le 5.10^5~

Sample Input 1

5 2
1 3 8 12 15
1 3 10 0
2 4 5 1

Sample Output 1

70

Explanation 1

• Xe ~1~, di chuyển từ đại lý ~1~ đến đại lý ~3~, tức là tọa độ ~1~ đến tọa độ ~8~. Xe không được đổ xăng lần nào, do vậy sẽ dùng xăng trong bình lúc xuất phát. Lượng xăng ít nhất cần là ~|8-1|×10=70~ . Như vậy ~V~ bằng ~70~ thì xe ~1~ có thể đi được từ đại lý ~1~ đến đại lý ~3~.
• Xe ~2~, di chuyển từ đại lý ~2~ đến đại lý ~4~, tức là tọa độ ~3~ đến tọa độ ~12~. Xe được đổ xăng thêm một lần.
  • Đi từ tọa độ ~3~ đến tọa độ ~8~ hết ~|8-3|×5=25~.
  • Đi từ tọa độ ~8~ đến tọa độ ~12~ hết ~|12-8|×5=20~.
  • Như vậy, ~V = 25~ thì xe thứ ~2~ đi từ đại lý ~2~ đến đại lý ~3~; đổ xăng tại đại lý ~3~ và đi từ đại lý ~3~ đến đại lý ~4~.

• Do vậy, giá trị ~V~ nhỏ nhất để ~2~ xe có thể vận chuyển được sữa là ~70~.