minict part 1

Tanya đang học phép trừ và muốn giảm một số nguyên đi 1 đơn vị. Tuy nhiên Tanya vẫn chưa hiểu bài nên làm sai. Tanya dùng thuật toán sau:

• Nếu chữ số cuối cùng không phải số 0, Tanya trừ nó đi 1.
• Nếu chữ số cuối cùng là số 0, Tanya chia nó cho 10 (xóa chữ số cuối cùng).

Bạn được cho một số nguyên n. Tanya muốn thực hiện phép "trừ 1" k lần. Nhiệm vụ của bạn là hãy cho biết kết quả theo cách tính của Tanya.

Đề bài đảm bảo kết quả là một số nguyên dương.

Input

• Gồm hai số nguyên n và k (\(2 \le n \le 10^9, 1 \le k \le 50\))

Output

• Một số nguyên là kết quả.

Example

512 4

50

Allen có rất nhiều tiền. Anh ấy có n dollars trong ngân hàng. Vì lý do bảo mật, anh ấy muốn rút hết tiền ra. Các mệnh giá của tờ dollar bao gồm: \(1, 5, 10, 20, 100\). Hỏi số lượng tối thiểu tờ tiền mà Allen có thể nhận được là bao nhiêu?

Input

• Gồm hai số nguyên n (\(2 \le n \le 10^{18}\))

Output

• Một số nguyên là kết quả.

Example

125

3

43

5

Gọi phép dịch trái của một string \(t_1t_2t_3...t_{n-1}t_n\) là string \(t_2t_3...t_{n-1}t_nt_1\)

Gọi phép dịch phải của một string \(t_1t_2t_3...t_{n-1}t_n\) là string \(t_nt_1t_2t_3...t_{n-1}\)

Ví dụ: s = "4579" dịch trái là "5794", dịch phải là "9457"

Một string được gọi là good nếu phép dịch trái và phép dịch phải của nó bằng nhau.

Bạn được cho một string s chỉ bao gồm các kí tự từ 0 đến 9.

Hãy tính toán số lượng kí tự ít nhất cần xóa để làm cho string s trở thành good.

Input

• Dòng đầu tiên là số nguyên \(T (T \le 10)\) - là số lượng bộ dữ liệu.
• Mỗi bộ dữ liệu gồm một string \(s\) (\(s.size() \le 2*10^5\)).

Output

• Mỗi bộ dữ liệu in ra một số nguyên là số lượng ít nhất kí tự cần xóa để làm cho string s trở thành good.

Example

3
95831
100120013
252525252525

3
5
0

Cho số nguyên \(n\), hãy phân tích \(n\) thành tổng của \(k\) số nguyên tố sao cho \(k\) lớn nhất có thể.

Input

• Dòng đầu tiên là số nguyên \(n (2 \leq n \leq 10^5)\).

Output

• Dòng đầu in ra một số nguyên là \(k\).
• Dòng thứ hai in ra \(k\) số nguyên có tổng bằng \(n\) theo thứ tự tăng dần.

Example

5 

2
2 3

Cho một binary string (xâu nhị phân) \(s\) chỉ bao gồm các kí tự \('0'\) và \('1'\).

Một phép biến đổi được định nghĩa như sau:

• Chọn một kí tự trong \(string\) \(s\) và đảo kí tự đó, tức là \('0'\) đảo thành \('1'\), còn \('1'\) đảo thành \('0'\).

Một string được gọi là \(good\) nếu như nó không chứa bất kì đoạn con (không cần liên tục) nào bằng \("010"\) hoặc \("101"\). Ví dụ, \(s="1001"\) chứa \("101"\) là đoạn con nên \("1001"\) \(không\) \(phải\) là \(good\) \(string\), trong khi \(s="1000"\) là \(good\) \(string\).

Một đoạn con không liên tục của một string s là một string thu được bằng cách xóa đi một số kí tự (có thể không xóa) của \(s\).

Yêu cầu : Hãy cho biết số lần biến đổi tối thiểu để làm cho \(string\) \(s\) trở thành \(good\) \(string\).

Input

• Dòng đầu in ra một số nguyên là \(T (1 \leq T \leq 100)\) - số lượng bộ test.
• \(T\) dòng tiếp theo mỗi dòng chứa một binary \(string\) \(s\) \((1 \leq s.size() \leq 1000)\).

Output

• Mỗi bộ test in trên một dòng là một số nguyên - số lần biến đổi tối thiểu để làm cho string s trở thành good.

Example

3
001
110
01011001 

0
0
3

Cho một binary string (xâu nhị phân) \(s\) chỉ bao gồm các kí tự \('0'\) và \('1'\).

Một đoạn con \([L, R]\) của \(string\) \(s\) là một \(string\) \(s_Ls_{L+1} \cdots s_{R−1}s_R\) và nó có độ dài là \(R−L+1\).

Một đoạn con được gọi là cân bằng nếu như trong đoạn con có số lượng kí tự \('0'\) bằng số lượng kí tự \('1'\).

Yêu cầu: Hãy cho biết độ dài lớn nhất của đoạn con cân bằng có trong \(string\) \(s\).

