Trong kỳ thi Olympic Tin học Sinh viên, một thí sinh đã nộp lời giải cho một bài nhiều lần.

Kết quả của các lần nộp được biểu diễn bởi một xâu S, trong đó:

• W: lời giải chưa được chấp nhận.
• A: lời giải được chấp nhận (Accepted).

Đảm bảo rằng thí sinh thi có ít nhất một lần nhận được kết quả A.

Hãy xác định thí sinh thi cần bao nhiêu lần nộp để nhận được kết quả A đầu tiên.

Input

Một dòng duy nhất chứa xâu S chỉ gồm hai ký tự W và A.

Đảm bảo:

• 1 ≤ |S| ≤ 10^5.
• S chứa ít nhất một ký tự A.

Output

In ra một số nguyên là số lần nộp bài cho đến khi thí sinh thi nhận được kết quả A đầu tiên.

Ví dụ

Input

WWWWA

Output

5

Giải thích

Bốn lần nộp đầu tiên đều chưa được chấp nhận. Ở lần nộp thứ 5, thí sinh nhận được kết quả A đầu tiên.

Đề bài

Ở giảng đường Công nghệ thông tin, TrZit nổi tiếng với tài leo rank gánh team, và cũng khét tiếng với thói quen cắm mặt vào điện thoại dưới gầm bàn. Đúng lúc combat căng thẳng nhất trong giờ Toán rời rạc, thầy giáo bắt quả tang, thu luôn điện thoại rồi quay lên bảng viết dãy số:

$$1, 2, 3, \ldots, n$$

"Mỗi lượt, em chọn hai số a và b đứng ở hai vị trí khác nhau trên bảng, xóa cả hai số này đi rồi viết vào giá trị ~\vert{}a - b\vert{}~. Lặp lại thao tác cho đến khi trên bảng chỉ còn đúng một số duy nhất, đó chính là quân bài Joker. Tìm được cách chơi để Joker đạt giá trị lớn nhất thì em được nhận lại điện thoại và qua môn. Không thì sẽ cấm thi!!!"

Nhìn chiếc máy đang nằm trên bàn giáo viên và sợ bị cấm thi, TrZit vô cùng lo lắng, run sợ. Nhưng ngặt nỗi cả buổi lo leo rank nên cậu chẳng hiểu gì về bài toán này. Thầy giáo còn ra liên tiếp t dãy số như vậy, mỗi dãy có độ dài n khác nhau. Hãy giúp TrZit tìm giá trị lớn nhất mà quân Joker có thể đạt được ở từng dãy để chuộc lại điện thoại và không phải học lại.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương t là số lượng dãy số.
• t dòng tiếp theo, mỗi dòng chứa một số nguyên dương n, mô tả dãy ~1, 2, \ldots, n~ tương ứng.

Kết quả

In ra t dòng, dòng thứ i là giá trị lớn nhất có thể của Joker ứng với n ở dòng thứ i của dữ liệu vào.

Ràng buộc và subtask

• ~1 \le t \le 10^5~
• ~1 \le n \le 10^{18}~
• Với ~n = 1~, trên bảng đã chỉ có một số nên Joker chính là số đó.

Ví dụ

Input

2
4
3

Output

4
2

Giải thích:

• Với ~n = 4~: ~\{1,2,3,4\} \to \{1,1,4\} \to \{0,4\} \to \{4\}~.
• Với ~n = 3~: ~\{1,2,3\} \to \{1,3\} \to \{2\}~.

HK là người canh giữ một mê cung bí ẩn.

Trong cuộc thi Olympic Tin học sinh viên vòng 2, các thí sinh sẽ phải vượt qua mê cung của HK để chứng minh khả năng của mình. Nhiệm vụ của HK là thiết kế mê cung sao cho càng nhiều vị trí xuất phát khiến thí sinh bị mắc kẹt càng tốt.

Mê cung có dạng một hình chữ nhật gồm n hàng và m cột. Mỗi ô trong mê cung chứa một mũi tên chỉ một trong bốn hướng:

