Nhập 1 số nguyên dương ~N~. Nhập tiếp ~N~ số nguyên. Ghi ra màn hình dãy số vừa nhập. Ghi ra màn hình dãy số vừa nhập theo thứ tự ngược lại.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~).
• Dòng tiếp theo chứa ~N~ số nguyên ~x~ (~|x| \leq 10^9~).

Output

• Dòng đầu tiên chứa dãy số vừa nhập.
• Dòng tiếp theo chứa dãy số vừa nhập theo thứ tự ngược lại.

Sample Test

Input:

4
1 3 4 2

Output:

1 3 4 2
2 4 3 1

Cho ~n~ số nguyên dương ~a_{1}, a_{2}, a_{3}, ..., a_{n}~ và một số nguyên dương ~v~. Hãy xác định vị trí xuất hiện số ~v~ đầu tiên trong dãy ~a~.

Input

• Dòng thứ nhất chứa số ~n~ và ~v~ (~1 \leq n, v \leq 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_{1}, a_{2}, a_{3}, ..., a_{n}~ (~1 \leq a_i \leq 10^5~).

Output

• In ra NO nếu số ~v~ không tồn tại trong dãy ~a~, ngược lại dòng đầu tiên in ra YES và dòng thứ hai in ra vị trí đầu tiên xuất hiện số ~v~.

Sample Test 1

Input:

5 2
8 2 2 10 2

Output:

YES
2

Sample Test 2

Input:

5 3
8 2 2 10 2

Output:

NO

Cho ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~. Hãy in ra các số chẵn và các số lẻ trên các dòng khác nhau.

Input

• Dòng đầu chứa số nguyên dương ~N~ (~N \leq 10^3~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~ (~a_i \leq 10^3~).

Output

• Dòng đầu tiên in ra các số chẵn.
• Dòng thứ hai in ra các số lẻ.
• Các số cách nhau một dấu cách, theo trình tự từ trái sang phải như trong input.

Sample Test

Input

5
1 2 4 3 5

Output

2 4
1 3 5

Cho ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~ và một số ~x~. Đếm xem có bao nhiêu số lớn hơn ~x~.

Input

• Dòng đầu chứa số nguyên dương ~N~ (~N \leq 10^3~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~ (~a_i \leq 10^3~).
• Dòng thứ ba chứa một số nguyên dương ~x~ (~x \leq 10^3~).

Output

• In ra số lượng số lớn hơn ~x~.

Sample Test

Input

5
1 2 4 3 5
3

Output

2

Note

• Có hai số lớn hơn ~3~ là ~4~ và ~5~.

Nhập 1 số nguyên dương ~N~, sau đó nhập tiếp 1 dãy gồm ~N~ số nguyên. Nhập 1 số nguyên dương ~K~. Xóa số ở vị trí thứ ~K~ trong dãy vừa nhập. In ra dãy đó.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~).
• Dòng tiếp theo chứa ~N~ số nguyên ~x~ (~|x| \leq 10^9~).
• Dòng cuối chứa số nguyên dương ~K~ (~1 \leq K \leq N~).

Output

In ra dãy mới.

Sample Test

Input:

4
1 7 5 10
2

Output:

1 5 10

Nhập 1 số nguyên dương ~N~, sau đó nhập tiếp 1 dãy gồm ~N~ số nguyên. Nhập 1 số nguyên dương ~K~. Xóa tất cả các phần tử có giá trị bằng ~K~. In ra dãy đó.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~).
• Dòng tiếp theo chứa ~N~ số nguyên ~x~ (~|x| \leq 10^9~).
• Dòng cuối chứa số nguyên dương ~K~ (~|K| \leq 10^9~).

Output

In ra dãy mới.

Sample Test

Input:

4
1 7 1 10
1

Output:

7 10

Nhập 1 số nguyên dương ~N~, sau đó nhập tiếp 1 dãy gồm ~N~ số nguyên đánh số từ ~1~. Nhập 2 số nguyên dương ~V~ và ~K~. Thêm số ~V~ vào vị trí ~K~ trong dãy. In ra dãy đó.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~).
• Dòng tiếp theo chứa ~N~ số nguyên ~x~ (~|x| \leq 10^9~).
• Dòng cuối chứa 2 số nguyên dương ~V~ và ~K~ (~|V| \leq 10^9, 1 \leq K \leq N~).

Output

In ra dãy mới.

Sample Test

Input:

4
1 7 3 10
5 2

Output:

1 5 7 3 10

Cho ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~ và hai số ~l, r~. Tính tổng các số từ ~a_l~ đến ~a_r~.

Input