Input

• Dòng đầu tiên là số nguyên \(n (n \leq 10^5)\).
• Dòng thứ hai là string \(s\).

Output

• Gồm một số nguyên là độ dài của đoạn con cân bằng lớn nhất.

Example

9
010010100 

6

Vương quốc Linear có đúng một tuyến tàu điện. Tuyến này có \(n\) điểm dừng. Tại điểm dừng thứ \(i\) có \(a_i\) hành khách xuống tàu, và có \(b_i\) hành khách lên tàu. Ban đầu (trước điểm dừng đầu tiên) xe điện không có hành khách. Ngoài ra, khi đến điểm dừng cuối cùng, tất cả hành khách có trên tàu sẽ xuống tàu.

Yêu cầu: Nhiệm vụ của bạn là tính toán sức chứa tối thiểu của tàu điện, sao cho số người bên trong tàu tại bất kì thời điểm nào đều không vượt quá sức chứa này. Lưu ý rằng tại mỗi điểm dừng, các hành khách xuống tàu trước, sau đó các hành khách khác mới được lên tàu.

Input

• Dòng đầu tiên là số nguyên \(n\) - số điểm dừng của tuyến tàu điện.
• Trong \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i\) và \(b_i\). Số lượng khách xuống tàu không lớn hơn số lượng khách hiện có trên tàu. Số khách trên tàu sau điểm dừng thứ \(n\) luôn đảm bảo bằng \(0\).

Output

• Gồm một số nguyên là sức chứa tối thiểu của tàu điện.

Constraints

• \(2\leq n\leq 1000\)
• \(0\leq a_i ,b_i\leq 1000\)

Example

4
0 60
56 79
54 77
106 0 

106

Cho một xâu \(s\) và bạn có thể thay đổi một kí tự trong xâu \(s\) thành một kí tự khác.

Hãy tính toán số lượng tối thiểu các kí tự cần thay đổi trong xâu \(s\), sao cho xâu \(s\) chứa ít nhất \(k\) kí tự khác nhau.

Input

• Dòng đầu tiên là xâu \(s\) chỉ chứa các kí tự latin thường.
• Dòng thứ hai chứa số nguyên \(k\).

Output

• Gồm một số nguyên là số kí tự tối thiểu cần thay đổi, nếu như không thể thực hiện được thì in ra impossible.

Constraints

• \(1\leq |s|\leq 1000\) (\(|s|\) là độ dài của xâu \(s\))
• \(1\leq k\leq 26\)

Example

justys
6 

1

Pi có \(n\) số nguyên \(a_1, a_2, ..., a_n\) có trong túi xách và Pi có \(k\) người bạn. Pi muốn phân phát tất cả số nguyên trong túi cho những người bạn, sao cho người bạn thứ \(i\) nhận được chính xác \(w_i\) số nguyên và mỗi số nguyên chỉ được phân phát cho chính xác một người bạn.

Độ hạnh phúc của một người bạn là tổng của số nguyên lớn nhất và số nguyên nhỏ nhất mà người này nhận được.

Pi muốn làm cho những người bạn của anh ấy hạnh phúc nhất có thể. Gọi \(s\) là tổng của các độ hạnh phúc của các người bạn sau khi được phân phát các số nguyên. Pi muốn \(s\) lớn nhất có thể. Hãy tìm số \(s\).

Input

• Dòng đầu tiên là hai số nguyên \(n\) và \(k\).
• Dòng thứ hai chứa n số nguyên \(a_1a_2...a_n\).
• Dòng thứ ba chứa k số nguyên \(w_1w_2...w_k\).

Output

• In ra số nguyên \(s\).

Constraints

• \(1\leq n\leq 2*10^5, 1\leq k\leq n\)
• \(-10^9\leq a_i\leq 10^9\)
• \(1\leq w_i\leq n\)
• \(w_1+w_2+...+w_k = n\)

Example

1 1
-4 
1 

-8

4 2
10 10 11 11
2 2 

42

Bảo mới lên lớp 3 tại trường tiểu học ABC. Bảo đang học phép toán cộng.

Cô giáo viết lên bảng một biểu thức gồm nhiều phép toán cộng. Để làm cho việc tính toán dễ dàng, biểu thức này chỉ chứa các số hạng 1, 2 và 3. Tuy nhiên, như vậy vẫn quá khó với Bảo. Bảo chỉ mới biết đếm, nên Bảo chỉ có thể tính biểu thức nếu các số hạng của biểu thức được viết theo thứ tự tăng dần. Ví dụ, Bảo không thể tính \(1+3+2+1\) nhưng có thể tính \(1 + 1 + 2 + 3\).

Bạn biết được biểu thức được viết trên bảng. Hãy sắp xếp các số hạng theo thứ tự không giảm để cho Bảo dễ dàng tính toán.

Input

• Gồm một dòng duy nhất là một string \(s\) (\(|s| \leq 100\)) - biểu thức được viết trên bảng theo quy tắc trên, string s chỉ gồm các kí tự 1, 1, 3 và +.

Output

• Biểu thức sau khi được sắp xếp.

Example

3+2+2+1

1+2+2+3