• ~U~ - đi lên
• ~D~ - đi xuống
• ~L~ - đi sang trái
• ~R~ - đi sang phải

Để bắt đầu thử thách, thí sinh sẽ được đưa vào mê cung thông qua một cổng dịch chuyển. Cổng này có thể đưa thí sinh đến bất kỳ ô nào trong mê cung, và thí sinh không được lựa chọn trước mình sẽ xuất hiện ở đâu.

Ngay khi xuất hiện tại một ô, thí sinh bắt buộc phải di chuyển sang ô kế tiếp theo hướng mà ô hiện tại chỉ định. Thí sinh không thể thay đổi hướng hoặc đứng yên.

Nếu hướng di chuyển đưa thí sinh ra ngoài mê cung, thí sinh đã thoát thành công.

Ngược lại, nếu thí sinh quay trở lại một ô mà mình đã từng đi qua, từ đó quá trình di chuyển sẽ lặp lại vô hạn. Khi đó, thí sinh bị mắc kẹt trong mê cung.

Tuy nhiên, HK chưa hoàn thiện mê cung. Một số ô chưa có mũi tên và được ký hiệu bằng ~?~. Trước khi cuộc thi bắt đầu, HK được phép lựa chọn hướng cho từng ô ~?~.

HK muốn tận dụng cơ hội này để tạo ra một mê cung khó nhất có thể. Cụ thể, anh ta muốn lựa chọn hướng cho các ô ~?~ sao cho số lượng vị trí mà thí sinh có thể xuất hiện và bị mắc kẹt mãi mãi là lớn nhất.

Hãy giúp HK tính số lượng vị trí xuất phát lớn nhất khiến thí sinh bị mắc kẹt bằng cách gán hướng cho các ô ~?~ một cách tối ưu.

Đầu vào

Dòng đầu tiên chứa một số nguyên ~T~ là số lượng bộ test. ~(1 \le T \le 10^4)~

Với mỗi bộ test:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ lần lượt là số hàng và số cột của mê cung. ~(1 \le n, m \le 1000)~

• ~n~ dòng tiếp theo, mỗi dòng chứa một xâu gồm ~m~ ký tự mô tả hướng di chuyển của các ô trong mê cung. Mỗi ký tự là một trong:

  • ~U~ - di chuyển lên trên.
  • ~D~ - di chuyển xuống dưới.
  • ~L~ - di chuyển sang trái.
  • ~R~ - di chuyển sang phải.
  • ~?~ - ô chưa được HK quyết định hướng di chuyển.

Đảm bảo rằng tổng số ô ~n * m~ trên tất cả các bộ test không vượt quá ~10^6~.

Đầu ra

Với mỗi bộ test, in ra một số nguyên duy nhất là số lượng lớn nhất các ô mà từ đó thí sinh có thể bắt đầu và bị mắc kẹt mãi mãi sau khi HK gán hướng cho tất cả các ô ? một cách tối ưu.

Giới hạn

~20\%~ số điểm: ~n * m \le 9~ ở mỗi bộ test, ~T \le 10~.

~25\%~ số điểm: ~n * m \le 2000~ ở mỗi bộ test, tổng ~n * m~ trên tất cả bộ test không vượt quá ~2000~.

~25\%~ số điểm: Tổng ~n * m~ trên tất cả bộ test không vượt quá ~10^5~.

~30\%~ số điểm: Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

3
3 3
UUU
L?R
DDD
2 3
RRU
??D
3 3
RRD
U?D
ULL

Đầu ra

0
2
9

Giải thích

Ở bộ test thứ nhất, dù HK chọn hướng nào cho ô ~?~ thì thí sinh cũng có thể thoát khỏi mê cung.

Ở bộ test thứ hai, các ô đã được điền đều có thể thoát ra ngoài được, HK chỉ có thể điền 2 ô còn lại lần lượt là ~R~, ~L~ khiến thí sinh qua lại mãi nên kết quả là ~2~.

