Sau khi giải xong câu hỏi đó thì bất ngờ chiếc máy enigma đã dịch chuyển hai người abcnickname và Cpascal sang một mê cung khổng lồ với rất nhiều đường đi trước mặt họ là một bức tường gồm các ký tự như là (L , R) và một mảnh giấy trên tay abcnickname cũng là các ký tự đó nhưng ngắn hơn. Sau khi đọc qua và phân tích thì Cpascal đã biết được nguyên lý hoạt động của chúng bằng cách truy tìm các ký tự trên mảnh giấy đó và bức tường, tìm vị trí hợp lý, đánh dấu nếu là số chẵn thì là L còn lẻ thì R nhưng vì ký tự quá dài và thuật toán khá lâu và phức tạp vì vậy cần các bạn lập trình để có thể tạo ra được code tối ưu nhất, nhanh nhất để abcnickname và Cpascal có thể tiếp tục đi trước khi quá muộn và gặp những răc rối không mong muốn!

Yêu cầu: xuất ra số thứ tự cần rẽ đề abcnickname và Cpascal có thể di chuyển vào khu vực an toàn

Dữ liệu vào

• Đầu tiên là một xâu ~x~ là xâu ở trên tường với độ dài không quá 1000000 ký tự
• Thứ hai là một xâu ~y~ là xâu ở trong mảnh giấy đó dùng để so sánh xem chúng khớp một phần xâu ~x~ ở chỗ nào với độ dài không vượt quá ~x~ ký tự
• Và dữ liệu luôn luôn có đầu ra hợp lý không có trường hợp đặc biệt

Dữ liệu ra

• Tìm hiểu cách làm tối ưu của bài trên

Ví dụ

Input: 01

LLRRLRLRLLRRRLLRR
LLRR

Output: 01

L L R 

Input: 02

LLRRLRRRLRLLRLRLRLRLRLRRLLRRRLLRLLRLRLRLRLRRLRLRLR
LR

Output: 02

R L L R R R R R R R L R R R R R L L L