Cho một xâu \(s\) độ dài \(n\). Các ký tự từ trái sang phải được đánh số từ \(1\) tới \(n\).

Với mỗi \(i\) từ \(1\) tới \(n\), ta thực hiện thao tác sau: Đẩy các ký tự trong tiền tố độ dài \(i\) của \(s\) sang phải \(1\) đơn vị theo vòng tròn.

Điều đó có nghĩa là từ xâu \(s_1 s_2 s_3 \dots s_i\) sẽ biến thành \(s_2 s_3 s_4 \dots s_i s_1\)

Hãy cho biết kết quả của xâu \(s\) sau \(n\) thao tác.

Input

• Gồm 1 dòng duy nhất chứa xâu \(s\).

Output

• Gồm 1 dòng duy nhất chứa xâu kết quả.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 300\)
• Subtask \(2\) (\(28\%\) số điểm): \(n \le 3000\)
• Subtask \(3\) (\(52\%\) số điểm): \(n \le 300000\)

Example

dxmhloventha

vhednltmhoax