Trong một thành phố thông minh, hệ thống cảm biến giao thông gửi dữ liệu liên tục về trung tâm xử lí, mỗi tín hiệu cảm biến là một số nguyên dương. Tuy nhiên, do lỗi kĩ thuật, có những chuỗi tín hiệu bị trùng lặp ba lần liên tiếp gây nhiễu loạn quá trình phân tích. Đội kĩ thuật cần làm sạch tín hiệu theo quy tắc đặc biệt để đảm bảo dữ liệu đầu vào là tối ưu nhất.

Chuỗi tín hiệu ban đầu là một dãy số nguyên có ~n~ số. Hệ thống sẽ lọc nhiễu tín hiệu theo quy trình như sau:

• Bước 1. Từ trái sang phải, nếu phát hiện ~3~ tín hiệu liên tiếp giống nhau, hệ thống xóa bộ ba này khỏi dãy và đánh lại chỉ số từ đầu, rồi chuyển sang bước 2.
• Bước 2. Từ phải sang trái, nếu phát hiện ~3~ tín hiệu liên tiếp giống nhau, hệ thống xóa bộ ba này khỏi dãy và đánh lại chỉ số từ đầu, rồi chuyển về bước 1.

Quy trình này lặp lại cho đến khi không còn bộ ba nào giống nhau liên tiếp.

Yêu cầu

Viết chương trình mô phỏng quy trình lọc nhiễu tín hiệu và ghi ra kết quả.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên dương ~n~ ~(3 \le n \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~A_i~ ~(1 \le A_i \le 10^4)~.

Dữ liệu đầu ra

Gồm một dòng chứa dãy số nguyên dương ~A~ sau khi xóa.

Ví dụ

Ví dụ 1

INPUT

14
1 1 3 3 3 1 1 2 1 1 2 2 2 1

OUTPUT

1 2

Để trao đổi thông tin giữa các trung tâm an ninh mạng trên địa bàn thành phố Đà Nẵng, người ta thực hiện công tác mã hóa dữ liệu trước khi gửi đi.

Dữ liệu là xâu kí tự ~X~ gồm các chữ cái in thường từ a đến z, độ dài xâu ~X~ không quá ~10^6~. Lần lượt thực hiện mã hóa:

• Ban đầu xâu ~Y~ rỗng.
• Đưa một kí tự xâu ~X~ vào cuối xâu ~Y~ và đảo ngược xâu ~Y~.
• Các kí tự của xâu ~X~ đưa lần lượt vào xâu ~Y~ như vậy.

Yêu cầu

In ra xâu ~Y~ cuối cùng nhận được khi đã đưa hết kí tự của ~X~ vào.

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa xâu ~X~.

Dữ liệu đầu ra

Gồm một dòng duy nhất chứa xâu ~Y~ tìm được.

Ràng buộc dữ liệu

• 55% số test có độ dài xâu ~X~ không quá ~255~.
• 20% số test có độ dài xâu ~X~ không quá ~10^4~.
• 25% số test có độ dài xâu ~X~ không quá ~10^6~.

Ví dụ

Ví dụ 1

INPUT

agh

OUTPUT

hag

Giải thích:

• Bước 1: đưa a và đảo ngược ~Y~ được ~Y =~ a;
• Bước 2: đưa g và đảo ngược ~Y~ được ~Y =~ ga;
• Bước 3: đưa h và đảo ngược ~Y~ được ~Y =~ hag.

Trong chuyến tham gia lắp đặt trạm tín hiệu vệ tinh cho dự án thành phố thông minh của thành phố Đà Nẵng, An là một thành viên của Câu lạc bộ Sáng tạo trẻ thành phố, nhận thấy độ chênh lệch nhiệt độ tại khu vực đỉnh Bà Nà vào các thời điểm sáng, trưa, tối là rất lớn.

Trong nghiên cứu gần đây của mình, An đã phát triển một hệ thống điện mới dựa trên sự biến đổi kép của nhiệt độ. Khi hệ thống được cung cấp ~3~ mức nhiệt độ khác nhau theo thứ tự lần lượt là ~x~, ~y~ và ~z~ thì sẽ tạo ra ~Q~ đơn vị điện năng theo công thức ~Q = xy - y^2 - xz + yz~.

Yêu cầu

Cho dãy số nguyên ~a_1, a_2, \ldots, a_n~ là nhiệt độ tại ~n~ thời điểm theo thứ tự thời gian trong một ngày. Hãy tìm ~3~ thời điểm ~i~, ~j~, ~k~ ~(1 \le i < j < k \le n)~ để thu ~3~ mức nhiệt ~x = a_i~, ~y = a_j~ và ~z = a_k~ sao cho năng lượng điện tạo ra là lớn nhất.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên ~n~ ~(3 \le n \le 10^6)~.
• Dòng thứ hai chứa dãy gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(|a_i| \le 10^6)~.

Dữ liệu đầu ra

Gồm một số nguyên là năng lượng điện lớn nhất tạo được.

Ràng buộc dữ liệu

• 40% số test có ~n \le 100~.
• 30% số test có ~n \le 10^4~.
• 30% số test không giới hạn gì thêm.

Ví dụ

Ví dụ 1

INPUT

7
-5 12 4 20 5 9 3

OUTPUT

144

Hoàng Anh thích thiết kế máy tính có cấu hình mạnh cho các bạn học AI. Sau nhiều lần tìm hiểu, nghiên cứu, Hoàng Anh đã thiết kế ra một loại máy tính thích hợp. Tuy nhiên, để sản phẩm đến được với những người bạn học AI phải có mức giá phải chăng và chất lượng tốt. Hoàng Anh quyết định sử dụng các thiết bị chính của nhà cung cấp phù hợp.

Bốn bộ phận chính là: chip, màn hình cảm ứng, bo mạch và vỏ máy. Mỗi bộ phận có ~n~ nhà cung cấp, và mỗi bộ phận của một nhà cung cấp có một điểm đánh giá của các khách hàng là ~V_i~ và có giá thành là ~C_i~.

Yêu cầu

Chọn ra ~4~ nhà cung cấp cho ~4~ bộ phận chính của chiếc máy tính mà tổng điểm đánh giá là lớn nhất và giá thành không quá ~M~.

Dữ liệu đầu vào

Gồm năm dòng:

• Dòng thứ nhất chứa hai số nguyên ~n~ ~(2 \le n \le 10^3)~ và ~M~ ~(2 \le M \le 10^9)~.
• Dòng thứ ~k~ tiếp theo ~(k~ từ ~1~ đến ~4)~ chứa ~n~ cặp số nguyên dương ~(C_{k_1}, V_{k_1}), (C_{k_2}, V_{k_2}), \ldots, (C_{k_n}, V_{k_n})~ ~(1 \le V_{k_i}, C_{k_i} \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là tổng điểm đánh giá lớn nhất của máy tính mà tổng giá thành không quá ~M~.

Ràng buộc dữ liệu

• 50% số test có ~n \le 10^2~.
• 50% số test còn lại có ~n \le 10^3~.

Ví dụ

Ví dụ 1

INPUT

2 10
2 2 3 3
2 2 4 5
2 2 5 8
2 2 6 8

OUTPUT

11