Bình luận

• 
  

  0

  Thanh72    10:11 p.m. 18 Tháng 8, 2023 ← chỉnh sửa 3 →

  Xét những phép biến đổi xâu sau:

  1. Thêm kí tự # vào phía sau xâu (Xem kí tự # có thứ tự từ điển nhỏ hơn tất cả các kí tự khác trong xâu).
  2. Tạo một tập gồm toàn bộ các hoán vị vòng quanh của xâu đó. (VD: Cho xâu \(S\) = abc thì tập các hoán vị vòng quanh của xâu \(S\) là {abc, bca, cab}).
  3. Sắp xếp các xâu trong tập tuân theo thứ tự từ điển.
  4. Tạo một xâu mới từ những kí tự cuối cùng của các xâu trong tập theo thứ tự.

  Ví dụ, ta biến xâu babc thành babc#. Sau đó, ta có tập các hoán vị vòng quanh của xâu theo thứ tự từ điển là: {#babc, abc#b, babc#, bc#ba, and c#bab}. Rồi ta tạo ra xâu mới cb#ab.

  Yêu cầu: Từ xâu đã qua biến đổi, hãy xây dựng lại và in ra xâu ban đầu.

  Input

  • Gồm một dòng chứa một xâu đã qua những phép biến đổi trên với độ dài \(n+1(1 \leq n \leq 10^6)\). Mọi chữ cái trong xâu là chữ cái latin thường.

  Output

  • Gồm một dòng chứa một xâu độ dài \(n\) là xâu ban đầu.

  Test 1

  Input

  cb#ab

  Output

  babc