Ở bộ test thứ ba, ~8~ ô ngoài rìa tạo thành một chu trình khép kín nên dù ô ~?~ ở giữa HK có gán là gì thì thí sinh cũng không thể thoát khỏi mê cung nên đáp án là ~9~.

Đề bài

Trong đêm khai mạc kỳ thi Olympic Tin học Sinh viên, sân khấu được trang trí bởi n bóng đèn tạo nên những dải sáng lung linh.

Để đơn giản hóa việc điều khiển ánh sáng, sân khấu được mô hình hóa thành một trục số. Bóng đèn thứ i được đặt tại vị trí x_i và có phạm vi chiếu sáng r_i. Vì vậy, bóng đèn này chiếu sáng tất cả các vị trí thuộc đoạn:

$$ [x_i-r_i,\;x_i+r_i] $$

Một vị trí trên sân khấu được gọi là lung linh nếu vị trí đó được ít nhất hai bóng đèn cùng chiếu sáng.

Hãy tính tổng độ dài các phần sân khấu lung linh.

Input

• Dòng đầu tiên chứa số nguyên n — số lượng bóng đèn.
• n dòng tiếp theo, dòng thứ i chứa hai số nguyên x_i và r_i — vị trí và phạm vi chiếu sáng của bóng đèn thứ i.

Output

In ra một số nguyên duy nhất — tổng độ dài các phần sân khấu được ít nhất hai bóng đèn cùng chiếu sáng.

Ràng buộc

• 1 <= n <= 2 * 10^5
• -10^9 <= x_i <= 10^9
• 1 <= r_i <= 10^9
• Đảm bảo kết quả nằm trong phạm vi số nguyên 64-bit có dấu.

Subtask

• Subtask 1 (15 điểm): n <= 2
• Subtask 2 (20 điểm): n <= 2000
• Subtask 3 (25 điểm): Không tồn tại vị trí nào được nhiều hơn hai bóng đèn cùng chiếu sáng.
• Subtask 4 (40 điểm): Không có ràng buộc bổ sung.

Ví dụ 1

Input

3
5 5
11 5
20 2

Output

4

Giải thích

Ba bóng đèn lần lượt chiếu sáng các đoạn:

$$ [0,10],\quad[6,16],\quad[18,22] $$

Hai bóng đèn đầu tiên cùng chiếu sáng đoạn [6,10], có độ dài 4.

Bóng đèn thứ ba không giao với vùng chiếu sáng của hai bóng còn lại.

Vì vậy tổng độ dài phần sân khấu lung linh là:

$$ 10-6=4 $$

Đề bài

Trong một cuộc thi OLP, TrViệt gặp một bài toán tính tổng dãy số khá đơn giản. Sau khi giải xong, TrViệt chợt nảy ra một câu hỏi:

Nếu thay vì tính tổng các phần tử, ta tính tổng giá trị nhỏ nhất của tất cả các dãy con liên tiếp thì sao?

TrViệt quyết định ra một bài toán để thử thách mọi người. Liệu bạn có thể giải bài toán này không?

Cho một mảng A gồm N số nguyên: ~a_0, a_1, \dots, a_{N-1}~.

Một dãy con liên tiếp (subarray) là một đoạn các phần tử nằm kề nhau trong mảng, được xác định bởi hai chỉ số l và r với ~0 \le l \le r < N~.

Ví dụ, với mảng [3, 1, 2], các subarray là: [3], [1], [2], [3, 1], [1, 2], [3, 1, 2].

Yêu cầu: Với mỗi cặp chỉ số (l, r) thỏa mãn ~0 \le l \le r < N~, đặt:

$$f(l, r) = \min(a_l, a_{l+1}, \dots, a_r)$$

Hãy tính:

$$S = \sum_{0 \le l \le r < N} f(l, r)$$

Vì kết quả có thể rất lớn, hãy in kết quả theo modulo ~10^9 + 7~.

