Cảm thấy quá mệt mỏi với việc nghỉ dịch Covid-19 ở nhà, Doraemon rủ Nobita và những người bạn đi phiêu lưu ở hòn đảo kho báu ở Mỹ cách đây 1500 năm. Sau khi đến đảo, vì quá mệt mỏi sau chuyến hành trình dài, mọi người quyết định nghỉ chân một lúc. Tại đây, Doraemon chợt nhớ ra việc học hành bết bát của Nobita nên đã đố Nobita một câu hỏi để ôn lại các thuật toán khủng như Suffix Array, Treap, Palindrome Tree, etc…

Doraemon cho Nobita 1 chiếc hộp đặc biệt biết cứ bỏ \(M\) quả chuối vào chiếc hộp này thì tất cả quả chuối sẽ biến mất. Sau đó Doraemon cho Nobita 2 số \(L\) và \(R\) và bắt Nobita phải chọn 2 số \(i\) và \(j\) \((i < j)\) trong đoạn \(L\) và \(R\). Sau khi chọn Nobita sẽ có được tổng số chuối là \(i \times j\). Tiếp theo, cậu sẽ phải liên tục bỏ \(M\) quả chuối vào thùng đến khi số chuối còn lại ít hơn \(M\). Vì Nobita là 1 cậu bé “ngốc nghếch” nên cậu muốn biết được số lượng chuối còn lại ít nhất sau khi bỏ vào thùng.

Input

• Một dòng duy nhất, gồm ba số lần lượt là \(L, R, M\) \((1 \leq L < R \leq 2000, 1 \leq M \leq 2000)\).

Output

• Một dòng duy nhất, là kết quả của bài toán.

Scoring

• Ở bản dễ, \(1 \leq L < R \leq 2000\).
• Ở bản khó, \(1 \leq L < R \leq 10^9\).

Example

4 7 13 

2

Cho một xâu ký tự \(S\) chỉ gồm các chữ cái thường a..z. Xâu đối xứng là xâu kí tự mà khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. Ví dụ: \(madam\), \(ioi\) là các xâu đối xứng.

Yêu cầu: Với xâu ký tự \(S\) cho trước, hãy tính số ký tự bỏ đi ít nhất để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.

Ví dụ:

• Cho xâu aammmda thì cần bỏ 2 ký tự a và m thì xâu còn lại là ammda và xếp lại thành madam là xâu đối xứng.
• Cho xâu aaabbcc thì không cần bỏ ký tự thì xâu đó xếp lại thành bcaaacb là xâu đối xứng.

Input

• Một xâu ký tự \(S\) có \(n\) ký tự (\(n \le 10^5\)) chỉ gồm các ký tự chữ cái thường a..z.

Output

• Một số nguyên là số lượng ký ít nhất cần bỏ để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.

Scoring

• Subtask \(1\): (\(30\%\) số điểm): chỉ chứa 2 ký tự a và b.
• Subtask \(2\): (\(30\%\) số điểm): chỉ chứa 3 loại ký tự bất kỳ.
• Subtask \(3\): (\(40\%\) số điểm): trường hợp còn lại.

Example

aammmda

2

aaabbcc

0

Tam giác vuông cân là tam giác vuông có hai cạnh góc vuông bằng nhau. Chúng ta có thể sử dụng một số dấu sao để tạo thành một tam giác vuông cân. Nhiệm vụ của bạn rất đơn giản, cho trước số dấu sao, hãy xác định xem có thể xếp chúng thành một tam giác vuông cân được hay không

Input

• Một dòng chứa số nguyên \(N\) \((1 \leq N \leq 10^{18})\) là số chấm tròn

Output

• Một dòng chứa kết quả, nếu các chấm tròn có thể tạo thành tam giác vuông cân, in ra YES, ngược lại in ra NO

Scoring

• Nếu chương trình chạy đúng những trường hợp \(N \leq 10^{14}\), thí sinh sẽ được \(8/13\) testcase.
• Nếu chương trình chạy đúng những trường hợp \(N \leq 10^{18}\), thí sinh sẽ được \(13/13\) testcase.

Example

3 

YES

*

*  *

Từ một số nguyên dương \(k\) ban đầu, ta thực hiện biến đổi số \(k\) theo quy tắc biến đổi sau đây:

Nếu \(k\) chia hết cho \(6\) thì thay số \(k\) bởi thương \(k:6\); còn nếu \(k\) không chia hết cho \(6\) thì thay số \(k\) bởi tích \(3 \times k\).

Yêu cầu: Hãy xác định số lần biến đổi theo quy tắc trên để \(k\) bằng \(1\). Trong trường hợp không thể biến đổi \(k\) bằng \(1\) thì in ra kết quả \(-1\).

Input

• Một dòng chứa số nguyên \(k\) \((k \leq 10^{9})\).

Output

• Số nguyên \(m\) là số lần biến đổi để \(k\) bằng \(1\).

Example

12 

3

10

-1

ami đang đi vượt ải Codeforces. Để trở thành master, ami phải vượt qua \(n\) con quái vật. Con quái vật thứ \(i\) sẽ làm ami hao tổn \(a_i\) công lực. Và vì các ải này diễn ra liên tiếp, ami không có thời gian để hồi phục công lực. ami sẽ gục ngã nếu sau một trận chiến, công lực còn lại bé hơn hoặc bằng \(0\).

Ví dụ: nếu ban đầu ami có \(10\) công lực, và con quái vật đầu tiên có sức mạnh \(a_1 = 4\), ami sẽ vượt ải thành công và còn \(6\) công lực. Nếu con quái vật thứ hai có sức mạnh ít nhất là \(6\), ami sẽ bị đánh gục ở ải này.

ami đã nghiên cứu rất kỹ về đối thủ của mình. Anh biết rằng sức mạnh của chúng tương ứng là \(a_1, a_2, ..., a_n\). Và để thêm phần kỹ càng, ami sẽ mang theo một bộ giáp có thể chống được \(k\) sát thương. Nói cách khác, nếu ami sử dụng bộ giáp này khi đấu với quái vật thứ \(i\) thì chỉ mất đi \(max(0, a_i - k)\) công lực. Tuy nhiên, bộ giáp này chỉ sử dụng được cho \(1\) ải duy nhất và ami phải tính toán sử dụng sao cho tối ưu.

ami muốn vượt qua cả \(n\) ải này. Hỏi ban đầu anh phải chuẩn bị ít nhất bao nhiêu công lực? Biết rằng ami rất bá đạo nên sẽ sử dụng giáp một cách tối ưu.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, k \ (k \leq 10^9)\) tương ứng là số quái vật và sức mạnh của giáp.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\) là sức mạnh của \(n\) con quái vật.

Output

• In ra một số nguyên là công lực ít nhất ami cần chuẩn bị trước khi vượt ải.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 1000\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \leq 10^5\).

Example

5 5
1 2 6 7 3

15

5 3 
1 1 1 1 1

5

Cho một xâu \(S\) được chỉ gồm các ký tự chữ cái thường \(‘a’… ‘z’\) được gọi là xâu chẵn nếu số lần xuất hiện của từng chữ cái trong xâu \(S\) là số chẵn.

Input

• Một dòng chứa duy nhất xâu \(S\) có số lượng ký tự không quá 255 ký tự.

Output

• Nếu xâu \(S\) là xâu chẵn thì in ra "Yes". Ngược lại thì in ra "No".

Example

adccda  

Yes

adcccdaa

No

Số Hacking Number được định nghĩa là một số CHẴN có thể phân tích ra thừa số nguyên tố, sao cho số lượng thừa số nguyên tố CHÍNH XÁC là ba thừa số (Tính cả các số trùng nhau).

Ví dụ như số \(8\) là một số Hacking Number vì nó có thể phân tích ra là \(8 = 2 * 2 * 2\) và còn là số chẵn.

\(12\) cũng là Hacking Number vì nó là số chẵn phân tích ra là \(12 = 2 * 2 * 3\).

Còn số \(27\) dù có thể phân tích ra là \(27 = 3 * 3 * 3\) nhưng lại không phải Hacking Number do nó là số LẺ.

Ví dụ cuối cùng là số \(4\), dù là số chẵn nhưng chỉ có \(2\) phần tử sau khi phân tích ra thừa số nguyên tố \((4 = 2 * 2)\)

Cho một số \(N\) \((1 \le N \le 10^{9})\) và nhiệm vụ của bạn là xác định xem nó có phải Hacking Number không?

Input

• Một số tự nhiên \(N\) \((1 \leq N \leq 10^{9})\)

