ko thích nói

Cho 1 dãy gồm \(n\) số, tính tổng các số khác 0

Input

• Dòng 1: Số \(n(1 \leq n \leq 10^5)\)
• Dòng 2: Gồm \(n\) số nguyên, mỗi số có giá trị tuyệt đối không quá \(10^9\)

Output

• In ra tổng các số khác 0 vừa nhập

Example

5
2 3 4 5 0

14

Cho dãy số \(A\) gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Đếm số lượng số âm, số dương trong dãy số.

Input

• Dòng đầu tiên gồm số nguyên dương \(N\) \((N \le 10^5)\);
• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,..,a_N\) \((|a_i| \le 10^9)\)

Output

• In ra số lượng số âm, số lượng số dương.

Example

5
-2 4 0 5 4 

1 3

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Với mỗi chỉ số \(1 \le i \le N\) đếm xem có bao nhiêu phần tử bé hơn \(a_i\).

Input

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

Output

• In ra \(N\) số nguyên, số thứ \(i\) cho biết số phần tử nhỏ hơn \(a_i\).

Scoring

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

Example

5
3 2 1 1 2 

4 2 0 0 2

Ami có một dãy số nguyên dương liên tiếp từ \(l\) đến \(r\). LN lại cho Ami hai số \(t\) và \(k\). Cần đếm xem có bao nhiêu số nguyên \(x\) thoả mãn:

1. \(l \le x \le r\)
2. \(x^t\) có đúng \(k\) chữ số \(0\) tận cùng

Input