Dữ liệu vào (Input)

• Dòng 1: một số nguyên N — số phần tử của mảng.
• Dòng 2: N số nguyên ~a_0, a_1, \dots, a_{N-1}~ — giá trị các phần tử của mảng.

Ràng buộc: ~1 \le N \le 10^6~ và ~1 \le a_i \le 10^9~.
Giới hạn cụ thể của N phụ thuộc vào từng subtask (xem phần Subtask).

Kết quả (Output)

In ra một số nguyên duy nhất là giá trị của ~S~ modulo ~10^9 + 7~.

Ví dụ

Ví dụ 1

Input

4
3 1 2 4

Output

17

Giải thích: Các subarray và giá trị nhỏ nhất tương ứng:

• [3] ⇒ min = 3
• [1] ⇒ min = 1
• [2] ⇒ min = 2
• [4] ⇒ min = 4
• [3, 1] ⇒ min = 1
• [1, 2] ⇒ min = 1
• [2, 4] ⇒ min = 2
• [3, 1, 2] ⇒ min = 1
• [1, 2, 4] ⇒ min = 1
• [3, 1, 2, 4] ⇒ min = 1

Tổng = 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17.

Ví dụ 2

Input

3
1 1 1

Output

6

Giải thích: Mảng có 6 subarray: [1], [1], [1], [1, 1], [1, 1], [1, 1, 1]. Cả 6 đều có min = 1, nên tổng = 6.

Subtask

Bộ test được chia thành 4 subtask:

nqson đang sống ở một thế giới có vô hạn thành phố, được đánh số thứ tự từ 1 đến vô cùng. Giao thông ở đây rất đặc biệt: Từ bất kỳ thành phố ~x~ nào, bạn luôn đứng trước 2 con đường (Trái và Phải), mỗi con đường lại chia thành 2 nhánh nhỏ. Tổng cộng từ thành phố ~x~ sẽ có 4 vé thông hành dẫn đến các đích sau:

• Nếu chọn đường bên Trái:

  • Đi nhánh trái: Dẫn tới thành phố ~x \times 2 - 1~
  • Đi nhánh phải: Dẫn tới thành phố ~x \times 2~

• Nếu chọn đường bên Phải:

  • Đi nhánh trái: Dẫn tới thành phố ~x \times 2~
  • Đi nhánh phải: Dẫn tới thành phố ~x \times 2 + 1~

Mỗi nhánh đường con chỉ được đi qua tối đa 1 lần duy nhất. Do hầu hết các nhánh đều dẫn ta tiến về các thành phố có số lớn hơn, ngoại trừ ở thành phố 1: nhánh Trái - trái sẽ dẫn ngược về chính nó (~1 \times 2 - 1 = 1~). Vì vậy sẽ có đúng 2 cách để bắt đầu:

1. Đứng yên không di chuyển (tốn 0 bước).
2. Dạo một vòng qua nhánh Trái - trái để trở về lại thành phố 1 (lúc này nhánh này sẽ bị khóa và không thể đi tiếp vòng nữa).

Có ~t~ ngày, mỗi ngày mới bắt đầu, nqson sẽ được hệ thống đưa trở lại thành phố 1. Bạn hãy giúp nqson mỗi ngày tính xem có tất cả bao nhiêu cách khác nhau để di chuyển từ thành phố 1 đến thành phố ~n~.

Lưu ý: Vì kết quả có thể rất lớn, hãy in ra phần dư của số cách tìm được khi chia cho ~10^9+7~.

Đầu vào

Dòng đầu tiên ~t~ là số ngày

~t~ dòng tiếp theo, mỗi dòng chứa số nguyên dương ~n~ - đại diện cho thành phố đích mà nqson muốn tới.

Đầu ra

~t~ dòng, mỗi dòng in ra một số nguyên duy nhất là số cách di chuyển từ thành phố 1 tới thành phố ~n~ vào ngày đó (sau khi đã modulo cho ~10^9+7~).

Giới hạn

