Cho một số nguyên dương \(n\), một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\) và hai số nguyên \(k\) và \(x\).
Hãy chèn một phần tử có giá trị bằng \(x\) vào sau vị trí thứ \(k\) trong dãy \(a\).

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{6}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{9}\)).
• Dòng thứ ba gồm hai số nguyên \(k\) và \(x\) (\(1 \le k \le n\); \(|x| \le 10^{9}\)).

Output

• In ra các phần tử của dãy \(a\) trên một dòng sau khi chèn phần tử \(x\) vào sau vị trí \(k\). Các số cách nhau ít nhất một khoảng trắng.

Examples

4
1 7 5 10
2 3

1 7 3 5 10

Cho một số nguyên dương \(n\), một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\) và một số nguyên dương \(k\).
Hãy xoá phần tử ở vị trí thứ \(k\) trong dãy \(a\).

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{6}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{9}\)).
• Dòng thứ ba gồm số nguyên dương \(k\) (\(1 \le k \le n\)).

Output

• In ra các phần tử của dãy \(a\) trên một dòng sau khi xoá phần tử ở vị trí \(k\). Các số cách nhau ít nhất một khoảng trắng.

Examples

4
1 7 5 10
2

1 5 10

Cho một số nguyên dương \(n\) và một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\).
Hãy in ra dãy \(a\) sau khi loại bỏ tất cả các phần tử âm.

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{5}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{9}\)).

Output

• In ra các phần từ của dãy \(a\) sau khi loại bỏ các phần tử âm. Các số cần đảm bảo thứ tự như ban đầu và cách nhau ít nhất một khoảng trắng.

Examples

6
4 -1 2 0 0 -5

4 2 0 0

Cho một số nguyên dương \(n\), một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) và một số nguyên \(k\).
Hãy xoá tất cả các phần tử có giá trị bằng \(k\) trong dãy \(a\).

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{5}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{9}\)).
• Dòng thứ ba gồm số nguyên \(k\) (\(|k| \le 10^{9}\)).

Output

• In ra các phần từ của dãy \(a\) sau khi loại bỏ các phần tử bằng \(k\). Các số cần đảm bảo thứ tự như ban đầu và cách nhau ít nhất một khoảng trắng.

Examples

4
1 7 1 10
1

7 10

Cho một số nguyên dương \(n\) và một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\).
Hãy dịch chuyển vị trí của các phần tử trong dãy sang phải đúng \(1\) đơn vị. Cụ thể, phần từ \(a_1\) cũ sẽ trở thành phần từ \(a_2\) mới, phần từ \(a_2\) cũ sẽ trở thành phần tử \(a_3\) mới,\(\ldots\) Phần tử cuối cùng sẽ được đưa lên đầu dãy.

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{6}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{6}\)).

Output

• In ra các phần tử của dãy \(a\) lần lượt trên một dòng sau khi dịch chuyển vị trí theo yêu cầu đề bài. Các số cách nhau ít nhất một khoảng trắng.

Examples

9
-8 -7 0 7 -2 2 10 -7 5

5 -8 -7 0 7 -2 2 10 -7

10
4 -7 6 -7 6 9 -8 -3 10 6

6 4 -7 6 -7 6 9 -8 -3 10

Trong đợt nghỉ hè này, TDZ được giao nhiệm vụ thống kê và báo cáo nhiệt độ của các ngày trong một tuần. Việc thống kê thì đã quá dễ dàng vì TDZ có thể Google và hàng chục triệu kết quả sẽ hiện ra trước mắt. Nhưng còn việc viết báo cáo, vì TDZ mải chơi và lười nghĩ nên TDZ quyết định nhờ các bạn đọc thực hiện công việc hộ TDZ.

Một bản báo cáo nhiệt độ cần có các thông tin sau:

• Nhiệt độ của các ngày lạnh hơn 10°C.
• Nhiệt độ của ngày lạnh nhất và nóng nhất.

Vậy đó, mặc dù biết cổ xuý cho việc lười biếng là không tốt, các bạn giúp TDZ lần này nhé 🙂

Input

• Gồm bảy số thực lần lượt là nhiệt độ của các ngày trong tuần.

Output

• Dòng thứ nhất in ra nhiệt độ của các ngày lạnh hơn 10°C. Nếu có nhiều ngày thoả mãn thì in theo thứ tự ngày trong tuần.
• Dòng thứ hai in ra nhiệt độ của ngày lạnh nhất.
• Dòng thứ ba in ra nhiệt độ của ngày nóng nhất.

Sample Test

12.8 15.3 20.1 15.9 9.0 8.9 12.6 

9.0 8.9
8.9
20.1

Cho một số nguyên dương \(n\) và một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\).
Hãy tính các khoảng cách giữa hai số liên tiếp. Cụ thể, hãy tính tất cả \(|a_i - a_{i - 1}|\) với \(2 \leq i \leq n\).

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{6}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{6}\)).