• Dòng đầu tiên chứa số nguyên dương \(Q\) (\(Q \le 300\, 000\)) - số lượng test.
• \(n\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên dương \(l,r,t,k\) (\(l,r,t,k \le 10^{17}\)).

Output

• Ứng với mỗi bộ dữ liệu, in ra kết quả của bài toán.

1
1 110 2 2

10

Cho 2 chuỗi kí tự \(a\) và \(b\). Hãy in ra độ chênh lệnh độ dài của \(2\) chuỗi.

Input

• Dòng thứ nhất là chuỗi kí tự a.
• Dòng thứ hai là chuỗi kí tự b.

Output

• Gồm một dòng duy nhất là kết quả cần tìm.

Lưu ý: Chuỗi nhập vào có thế có dấu khoảng trống (dùng getline).

Example

zzzzzz aa
ssssss aaaaaa 

4

Cho số tự nhiên \(n\) \((0 \le n \le 100)\).
In ra hai số nguyên \(a\),\(b\) chứa được trong \(32\)-bit thỏa mãn \(a+b=n\).

Input

• Số tự nhiên \(n\).

Output

• Hai số nguyên \(a\), \(b\) thỏa mãn yêu cầu đề bài, cách nhau một dấu cách.

Example

5 

2 3

Cho một xâu kí tự, hãy kiểm tra tính đối xứng của nó. Một xâu kí tự được gọi là xâu đối xứng nếu ta đọc xâu này từ trái sang phải hoặc từ phải sang trái là như nhau.

Input

• Một xâu ký tự \(S\).

Output

• In ra \(YES\) nếu \(S\) là xâu đối xứng, ngược lại in ra \(NO\).

Constraints

• \(1 \leq S.size() \leq 255\)

Example

abccba 

YES

abcccc 

NO

Cho một chuỗi kí tự gồm \(n\)n kí tự bất kì \((n≤100)\). Hãy đổi tất cả chữ hoa có trong chuỗi thành chữ thường. Xuất chuỗi ra màn hình.

Input

• Gồm một dòng duy nhất là một chuỗi kí tự

Output

• In chuỗi đã đổi ra màn hình

Example

4I1K2D14Ti 

4i1k2d14ti

Cho một xâu \(S\) chỉ gồm các chữ cái in thường. Cách mô tả rút gọn của xâu \(S\) như sau:

• Chọn ra một xâu \(X\) ngắn nhất có thể và một số nguyên dương \(K\), sao cho khi viết xâu \(X\) lặp lại \(K\) lần thì ta thu được xâu \(S\)
• Ghép \(K\) và \(X\), ta thu được xâu rút gọn của \(S\).

Ví dụ:

• Xâu rút gọn của “abababab” là “4ab”
• Xâu rút gọn của “aaa” là “3a”
• Xâu rút gọn của “abac” là “1abac”

Input

• Gồm một dòng duy nhất chứa xâu \(S\) có độ dài không quá \(1000\).

Output

• In ra xâu rút gọn của xâu \(S\).

Example

abababab 

4ab

aaa 

3a

abac 

1abac

Một xâu ký tự có thể nén lại thành một xâu mới bằng cách nén các ký tự giống nhau đứng cạnh nhau. Ví dụ trong xâu \(aaaa\) sẽ nén thành \(4a\). Hãy lập trình để nén một xâu ký tự thường theo cách trên.

Input

• Một xâu các ký tự là chữ cái thường có tối đa \(10^5\) ký tự.

Output

• Một xâu ký tự sau khi nén.

Example

mmaabbbeeeezh 

2m2a3b4ezh

Tudor đang ngồi trong lớp học, thế nhưng anh ta lại không chú ý vào bài học. Thế nhưng anh ấy bị giáo viên Toán gọi lên bảng để làm một số bài tập. Vì giáo viên không mong đợi gì quá nhiều ở Tudor nên anh ấy chỉ cần làm bài toán cộng đơn giản. Tuy bài toán có thể dễ với bạn nhưng không dễ với Tudor, vì vậy hãy giúp anh ấy !!

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((n \le 100\, 000)\) - số bộ dữ liệu vào.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên có giá trị tuyệt đối không quá \(1\,000\,000\,000\), cách nhau bởi một dấu cách.

Output

• Ứng với mỗi bộ dữ liệu, in ra kết quả của bài toán tính tổng.

Example

2
1 1
-1 0 

2
-1

Oo rất thích việc giải quyết các bài toán. Vào một ngày trong chuỗi những ngày phong tỏa do COVID-19, Oo phải giải quyết bài toán sau: "Cho các điểm trên mặt phẳng tọa độ \(\text{Oxy}\), điểm thứ \(i\) có tọa độ \((2019-a_i,2a_i)\). Hãy tìm hai điểm có khoảng cách lớn nhất trong các cặp điểm được tạo ra bởi các điểm trên và in ra bình phương khoảng cách của cặp điểm đó".

Sau 10 ngày nghiên cứu mệt mỏi, cuối cùng Oo đã đưa ra một công thức khoảng cách giữa hai điểm bất kỳ trên mặt phẳng tọa độ. Bình phương khoảng cách giữa hai điểm \((x_1,y_1)\) và \((x_2,y_2)\) là \((x_1-x_2)^2+(y_1-y_2)^2\). Từ ý tưởng thiên tài đó, Oo đã code ra một lời giải "thiên tài". Không may mắn thay, lời giải đó quá dài để viết ra ở đây nhưng Oo vẫn tự hào nói với bạn cái cốt lõi của ý tưởng: Duyệt qua tất cả các cặp điểm và tìm ra cặp điểm tối ưu. Phần chứng minh của công thức và phần code sẽ do người làm tự thân vận động nhé :).

Bất ngờ thay, Oo nhận ra rằng giới hạn của bài toán là \(10^5\). Nhưng giống như lần trước, Oo đã không tốn quá nhiều thời gian để nghĩ ra một ý tưởng thiên tài khác: thuật toán ngẫu nhiên (randomization algorithm). Nghe có vẻ đáng sợ nhỉ ? Đừng lo !! Oo đã cung cấp lời giải cho điều này như sau: Chọn ra \(k\) điểm bất kỳ từ \(n\) điểm trên và sử dụng lời giải bên trên cho \(k\) điểm đã chọn này. Nhưng chúng ta phải chọn như thế nào ? Vâng, sau \(9954\) thí nghiệm, Oo có thể tự tin nói với bạn rằng \(k\) sẽ không bao giờ vượt quá \(5000\).

Không quá bất ngờ, code trên của Oo đã bị Wrong Answer vài lần. Nhưng điều đó không có vấn đề gì vì Oo đã giải quyết được bài toán đầy thử thách trên. Bây giờ là cơ hội của bạn để áp dụng những gì bạn đã học được qua quá trình giải quyết của Oo. Đây là bài toán dành cho bạn: Hãy tìm giá trị in dự kiến của code của Oo. Quá dễ phải không ? À mà này, không có gợi ý gì đâu nhá, cho gợi ý hết thì mất vui rồi :(.

Input

• Dòng đầu chứa hai số nguyên dương \(n\), \(k\) \((n \le 10^5, k \le \min (5000, n))\) -- số \(n\) và \(k\) trong code của Oo.
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) \((a_i \le 10^9)\)