• Dòng đầu chứa số nguyên dương ~N~ (~N \leq 10^3~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~ (~a_i \leq 10^3~).
• Dòng thú ba chứa hai số nguyên dương ~l~, ~r~. (~1 \leq l \leq r \leq n~).

Output

• In ra tổng các số từ ~a_l~ đến ~a_r~.

Sample Test

Input

5
1 2 4 3 5
2 4

Output

9

Note

• ~a_2 + a_3 + a_4 = 2 + 4 + 3 = 9~.

Cho 2 dãy ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~ và ~b_1, b_2, b_3,..., b_N~. Tìm tổng ~a_i + b_i~ lớn nhất.

Input

• Dòng đầu chứa số nguyên dương ~N~ (~N \leq 10^3~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~ (~a_i \leq 10^3~).
• Dòng thứ ba chứa ~N~ số nguyên dương ~b_1, b_2, b_3, ..., b_N~ (~b_i \leq 10^3~).

Output

• In ra tổng ~a_i + b_i~ lớn nhất.

Sample Test

Input

5
1 2 4 3 5
3 4 1 3 2

Output

7

Cho ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~ và một số thực ~x~. Hãy tìm số có giá trị gần với ~x~ nhất trong ~N~ số đã cho.

Input

• Dòng đầu chứa số nguyên dương ~N~ (~N \leq 10^3~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, a_3, ..., a_N~ (~a_i \leq 10^3~).
• Dòng thú ba chứa một số thực ~x~. (~0 \leq x \leq 10^3~).

Output

• In ra số có giá trị gần với ~x~ nhất. Nếu có nhiều vị trí ~i~ thoả mãn, in ra giá trị của ~a_i~ với ~i~ bé nhất.

Sample Test 1

Input

5
1 2 4 3 5
3.6

Output

4

Sample Test 2

Input

4
1 2 4 2
2.9

Output

2

Nhập 1 số nguyên dương ~N~, sau đó nhập tiếp 1 dãy gồm ~N~ số nguyên. Tìm trung bình cộng của dãy số và tìm giá trị của phần tử gần với trung bình cộng nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~).
• Dòng tiếp theo chứa ~N~ số nguyên ~x~ (~|x| \leq 10^9~).

Output

• Dòng đầu tiên ghi ra trung bình cộng của dãy số (làm tròn đến chữ số thập phân thứ 3).
• Dòng tiếp theo ghi ra giá trị của phần tử gần với trung bình cộng nhất. Nếu có nhiều giá trị thoả mãn, in ra giá trị ở vị trí bé nhất.

Sample Test

Input:

3
3 5 10

Output:

6.000
5

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

Input:

12.8 15.3 20.1 15.9 9.0 8.9 12.6 

Output:

9.0 8.9
8.9
20.1

Nhập 1 số nguyên dương ~N~, sau đó nhập tiếp 1 dãy gồm ~N~ số nguyên. Tìm số lớn nhất, bé nhất và vị trí xuất hiện đầu tiên của nó.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~).
• Dòng tiếp theo chứa ~N~ số nguyên ~x~ (~|x| \leq 10^9~).

Output

• Dòng đầu tiên ghi ra số lớn nhất và vị trí đầu tiên tìm được.
• Dòng tiếp theo ghi ra số bé nhất và vị trí đầu tiên tìm được.

Sample Test

Input:

4
3 1 4 2

Output:

4 3
1 2

Nhập 1 số nguyên dương ~N~, sau đó nhập tiếp 1 dãy gồm ~N~ số nguyên. Kiểm tra xem dãy vừa nhập có đối xứng hay không. Có thì ghi YES, ngược lại ghi NO.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~).
• Dòng tiếp theo chứa ~N~ số nguyên ~x~ (~|x| \leq 10^9~).

Output

Nếu dãy đối xứng thì in ra YES, ngược lại in ra NO.

Sample Test

Input:

5
1 6 2 6 1

Output:

YES

Nhập 1 số nguyên dương ~N~, sau đó nhập tiếp 1 dãy gồm ~N~ số nguyên. Tìm cặp đôi liên tiếp có khoảng cách lớn nhất. Ghi ra khoảng cách lớn nhất đó.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~2 \leq N \leq 10^6~).
• Dòng tiếp theo chứa ~N~ số nguyên ~x~ (~|x| \leq 10^9~).

Output

In ra khoảng cách lớn nhất.

Sample Test

Input:

4
1 3 5 10

Output:

5

Nhập 1 số nguyên dương ~N~, sau đó nhập tiếp 1 dãy gồm ~N~ số nguyên. In ra số lượng phần tử của dãy con không giảm liên tiếp có nhiều phần tử nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~).
• Dòng tiếp theo chứa ~N~ số nguyên ~x~ (~|x| \leq 10^9~).

Output

In ra số lượng phẩn tử của dãy con không giảm liên tiếp có nhiều phần tử nhất.

Sample Test

Input:

