Cho một chuỗi kí tự \(S\) có \(n\) kí tự \((n≤100)\). Hãy đếm số kí tự khoảng trắng trong chuỗi đó.

Input

• Gồm một dòng duy nhất là chuỗi kĩ tự \(S\).

Output

• In ra số lượng kí tự khoảng trắng của \(S\).

Example

kid  1   4   1  2 

10

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

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Đếm số cặp chỉ số \((i,j)\) thỏa mãn:

• \(1 \le i \le j \le n\);
• \(a_i + a_j^2=K\) với \(K\) cho trước.

Input

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

Output

• In ra số cặp \((i,j)\) thỏa mãn.

Example

3 5
1 2 2 

2

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

Bạn có \(2\) mảng số nguyên không âm được sắp xếp theo thứ tự không giảm \(a\) gồm \(n\) phần tử và \(b\) gồm \(m\) phần tử.

Hãy ghép \(a\) và \(b\) thành một mảng số nguyên \(c\) gồm \(n + m\) phần tử.

Hãy cho biết mảng \(c\) theo thứ tự không giảm.

Constants

• \(1 \leq n, m \leq 10^5\)
• \(0 \leq a_i, b_i \leq 10^9\)

Example

6 7
1 6 9 13 18 18
2 3 8 13 15 21 25

1 2 3 6 8 9 13 13 15 18 18 21 25

(dịch đại khái)

Cho \(N\) \((1 \leq N \leq 20)\) chú bò với độ cao \(a_1, a_2, \dots, a_N\). Trang trại có \(N\) chuồng với giới hạn độ cao \(b_1, b_2, \dots, b_N\) (tức, nếu \(b_5=17\), thì chỉ có chú bò cao không quá 17 đơn vị mới được ở chuồng 5).

Có bao nhiêu cách xếp bỏ vào các chuồng sao cho mỗi chú bò ở một chuồng khác nhau, và chú bò nào cũng ở trong chuồng mà không vượt giới hạn độ cao của chuồng đó?

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq 10^9)\)
• Dòng thứ ba chứa \(N\) số nguyên \(b_1, b_2, \dots, b_n\) \((1 \leq b_i \leq 10^9)\)

Định dạng đầu ra

• Số lượng cách thỏa mãn đề. Đáp án không vượt quá kiểu dữ liệu số nguyên 64-bit (long long trong C++)

Điểm số

• Test 1-5 thỏa mãn \(N \leq 8\).
• Test 6-12 không có giới hạn nào khác.

Ví dụ

4
1 2 3 4
2 4 3 4

8