Output

• Biết rằng giá trị đó có thể viết dưới dạng \(P/Q\). In ra giá trị \(f = P \times Q^{-1} \mod (10^9+7)\)

Example

4 3
1 2 3 4 

500000036

2 2
2 3 

5

Trong máy tính, để tiết kiệm bộ nhớ, người ta thường tìm cách nén dữ liệu. Trong việc nén văn bản, ta sư dụng một phương pháp đơn giản đươc mô tả thông qua ví dụ sau:

Ví dụ:

Với xâu ký tự: "aaaabbb" sẽ được nén lại thành xâu "4a3b". Với xâu ký tự "aaab" sẽ được nén lại thành "3ab".

Cho một xâu \(S\) gồm các ký tự thuộc tập \('a'...'z'\). Gọt \(St\) là xâu nén của xâu \(S\) theo phương pháp được mô tả như trên. Xâu \(St\) gồm \(N\) ký tự thuộc tập các ký tự \('a'...'z'\), \('0',...'9'\)

Hãy giải nén xâu \(St\) để được xâu gốc \(S\).

Input

• Một xâu ký tự \(St\).

Output

• Một xâu ký tự \(S\) sau khi giải nén.
• Đề đảm bảo số lượng kí tự sau khi giải nén không quá \(10^{7}\).

Constraints

• \(1 \leq N \leq 10000\)

Example

2m2a3b4ezh 

mmaabbbeeeezh

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,..,a_N\) và số nguyên dương \(K\). Chọn ra \(K\) phần tử liên tiếp sao cho tổng của chúng là lớn nhất. In ra giá trị đó

Input

• Dòng 1: hai số nguyên dương \(N\) và \(K\) \((K \le N \le 10^5)\);
• Dòng 2: gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)

Output

• In ra đáp án thỏa mãn yêu cầu đề bài.

Example

6 2
2 4 5 2 9 1 

11

Cho hai số nguyên dương \(A\) và \(B\). Tìm chữ số tận cùng của \(A^B\).

Input

• Dòng thứ nhất chứa số nguyên dương \(A\).
• Dòng thứ hai chứa số nguyên dương \(B\).

Output