• Subtask 1 (25% số điểm): ~t = 1, 1 \le n \le 10^3~.
• Subtask 2 (25% số điểm): ~t = 1, 1 \le n \le 10^6~.
• Subtask 3 (25% số điểm): ~t \le 10^5, 1 \le n \le 10^7~.
• Subtask 4 (25% số điểm): ~t \le 10^6, 1 \le n \le 10^{18}~.

Ví dụ 1

Đầu vào

2
2
1

Đầu ra

4
2

Giải thích

Có 4 cách khác nhau để đi từ thành phố 1 tới thành phố 2:
- Cách 1: Từ 1 --> rẽ nhánh (Trái - phải) --> đến 2.
- Cách 2: Từ 1 --> rẽ nhánh (Phải - trái) --> đến 2.
- Cách 3: Từ 1 --> rẽ nhánh (Trái - trái) vòng lại 1 --> rẽ nhánh (Trái - phải) --> đến 2.
- Cách 4: Từ 1 --> rẽ nhánh (Trái - trái) vòng lại 1 --> rẽ nhánh (Phải - trái) --> đến 2.

Có đúng 2 trạng thái xuất phát hợp lệ tại thành phố 1:
- Cách 1: Không làm gì cả (đứng yên tại chỗ).
- Cách 2: 1 --> rẽ nhánh (Trái - trái) --> 1. Nhánh này lúc này đã bị khóa nên không thể đi tiếp vòng 2.

Tại học viện ma thuật, hai pháp sư tài năng là Alice và Bob đang chuẩn bị ký kết một "Khế ước Ma pháp" để chia sẻ một kho báu vĩ đại.

Kho báu này bao gồm ~n - 1~ viên đá ma thuật khác nhau, được đánh số từ ~1, 2, 3, \dots, n-1~. Cường độ ma lực của viên đá thứ ~i~ chính là ~i + 1~ (tức là các viên đá có cường độ ma lực từ ~2~ đến ~n~).

Theo ghi chép cổ, mỗi mức cường độ ma lực được hình thành từ sự kết hợp của các "Cổ ngữ căn nguyên" - chính là các ước số nguyên tố của mức cường độ đó. Ví dụ, viên đá có cường độ ma lực ~12~ được hình thành từ cội nguồn ~2~ và cội nguồn ~3~.

Bây giờ, Alice và Bob mỗi người muốn chọn ra một tập hợp các viên đá mang về nghiên cứu. Tuy nhiên, Khế ước Ma pháp quy định rất nghiêm ngặt: Để tránh xảy ra một vụ nổ cộng hưởng phép thuật, tập hợp đá của Alice và tập hợp đá của Bob tuyệt đối không được chứa bất kỳ "Cổ ngữ căn nguyên" nào chung. Cụ thể hơn, nếu Alice chọn một viên đá có ma lực là ~x~ và Bob chọn một viên đá có ma lực là ~y~, thì ~x~ và ~y~ phải luôn nguyên tố cùng nhau.

Hãy tính xem có tổng cộng bao nhiêu cách khác nhau để Alice và Bob chọn đá ma thuật thỏa mãn Khế ước. Chú ý, một pháp sư có thể không lấy bất cứ viên đá nào.

Đầu vào

Một dòng chứa một số nguyên dương ~n~ (~2 \le n \le 500~).

Đầu ra

Một dòng chứa một số nguyên duy nhất là kết quả bài toán. Do kết quả có thể rất lớn, bạn chỉ cần đưa ra kết quả sau khi chia lấy dư cho ~998244353~.

Giới hạn