8
2 1 3 5 2 4 6 8

Output:

4

Cho số nguyên dương ~n~, hãy tìm số Tribonacci thứ ~n~.

Số Tribonacci thứ ~i~ được định nghĩa như sau: ~ \begin{equation} f_i = \begin{cases} 0 & \text{nếu $i < 3$}\\ 1 & \text{nếu $i = 3$}\\ f_{i - 1} + f_{i - 2} + f_{i - 3} & \text{nếu $i > 3$} \end{cases} \end{equation} ~

Input

Gồm một số nguyên dương ~n~ duy nhất (~n \leq 40~).

Output

In ra số Tribonacci thứ ~n~.

Sample Test 1

Input:

4

Output:

1

Sample Test 2

Input:

10

Output:

44

TDZ đang học về ước chung lớn nhất (~UCLN~). Nhưng khi nghe đến thứ gọi là "ước nguyên tố" thì TDZ đang rất mơ hồ vì cậu không nắm vững kiến thức về số nguyên tố. Vì vậy, TDZ nhờ bạn giải giúp bài tập này để thông não ra một tí:

Cho ~n~ số nguyên dương, hãy:

• Đếm số lượng số nguyên tố trong ~n~ số này.
• Tìm ~UCLN~ của ~n~ số này.

Input

• Dòng thứ nhất gồm một số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên dương có giá trị không vượt quá ~10^5~.

Output

• Dòng thứ nhất in ra số lượng số nguyên tố trong ~n~ số.
• Dòng thứ hai in ra ~UCLN~ của ~n~ số.

Subtasks

• Subtask ~1~ (~50\%~): Tất cả các số trong input nhỏ hơn ~10^3~.
• Subtask ~2~ (~50\%~): Không thay đổi.

Sample Test 1

Input:

5
3 6 2 9 5

Output:

3 
1

Note:

• Có ~3~ số nguyên tố là ~3, 2, 5~.
• ~UCLN(3, 6, 2, 9, 5) = 1~

Sample Test 2

Input:

4
4 8 10 6

Output:

0
2

Cho một dãy ~A~ gồm ~n~ số nguyên ~a_{1}, a_{2}, a_{3}, ..., a_{n}~. Hãy tìm đoạn con đan dấu dài nhất của dãy ~A~.

Note:

• Một đoạn con đan dấu của dãy ~A~ là một đoạn liên tiếp ~a_{l}, a_{l + 1}, a_{l + 2}, ..., a_{r}~ ~(l \leq r)~ sao cho ~\forall i: l \leq i < r~, ~a_{i}~ khác dấu ~a_{i + 1}~.
• Số ~0~ không khác dấu với các số khác.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên ~a_{1}, a_{2}, a_{3}, ..., a_{n}~ (~|a_{i}| \leq 10^5~).

Output

• Dòng thứ nhất in ra độ dài đoạn con đan dấu dài nhất của dãy ~A~.
• Dòng tiếp theo in ra các số trong đoạn con đan dấu dài nhất, mỗi số cách nhau một khoảng trắng. Nếu có nhiều đoạn thoả mãn hãy in ra đoạn xuất hiện đầu tiên trong dãy.

Sample Test 1

Input:

5
-3 6 -2 9 5

Output:

4
-3 6 -2 9

Sample Test 2

Input:

6
1 -3 6 2 -9 5

Output:

3
1 -3 6

Note: Có hai đoạn đan dấu là ~[1, -3, 6]~ và ~[2, -9, 5]~, ta chỉ lấy đoạn xuất hiện đầu tiên.

Cho một số nguyên dương ~n~. Hãy phân tích số ~n~ thành tổng của các số Fibonacci khác nhau.

Input

Gồm một số nguyên dương ~n~ duy nhất (~n \leq 10^9~).

Output

In ra các số Fibonacci trên một dòng, theo thứ tự bất kì và cách nhau một khoảng trắng, sao cho tổng các số đó bằng ~n~. Nếu có nhiều cách phân tích thoả mãn thì in ra cách nào cũng được.

Sample Test 1

Input:

5

Output:

2 3

Note: Có thể phân tích ~5~ thành chính số ~5~ hoặc ~2 + 3~.

Sample Test 2

Input:

16

Output:

5 3 8

Note: Có nhiều cách phân tích thoả mãn, ví dụ như ~16 = 13 + 3~ và ~16 = 8 + 5 + 2 + 1~.

Cho số nguyên dương ~n~, hãy in ra ~n~ dòng đầu tiên của tam giác Pascal.

Input

Gồm một số nguyên dương ~n~ duy nhất (~n \leq 60~).

Output

Với mỗi dòng của tam giác Pascal, in ra các số lần lượt cách nhau một khoảng trắng.

Sample Test

Input:

5

Output:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1