• In ra chữ số tận cùng của \(A^B\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(A, B \leq 10\);
• Subtask \(2\) (\(30\%\) số điểm): \(A, B \leq 10^6\);
• Subtask \(3\) (\(20\%\) số điểm): \(A, B \leq 10^9\);
• Subtask \(4\) (\(10\%\) số điểm): \(A, B \leq 10^{18}\);
• Subtask \(5\) (\(10\%\) số điểm): \(A, B \leq 10^{100000}\);

Example

2
4 

6

Năm Covid thứ nhất, Giáo sư Kẻ-là-ai-cũng-biết-là-ai-đấy - một KOL nổi tiếng trong làng VNOI đã buồn phải ở nhà không được đi chơi.

Tất nhiên để giải sầu, giáo sư sẽ post bài trên facebook. Giáo sư có rất nhiều chủ đề: thả thính, cách ly, đồ bảo hộ,… Tuy nhiên là người điều độ, một ngày giáo sư post đúng \(n\) bài.

Kế hoạch của giáo sư được định nghĩa là một tập hợp các số tự nhiên được sắp xếp, có thứ tự \((p_1, p_2, …, p_k)\), chứa ít nhất hai phần tử, thỏa mãn điều kiện: \(p_1 + p_2 + ... + p_k = n\). Kế hoạch này thể hiện giáo sư sẽ post \(p_1\) bài chủ đề \(1\), \(p_2\) bài chủ đề \(2\), … , \(p_k\) bài chủ đề \(k\).

Giáo sư sẽ liệt kê tất cả các kế hoạch của mình theo thứ tự từ điển.

Ví dụ: đối với nếu \(n = 4\), giáo sư có \(7\) kế hoạch, liệt kê trong bảng từ điển như sau:

\(\begin{matrix} &Số\ thứ\ tự &Kế\ hoạch\\ &1&1\ 1\ 1\ 1\\&2&1\ 1\ 2 \\&3&1\ 2\ 1\\&4&1\ 3\\&5&2\ 1\ 1\\&6&2\ 2\\&7&3\ 1\end{matrix}\)

Biết giá trị của số tự nhiên \(n\).

1. Với số \(k\) cho trước, giúp giáo sư xác định kế hoạch post bài có vị trí \(k\) trong bảng từ điển.
2. Với một kế hoạch nhất định, tính vị trí của nó trong bảng từ điển của giáo sư.

Input

• Dòng đầu tiên ghi số \(c\) (\(1\) hoặc \(2\)) là nhiệm vụ cần giải quyết.
• Dòng thứ hai ghi giá trị số \(n\).
• Dòng thứ ba, tùy thuộc vào giá trị của \(c\), ghi:
  • Nếu \(c = 1\), số tự nhiên \(k\),
  • Nếu \(c = 2\), các số tự nhiên cách nhau bởi một khoảng trắng là một kế hoạch của giáo sư.

Output

• In ra đáp án.

Constraints

• \(1 < n < 10.000\).
• \(0 < k < 10^{17}\) (dù \(c = 1\) hay \(c = 2\)).
• Đảm bảo có đáp án

Scoring

• Subtask \(1\) (\(18\%\) số điểm): \(n \le 20\)
• Subtask \(2\) (\(36\%\) số điểm): \(n <10 000\) và \(k \le 1 000 000\)
• Subtask \(3\) (\(18\%\) số điểm): \(k \le 2 000 000 000\)

Example

1
4
5 

2 1 1

2
21
1 2 3 4 5 6 

375776

Quay trở lại với Doraemon và đồng bọn, sau khi nghỉ ngơi thoải mái, cả bọn bắt đầu chuyến hành trình khám phá hòn đảo. Trong lúc đi tham quan, Suneo bỗng phát hiện được một phế tích bỏ hoang và thông báo cho cả bọn cùng khám phá nơi này vì có vẻ nó là nơi bắt đầu của cuộc hành trình tìm kiếm kho báu. Vừa bước chân vào phế tích, cửa ra liền đóng sầm lại làm cả bọn sợ hãi và trước mặt họ có vẻ là một câu đố. Một bức tranh có kích thước \(N×M\) hiện lên trước mặt họ, các ô bên trong bức tranh đều có màu trắng và viền của bức tranh có màu xám. Bên cạnh bức tranh có vài dòng chữ: “Ta sẽ vẽ vào bức tranh này dùng những con quái vật. Ta sẽ sắp xếp một số quái vật ở viền ngoài của bức tranh và hướng mặt về phía bảng. Việc sắp xếp các con quái vật có thể được biểu diễn bởi \(4\) chuỗi \(A, B, C, D\):

• Nếu \(A_i = 1\), có \(1\) con quái vật ở vị trí \((i, 0)\) \((1 \le i \le N)\).
• Nếu \(B_i = 1\), có \(1\) con quái vật ở vị trí \((i, M + 1)\) \((1 \le i \le N)\).
• Nếu \(C_i = 1\), có \(1\) con quái vật ở vị trí \((0, i)\) \((1 \le i \le M)\).
• Nếu \(D_i = 1\), có \(1\) con quái vật ở vị trí \((N + 1, i)\) \((1 \le i \le M)\).

2 quái vật bất kì sẽ tô 2 màu khác nhau, và màu của mỗi quái vật đều khác trắng và xám. Lần lượt thực hiện các thao tác sau đến khi tất cả quái vật để đã được chọn:

• Chọn \(1\) quái vật bất kì.
• Quái vật sẽ liên tục thực hiện thao tác sau nếu như ô trước mặt nó là \(1\) ô trắng: Đi sang ô trước mặt và tô màu ô đó với màu của nó. Nếu ô trước mặt nó có màu ko phải màu trắng thì quái vật sẽ dừng lại. May mắn cho các ngươi, lần này 2 chuỗi C và D đều không có quái vật.

Các ngươi hãy cho biết có bao nhiêu trạng thái khác nhau của bức tranh \((\)mod \(10^9 + 7)\). Hai trạng thái được coi là khác nhau nếu ở trạng thái này có ít nhất 1 ô khác màu với trạng thái kia."

Vì quá bất ngờ và sợ hãi, cả bọn chả biết phải làm gì để vượt qua thử thách này nên nhờ các bạn giúp họ vượt qua thử thách để cả bọn có thể bình tĩnh lại.

Input

• Dòng đầu tiên chứa hai số \(N, M\) \((1 \le N, M \le 10^5)\) là số hàng và số cột của bức tranh.
• \(4\) dòng tiếp theo, Mỗi dòng chứa \(1\) chuỗi lần lượt là \(A, B, C, D\).

Output

• Gồm 1 dòng chứa số nguyên là kết quả của bài toán.

Example

4 5
1110
1100
00000
00000 

4

![][1]

![][2]

![][3]

![][4]

![][5]

Nam là người thích chat với bạn bè trên Internet. Cậu ấy đã lập ra một phòng chat với điều kiện rằng trước khi vào phòng chat, mọi người phải chào hỏi trước.

Một câu chào được định nghĩa rằng, câu chào đó phải là một xâu kí tự, chỉ gồm các chữ cái, không chứa kí tự trắng, sao cho khi xóa đi một số chữ cái, nó sẽ trở thành một xâu từ khóa \(Key\) cho trước, tất nhiên là sẽ không được phép tráo đổi vị trí các chữ cái, mà chỉ được xóa bớt một số chữ cái.

Ví dụ: Với từ khóa là \(Key\) là xinchao khi Bình muốn vào phòng chat, Bình gõ choxiancaihao thì hệ thống sẽ xem xét xâu này và sẽ tự động loại bỏ các chữ cái để trở thành từ xinchao. Như vậy Bình được vào phòng chat.

Nhưng khi Bình gõ choxian, hệ thống không thể làm cách nào xóa bớt chữ cái để trở thành từ xinchao được. Như vậy, Bình không được vào phòng chat.

Yêu cầu: Cho từ khóa \(Key\) và \(N\) câu chào, hãy xác định xem câu chào nào được chấp nhận?

Input

• Dòng thứ nhất chứa số nguyên dương \(N\) (\(N≤100\))
• Dòng thứ hai chứa từ khóa \(Key\) (có độ dài \(≤10^4\))
• \(N\) dòng tiếp theo, mỗi dòng chứa xâu chữ cái mà Bình định gõ (có độ dài \(≤10^6\)).

Output

• Gồm \(N\) dòng, mỗi dòng tương ứng với câu chào, câu chào được đồng ý xuất YES, còn không, xuất NO.

Sample

4
hello
ahhellllloou
hlelo
helhcludoo
HelhcLudoo

YES
NO
YES
NO

Trong lúc Doraemon và những người bạn vẫn còn vui vẻ dưới ánh nắng tươi vàng trong một tiết trời hè nóng nực bên bãi biển tươi xanh thơm ngát mùi muối và những cánh chim trên cao bay dập dờn, dập dờn báo hiệu một mùa thu sắp đến và kết thúc một chuỗi ngày hè nóng nực nhưng cực kì đẹp đẽ và vui tươi thì ở phía bên kia xa xăm của hòn đảo tươi đẹp, dưới những tán cây dừa, một đàn khỉ nhí nhố gồm \(N\) chú đang háo hức xách cặp đến trường để đón lễ khai giảng nửa năm học mới 2019,5 - 2020.

Nhưng đâu phải chú nào cũng có tốc độ ngang nhau nên có chú đến sớm và có chú đến muộn và không có chú nào đến cùng thời điểm. Biết rằng khi chú thứ \(i\) đến thì có \(A_i\) chú khỉ khác có mặt trong lớp (tính cả chú thứ \(i\)). Hiệu trưởng kiêm giáo viên chủ nhiệm đã nhờ bác bảo vệ xây dựng lại thứ tự đến trường của các chú khỉ để có biện pháp xử lí thích đáng với những chú khỉ đi trễ.

Input

• Dòng đầu tiên chứa một số \(N\) là sĩ số của lớp \((1 \leq N \le 10^6)\)
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa một số duy nhất \(A_i\) \((1\leq A_i \leq N)\).

Output

• Một dòng duy nhất gồm \(N\) số, số thứ \(i\) là thứ tự đến trường của các chú khỉ \(i\).

Example

6
5 4 2 1 6 3 

4 3 6 2 1 5

Một đôi thỏ (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con (cũng gồm một thỏ đực và thỏ cái); một đôi thỏ con, khi tròn 2 tháng tuổi, sau mỗi tháng đẻ ra một đôi thỏ con, và quá trình sinh nở cứ thế tiếp diễn. Hỏi sau \(n\) tháng có bao nhiêu đôi thỏ, nếu đầu năm (tháng Giêng) có một đôi thỏ sơ sinh

Trong hình vẽ trên, ta quy ước:

• Cặp thỏ nâu là cặp thỏ có độ tuổi \(1\) tháng.
• Cặp thỏ được đánh dấu (màu đỏ và màu xanh) là cặp thỏ có khả năng sinh sản.

Nhìn vào hình vẽ trên ta nhận thấy:

• Tháng Giêng và tháng Hai: Chỉ có \(1\) đôi thỏ.
• Tháng Ba: đôi thỏ này sẽ đẻ ra một đôi thỏ con, do đó trong tháng này có \(2\) đôi thỏ.
• Tháng Tư: chỉ có đôi thỏ ban đầu sinh con nên đến thời điểm này có \(3\) đôi thỏ.
• Tháng Năm: có hai đôi thỏ (đôi thỏ đầu và đôi thỏ được sinh ra ở tháng Ba) cùng sinh con nên ở tháng này có \(2 + 3 = 5\) đôi thỏ.
• Tháng Sáu: có ba đôi thỏ (\(2\) đôi thỏ đầu và đôi thỏ được sinh ra ở tháng Tư) cùng sinh con ở thời điểm này nên đến đây có \(3 + 5 = 8\) đôi thỏ.

Khái quát, nếu \(n\) là số tự nhiên khác \(0\), gọi \(f(n)\) là số đôi thỏ có ở tháng thứ \(n\), ta có:

• Với \(n=1\) ta được \(f(1)=1\).
• Với \(n=2\) ta được \(f(2)=1\).
• Với \(n=3\) ta được \(f(3)=2\).
• Do đó với \(n>2\) ta được: \(f(n)=f(n−1)+f(n−2)\).

Nguồn: wikipedia

Dãy số trên gọi là dãy số \(Fibonacci\) và được định nghĩa như sau:

• \(F_1=F_2=1;\)
• \(\dots\)
• \(F_n=F_{n−2}+F_{n−1}\)

Hãy viết chương trình tính các số \(Fibonacci\) thứ \(a[i]\).

Input

• Gồm \(T\) dòng (\(T \le 10^6\)), dòng thứ \(i\) chứa số \(a[i]\) (\(a[i] \le 1000\)).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) chứa số \(F_{a[i]}\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(T = 5\) và \(a[i] \le 75\).
• Subtask \(2\) (\(25\%\) số điểm): \(a[i] \le 75\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

1
2
7
24
31
1 

1
1
13
46368
1346269
1

XYZ là trung tâm luyện thi đại học lâu đời ở tỉnh Phú Thọ, nơi đây đã sản sinh ra vô số thủ khoa của cả nước. Thành công của trung tâm đến từ bí quyết “Đánh giá năng lực 4.0”. Trung tâm vận hành cách đánh giá dựa trên một siêu máy tính. Giả sử đối tượng học tập còn \(X\) ngày là đến kỳ thi đại học và đối tượng muốn ôn thi \(N\) môn, siêu máy tính sẽ tính được rằng nếu đối tượng học ở trung tâm trong \(j\) ngày để ôn thi môn thứ \(i\) thì sẽ đạt \(A_{i,j}\) điểm. Tất nhiên là càng học nhiều thì điểm sẽ cao lên nên \(A_{i,j} \leq A_{i, j + k} (k \geq 0)\). Dựa vào đánh giá trên trung tâm sẽ tìm ra phương pháp học tập tốt nhất cho đối tượng.

Hôm nay do có một chút trục trặc nên siêu máy tính không thể hoạt động được nữa , bạn hãy viết chương trình giúp trung tâm nhé!!

Input

• Dòng đầu tiên chứa 2 số nguyên dương \(N\) và \(X\).
• \(N\) dòng tiếp theo, mỗi dòng ghi \(X\) số, số thứ \(j\) là \(A_{i,j}\) (\(A_{i,j} \leq 10^6\)) là số điểm đạt được của môn thứ \(i\) nếu học trong \(j\) ngày.

Output

• Hãy in ra một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N,X \leq 4\)
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 100, X=1\)
• Subtask \(3\) (\(40\%\) số điểm): \(N,X \leq 100\)

Example

3 3
4 8 9
0 5 6
3 6 7

11

Nhập vào từ bàn phím một xâu kí tự \(S\). Hãy viết ra một kí tự có số lần xuất hiện nhiều nhất trong xâu \(S\) (có phân biệt kí tự hoa và kí tự thường).

Lưu ý: Nếu có nhiều kí tự có cùng số lần xuất hiện nhiều nhất trong xâu \(S\) thì in ra kí tự xếp theo thứ tự từ điển nhỏ nhất trong xâu đó.

Input

• Dòng đầu tiên và duy nhất chứa 1 xâu \(S\) (chỉ gồm các chữ cái trong tập \(\{a,\dots,z, A,\dots,Z\}\)) \((|S| \leq 10^6)\)

Output

• In ra kí tự xuất hiện nhiều nhất trong xâu \(S\).

Example

abcdaadDedgdAAA 

d

Viết chương trình nhập vào 1 số nguyên \(n\), in ra màn hình số lượng số nguyên dương nhỏ hơn hoặc bằng \(\frac{n-1}{2}\).

Input

• Gồm 1 số nguyên \(n\) \((1 \leq n \leq 10 ^ 9)\).

Output

• Một dòng duy nhất chứa số lượng số nguyên dương nhỏ hơn hoặc bằng \(\frac{n-1}{2}\).

Example

9 

4

Conan đang trong một vụ án cực kì hóc búa, đã có đến 2 vụ án mạng xảy ra. Tại hiện trường 2 vụ án đều để lại dòng chữ kì lạ. Có vẻ như đó chính là gợi ý mà hung thủ để lại. Hung thủ dường như đang cố thách thức vị thám tử lừng danh của chúng ta. Bằng tài năng suy luận tài tình của mình, Conan đã khám phá đã ra được gợi ý của hung thủ chính là sự tương đồng của 2 dòng chữ đó. Tuy nhiên các dòng chữ rất dài, Conan giỏi suy luận nhưng lại không giỏi lập trình. Bạn là một lập trình viên giỏi, bạn hãy giúp Conan nhé.

Yêu cầu: Cho 2 chuỗi kí tự \(a\) và \(b\). Hãy xác định xem chuỗi \(a\) và \(b\) giống nhau bao nhiêu kí tự?

Input

• Dòng thứ nhất là chuỗi kí tự \(a (1 \leq |a| \leq 10^{5})\).
• Dòng thứ hai là chuỗi kí tự \(b\) \((1 \leq |b| \leq 10^{5})\).
• Các chuỗi chỉ gồm các kí tự từ \(\texttt{a}\) \(\rightarrow\) \(\texttt{z}\), \(|x|\) là số lượng ký tự của chuỗi \(x\).

Output

• Gồm một dòng duy nhất là số lượng kí tự giống nhau.

Example

aaabb
baa

3

Cho xâu \(S\) có độ dài \(2 \times N-1\) và một lưới ô vuông \(A\) có kích thước \(N \times N\), mỗi ô trên lưới ghi một chữ cái. Một người tìm cách di chuyển bắt đầu từ ô ở góc trên trái đến ô ở góc dưới phải, mỗi lần di chuyển chỉ được quyền sang ô có chung cạnh ở bên phải hoặc phía dưới sao cho các chữ cái trong các ô trên đường di chuyển tạo thành xâu \(S\).

Yêu cầu: Cho trước lưới ô vuông \(A\) và xâu \(S\), hãy xác định số cách di chuyển thỏa mãn yêu cầu đặt ra.

Input

• Dòng đầu tiên ghi số \(N\) (\(2\le N \le 1000\));
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) chữ cái Latin in thường (thể hiện lưới chữ cái);
• Dòng cuối ghi xâu \(S\) gồm \(2 \times N-1\) chữ cái Latin in thường.

Output

• Một dòng ghi số nguyên là số cách di chuyển thỏa điều kiện Modulo cho \(10^6+3\).

Example

3
aaa
aba
baa
aabaa

5