• Subtask ~1~ (~30%~ số điểm): ~2 \le n \le 30~.
• Subtask ~2~ (~20%~ số điểm): ~2 \le n \le 100~.
• Subtask ~3~ (~20%~ số điểm): ~2 \le n \le 200~.
• Subtask ~4~ (~30%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

4

Đầu ra

21

Trong quá trình tối ưu hóa kiến trúc hạ tầng backend, hệ thống lõi được mô phỏng dưới dạng một mạng lưới gồm ~n~ máy chủ, được đánh số từ ~1~ đến ~N~. Cấu trúc mạng này có dạng một cây có gốc, trong đó máy chủ 1 là máy chủ trung tâm. Máy chủ ~p_i~ là máy chủ cấp trên trực tiếp của máy chủ thứ ~i~ với mọi ~2 \le i \le N~. Ban đầu, tài nguyên phân bổ (tính bằng đơn vị băng thông) tại tất cả máy chủ đều bằng ~0~.

Ban được cấp quyền sử dụng một bộ điều phối đặc biệt có thể tăng lượng tài nguyên cho các máy chủ. Khi cung cấp ba tham số ~X, Y~ và ~K~ cho bộ điều phối, hệ thống sẽ tự động phân bổ thêm tài nguyên cho tất cả các máy chủ nằm trong nhánh mạng do máy chủ ~X~ quản lý. Cụ thể, nếu máy chủ ~X'~ nằm trong cây con gốc ~X~, lượng tài nguyên của ~X'~ sẽ được cộng thêm một lượng là ~\lfloor \frac{Y}{K^d} \rfloor~, trong đó ~d~ là khoảng cách trên đường đi ngắn nhất từ ~X~ đến ~X'~. Nói cách khác, với một thao tác, lượng tài nguyên của bản thân máy chủ ~X~ tăng thêm ~Y~, các máy chủ con trực tiếp của ~X~ tăng thêm ~\lfloor \frac{Y}{K} \rfloor~, các máy chủ là con của các máy chủ con trực tiếp của ~X~ tăng thêm ~\lfloor \frac{Y}{K^2} \rfloor~.

Yêu cầu: Có ~Q~ thao tác cần thực hiện tuần tự trên hệ thống. Mỗi thao tác thuộc một trong hai loại sau:

1. 1 X Y K: Kích hoạt bộ điều phối tại máy chủ ~X~ với tham số ~Y~ và mức độ suy hao là ~K~.

2. 2 X: Cho biết tổng lượng tài nguyên đang được phân bổ cho toàn bộ các máy chủ nằm trong nhánh mạng do máy chủ ~X~ quản lý (tổng tài nguyên của cây con gốc ~X~).

Đầu vào

• Dòng thứ nhất chứa hai số nguyên dương ~N~ và ~Q~ (~1 \le N, Q \le 5 \times 10^5~) - lần lượt là số lượng máy chủ và số lượng thao tác cần thực hiện.
• Dòng thứ hai chứa ~N - 1~ số nguyên ~p_2, p_3, \ldots, p_n~ (~1 \le p_i < i~) - trong đó ~p_i~ là máy chủ cấp trên trực tiếp của máy chủ ~i~.
• ~Q~ dòng tiếp theo, mỗi dòng mô tả một thao tác theo một trong hai định dạng:
  • 1 X Y K (~1 \le X \le N; 1 \le Y, K \le 2 \times 10^5~).
  • 2 X (~1 \le X \le N~).

Đầu ra

Với mỗi thao tác loại 2 theo đúng thứ tự trong đầu vào, in ra một dòng một số nguyên duy nhất là kết quả của truy vấn đó.

Giới hạn

• Subtask ~1~ (~10\%~ số điểm): ~N, Q \le 1000~.
• Subtask ~2~ (~10\%~ số điểm): ~K = 1~ trong mọi thao tác loại ~1~.
• Subtask ~3~ (~15\%~ số điểm): Mỗi máy chủ kết nối trực tiếp với tối đa ~2~ máy chủ khác.
• Subtask ~4~ (~15\%~ số điểm): Cấu trúc mạng là một cây nhị phân hoàn hảo.
• Subtask ~5~ (~20\%~ số điểm): ~N, Q \le 10^5~.
• Subtask ~6~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

6 5
1 1 2 2 3
1 1 10 2
2 2
2 1
1 2 20 3
2 2

Đầu ra

9
26
41

Trong kỳ thi Olympic Tin học Sinh viên, đàn chim cánh cụt tổ chức đại hội xây tháp bánh cá. Mỗi con phụ trách một tháp, nhưng khâu kiểm kê cho thấy các tháp cao thấp lộn xộn: con thì xây quá hăng, con thì có vẻ đã ăn mất vài tầng.

Có N tháp, tháp thứ i hiện cao hᵢ tầng. Ban tổ chức muốn chỉnh sửa để tất cả các tháp có cùng chiều cao. Họ có thể thực hiện các thao tác sau:

• Thêm một tầng vào một tháp, chi phí A.
• Bỏ tầng trên cùng của một tháp không rỗng, chi phí R.
• Chuyển tầng trên cùng từ một tháp không rỗng sang một tháp khác, chi phí M.

Hãy tính chi phí nhỏ nhất để các tháp có cùng chiều cao. Chim cánh cụt rất kiên nhẫn, nhưng ngân sách bánh cá thì không vô hạn.

Input

Dòng đầu gồm bốn số nguyên N, A, R, M: số tháp, chi phí thêm tầng, chi phí bỏ tầng và chi phí chuyển tầng.

Dòng thứ hai gồm N số nguyên h₁, h₂, …, hₙ: chiều cao ban đầu của các tháp.

Đảm bảo:

• 1 ≤ N ≤ 10⁵.
• 1 ≤ A, R, M ≤ 10⁴.
• 0 ≤ hᵢ ≤ 10⁹.

Output

In ra một số nguyên là chi phí nhỏ nhất để đưa tất cả các tháp về cùng chiều cao.

Ví dụ

Input:

3 1 100 100
1 3 8

Output:

12

Giải thích

Cách tốt nhất là thêm 1 tầng vào tháp 1 và 2 cho đến khi bằng tháp 3.

Chấm điểm

• N ≤ 100 và max(hᵢ) ≤ 100: 25%.
• max(hᵢ) - min(hᵢ) ≤ 2000: 25%.
• M ≥ A + R: 25%.
• Không có giới hạn: 25%.

Trong kỳ thi Olympic Tin học Sinh viên, Mạnh NĐ tham gia giải chạy vượt bậc đá. Vì Mạnh bật nhảy rất tự tin nhưng không giỏi tiết kiệm năng lượng, ban tổ chức gắn cho mỗi cú nhảy một mức phí cố định C, cộng thêm khoản phí phụ thuộc vào độ chênh cao giữa hai bậc.

Có N bậc đá nằm trên đường đua, đánh số từ 1 đến N. Bậc thứ i có độ cao hᵢ, trong đó các độ cao tăng nghiêm ngặt theo thứ tự. Mạnh bắt đầu ở bậc 1 và cần đến bậc N. Từ bậc i, Mạnh có thể nhảy đến bất kỳ bậc j thỏa mãn j > i.

Năng lượng tiêu tốn cho cú nhảy từ bậc i đến bậc j là (hⱼ - hᵢ)² + C.

Hãy tính tổng năng lượng nhỏ nhất để Mạnh đi từ bậc 1 đến bậc N.

Input

Dòng đầu gồm hai số nguyên N và C - số bậc đá và phí cố định cho mỗi cú nhảy.

Dòng thứ hai gồm N số nguyên h₁, h₂, …, hₙ - độ cao các bậc theo thứ tự.

Đảm bảo:

• 1 ≤ N ≤ 2·10⁵.
• 1 ≤ C ≤ 10¹².
• 1 ≤ h₁ < h₂ < … < hₙ ≤ 10⁶.

Output

In ra một số nguyên là tổng năng lượng nhỏ nhất để Mạnh đến bậc N.

Ví dụ

Input:

5 6
1 2 3 4 5

Output:

20

Chấm điểm

• N ≤ 20: 33%.
• N ≤ 5000: 33%.
• Không có giới hạn bổ sung: 34%.