contest 27/05/26

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

Cho dãy \(a\), số nguyên \(n\) phần tử, đếm số số xuất hiện trong dãy đó.

Input

• Dòng đầu gồm số nguyên n (\(1 \leq n \leq 200000\))
• Dòng thứ 2 gồm n số nguyên (\(-10^9 \leq a_{i} \leq 10^{9}\))

Output

• Kết quả.

Example

5
1 3 2 3 2

3

Khôi vừa viết một ứng dụng hẹn hò mang tên Fake love. Ứng dụng đang có \(n\) bạn nữ, \(m\) bạn nam đang sử dụng, biết rằng 2 người nam nữ sẽ chỉ thấy hợp nhau nếu độ chênh lệch cân nặng của họ không vượt quá \(k\). Qua một số thuật toán, ứng dụng của của Khôi sẽ xếp các nam nữ hợp nhau thành các couple. Vì muốn biết ứng dụng của mình đã tối tưu chưa, nên Khôi hỏi bạn có nhiều nhất bao nhiêu couple có thể có (1 nam chỉ có ghép thể với 1 bạn nữ, ngược lại cũng vậy).

Input

• \(n, m, k(1 \leq n, m\leq 2*10^5, 0 \leq k \leq 10^9)\).
• \(n\) số nguyên, \(1 \leq a_i\leq10^9\) cân nặng của các bạn nữ.
• \(m\) số nguyên, \(1 \leq b_i\leq10^9\) cân nặng của các bạn nam.

Output

• số couple.

Example

4 3 5
60 45 80 60
30 60 75 

2

Gần đến tết Tân Sửu 2021, \(n\) bạn học sinh lớp A5 khóa 16-19 đang họp lớp và quyết định rằng Chủ nhật tuần này sẽ đi chơi công viên Châu Phi.

Ở trò chơi "Tàu lượn siêu tốc", mỗi hàng của tàu sẽ chứa tối đa hai chỗ ngồi, và tổng cân nặng hai chỗ ngồi này có giá trị không quá \(x\).

Vậy khi đến chơi tàu lượn siêu tốc, tàu lượn trên phải có ít nhất bao nhiêu hàng ngồi để tất cả các bạn A5 có thể lên chơi 1 lúc.

Input

• \(n, x(1 \leq n\leq 2*10^5, 1 \leq x \leq 10^9)\).
• \(n\) số nguyên, \(1 \leq a_i \leq x\) cân nặng của bạn thứ i .

Output

• số hàng ngồi

Example

4 10
7 2 3 9 

3

Cho "tổ ong" có quy luật như sau:

Dễ thấy với mỗi tập các ô có giá trị \(n\) sẽ tạo thành một hình lục giác đều bậc \(n\).

Và hình lục giác thứ \(n+1\) sẽ bao quanh hình lục giác thứ \(n\).

Bạn được cho giá trị \(n\), Hãy tính số ô có giá trị nhỏ hơn hoặc bằng \(n\)

Input

• Số nguyên \(n (0 \leq n \leq 10^9)\)

Output

• Số ô có giá trị nhỏ hơn bằng \(n\).

Example

2 

19