Output

• In ra lần lượt \(n - 1\) khoảng cách giữa hai số liên tiếp trên một dòng. Các số cách nhau ít nhất một khoảng trắng.

Examples

5
1 3 5 2 7

2 2 3 5

10
5 -7 3 10 -4 -2 9 -4 1 -7

12 10 7 14 2 11 13 5 8

Một dãy tăng dần là dãy mà mọi phần tử (trừ phần tử đầu tiên) luôn lớn hơn phần tử đứng đằng trước nó.

Cho một số nguyên dương \(n\) và một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\). Hãy kiểm tra xem dãy \(a\) có phải là dãy tăng dần hay không.

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{6}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{9}\)).

Output

• In ra YES nếu dãy \(a\) là dãy tăng dần, ngược lại in ra NO.

Examples

7
9 16 16 0 17 15 -9

NO

5
9 10 11 15 19

YES

Cho một số nguyên dương \(n\) và một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\). Hãy tìm tổng lớn nhất của hai phần tử liên tiếp trong dãy \(a\).

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{3}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{9}\)).

Output

• In ra tổng lớn nhất của hai phần tử liên tiếp trong dãy \(a\).

Examples

7
9 16 16 0 17 15 -9

32

5
9 10 11 -15 19

21

Cho một số nguyên dương \(n\) và một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\). Hãy tìm phần tử lớn nhất và liệt kê tất cả vị trí các phần tử bằng với phần tử lớn nhất đó trong dãy \(a\).

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{3}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{9}\)).

Output

• Dòng thứ nhất in ra giá trị của phần tử lớn nhất trong dãy \(a\).
• Dòng thứ hai in ra các vị trí của các phần tử bằng phần tử lớn nhất trong dãy \(a\) theo thứ tự tăng dần. Các số cách nhau ít nhất một khoảng trắng.

Examples

7
9 17 16 0 17 15 -9

17
2 5

5
9 10 11 -15 19

19
5

Cho một số nguyên dương \(n\) và một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\). Hãy tìm phần tử bé nhất và liệt kê tất cả vị trí các phần tử bằng với phần tử bé nhất đó trong dãy \(a\).

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 10^{3}\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) (\(|a_i| \le 10^{9}\)).

Output

• Dòng thứ nhất in ra giá trị của phần tử bé nhất trong dãy \(a\).
• Dòng thứ hai in ra các vị trí của các phần tử bằng phần tử bé nhất trong dãy \(a\) theo thứ tự tăng dần. Các số cách nhau ít nhất một khoảng trắng.

Examples

7
9 17 16 0 17 15 -9

-9
7

5
9 -15 11 -15 19

-15
2 4

Cho một mảng số nguyên \(A\) có \(N\) phần tử, mảng này đã được sắp xếp tăng dần. Hãy tìm vị trí của hai phần tử khác nhau bất kỳ sao cho tổng của chúng có giá trị là \(X\). Nếu trong dãy \(A\) không tồn tại hai phần tử khác nhau có tổng là \(X\) thì in ra "No solution".

Input

• Dòng đầu chứa 2 số nguyên \(N\) và \(X\).
• Dòng tiếp theo chứa \(N\) số nguyên \(A_i\).

Output

• Hai vị trí \(i\) và \(j\) khác nhau sao cho tổng ở hai vị trí này có giá là \(X\). In vị trí phần tử nhỏ hơn trước phần tử lớn hơn.
• Nếu không tồn tại in ra "No solution".

Constants

• \(2 \leq N \leq 10^6\) và \(0 \leq A_i, X \leq 10^9\)

Example

6 16
2 3 5 7 9 12

4 5

Hiện nay, xem ý nghĩa biển số xe, số điện thoại, ngày sinh hay một dãy số nào đó là điều quan tâm của nhiều người. Cách đánh giá số đẹp của dãy số như sau: Tính tổng các chữ số trong dãy, nếu tổng là số có \(1\) chữ thì đó là giá trị số đẹp (độ đẹp của dãy số), ngược lại thì tiếp tục tính tổng các chữ số trong dãy.

Ví dụ:

• Dãy số ngày sinh \(02022020\) có tổng các chữ số là \(8\), vậy độ đẹp của dãy số là \(8\).
• Dãy số điện thoại \(0912345678\) có tổng các chữ số là \(45\), tính tục tính tổng ta được tổng là \(9\), vậy độ đẹp của dãy số là \(9\).

Yêu cầu: Cho dãy số có \(n\) chữ số. Hãy đánh giá độ đẹp của dãy số đã cho.

Input

• Chứa dãy số có \(n\) chữ số (\(n \leq 18\))

Output

• Một số nguyên là độ đẹp của dãy số.

Example

02022020

8

0912345678

9