Output

• In ra Yes nếu như \(N\) là Hacking Number, No nếu không phải.

Example

8

Yes

9

No

King vô cùng thích thú khi được học về các chữ số, đặc biệt cậu rất thích tính
xem con số nào có tổng các chữ số lớn nhất. Do đó, khi gặp một số King rất muốn biết
số đó có tổng các chữ số bằng bao nhiêu. Các bạn hãy viết chương trình để giúp King
thực hiện mong muốn trên nhé.

Yêu cầu: Cho một số tự nhiên \(n\). Hãy tính tổng các chữ số của \(n\).

Ví dụ: Với \(N = 12\) thì tổng các chữ số của nó là \(1 + 2 = 3\).

Input

• Một số nguyên dương \(n (n \le 10^{64})\)

Output

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

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(n \le 10^6\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 10^{18}\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^{64}\).

Example

12

3

Để sẵn sàng triển khai tiêm Vacxin cho địa phương có nguy cơ bùng dịch cao, người ta cần dự trữ không ít hơn \(n\) liều vacxin. Hiện nay trong kho đang có \(m\) liều vacxin, trong nước có hai cơ sở \(A, B\) sản xuất Vacxin. Nếu làm việc hết công suất, cơ sở \(A\) mỗi ngày sản xuất được pa liều, còn cơ sở \(B\) sản xuất được pb liều. Em hãy xác định sớm nhất sau bao nhiêu ngày sẽ có đủ \(n\) liều vacxin?

Input

• Dòng đầu ghi hai số nguyên \(n, m (0\le n,m\le 10^8)\)
• Dòng thứ hai chứa hai số nguyên \(pa, pb (0\le pa,pb\le 10^5)\)

Output

• Ghi một số nguyên là số ngày sớm nhất có đủ vacxin dự trữ theo kế hoạch.

Example

200 50 
20 35 

3

Cho mảng \(A\) gồm \(N\) số nguyên dương.

Yêu cầu: Hãy in ra tổng tất cả các cặp \((A_i \times A_j)\) với mọi cặp \((i,j)\) thỏa mãn \(1\le i < j\le N\) , chia lấy dư cho \(({10}^9+7)\). Hay nói cách khác: tổng tất cả các cặp tích của mảng.

Input

• Dòng đầu tiên nhập số nguyên dương \(N\) \((2\le N\le2\times{10}^5)\).
• Dòng còn lại nhập \(N\) số tiếp theo – là các phần tử của mảng \((1\le A_i\le{10}^9)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài sau khi chia lấy dư cho \(({10}^9+7)\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Có \(N\le{10}^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
1 2 3

11

Một dự án phần mềm cần triển khai trong \(n\) tháng đánh số từ \(1\) tới \(n\). Biết rằng:

• Bắt đầu vào một tháng, dự án có quyền thuê thêm nhân công. Để thuê mỗi nhân công cần một khoản chi phí \(H\) (trả cho nhà tuyển dụng).
• Mỗi nhân công được thuê sẽ được trả một khoản lương \(S\) mỗi tháng kể cả khi không làm việc.
• Kết thúc một tháng, dự án có quyền sa thải nhân công. Để sa thải mỗi nhân công cần trả một khoản chi phí \(D\).
• Không có nhân công nào trước khi dự án bắt đầu. Mỗi tháng \(i\) cần tối thiểu \(a_i\) nhân công. Kết thúc tháng thứ \(n\), toàn bộ nhân công phải bị sa thải.

Yêu cầu: Hãy giúp ông giám đốc dự án xây dựng kế hoạch thuê nhân công để dự án được hoàn thành với chi phí thuê nhân công ít nhất có thể.

Input

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

• Dòng 1 chứa số tháng \(n\) \((1 \leq n \leq 4 \cdot 10^5)\).
• Dòng 2 chứa ba số nguyên dương \(H,S,D\) \((H,S,D \leq 10^6)\).
• Dòng 3 chứa \(n\) số nguyên dương \(a_1,a_2,\ldots,a_n\) \((∀i:a_i \leq 10^6 )\).

Output

Ghi ra file văn bản PROJECT.OUT một số nguyên duy nhất là chi phí tối thiểu tìm được.

Example

3
4 5 6
10 9 11

265

Nguồn: Thầy Lê Minh Hoàng