Đề bài

Václav có một vườn hoa xinh đẹp gồm \(M\) bông hoa được trồng trên cùng một đường thẳng. Anh cũng đặt \(N\) vòi phun nước trên đường thẳng này để tưới hoa.

Vị trí các vòi phun lần lượt là \(s_1,\ldots,s_N\). Vị trí các bông hoa lần lượt là \(f_1,\ldots,f_M\). Cả hai dãy đều được cho theo thứ tự không giảm:

• \(s_1\le s_2\le\ldots\le s_N\).
• \(f_1\le f_2\le\ldots\le f_M\).

Václav sắp lên đường tham dự CEOI. Anh muốn bảo đảm tất cả hoa được tưới đầy đủ trong thời gian mình vắng mặt. Để làm việc này, anh xoay riêng từng vòi phun sang trái hoặc sang phải và đặt công suất phun. Vì mọi vòi phun dùng chung một ống nước, chúng đều phun xa một khoảng như nhau.

Nếu công suất phun là \(K\) và vòi phun thứ \(i\) quay sang trái, nó sẽ tưới mọi bông hoa có vị trí trong đoạn từ \(s_i-K\) đến \(s_i\), kể cả hai đầu mút. Tương tự, nếu vòi phun thứ \(j\) quay sang phải, nó sẽ tưới mọi bông hoa có vị trí trong đoạn từ \(s_j\) đến \(s_j+K\), kể cả hai đầu mút. Một vòi phun có thể tưới nhiều bông hoa và một bông hoa có thể được nhiều vòi phun tưới.

Hãy xác định liệu có thể tưới tất cả các bông hoa hay không. Nếu có, hãy tìm công suất phun nhỏ nhất đủ dùng cùng với một cách xoay các vòi phun tương ứng. Nếu có nhiều cấu hình hợp lệ với công suất nhỏ nhất, bạn có thể in ra bất kỳ cấu hình nào.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.

Dòng thứ hai chứa \(N\) số nguyên \(s_1,\ldots,s_N\), cách nhau bởi dấu cách, là vị trí các vòi phun.

Dòng thứ ba chứa \(M\) số nguyên \(f_1,\ldots,f_M\), cách nhau bởi dấu cách, là vị trí các bông hoa.

Dữ liệu ra

Nếu không thể tưới tất cả các bông hoa, in số \(-1\).

Nếu có thể, in hai dòng. Dòng đầu tiên chứa số \(K\), là công suất phun nhỏ nhất cần thiết để tưới tất cả các bông hoa. Dòng thứ hai chứa xâu \(c\) độ dài \(N\), trong đó \(c_i\) là L nếu vòi phun thứ \(i\) cần quay sang trái và là R nếu vòi phun đó cần quay sang phải.

Giới hạn

• \(1\le N,M\le 10^5\).
• \(0\le s_i\le 10^9\) với mọi \(1\le i\le N\).
• \(0\le f_i\le 10^9\) với mọi \(1\le i\le M\).
• \(s_i\le s_j\) với mọi \(i\le j\).
• \(f_i\le f_j\) với mọi \(i\le j\).

Chấm điểm

• Subtask 1 (3 điểm): \(N=1\).
• Subtask 2 (6 điểm): \(N=3x\) với một số nguyên \(x\) nào đó, và \(s_{3i+1}=s_{3i+2}=s_{3i+3}\) với mọi \(0\le i\le x-1\); nói cách khác, các vòi phun luôn được đặt theo từng nhóm ba chiếc.
• Subtask 3 (17 điểm): \(N\le 10\) và \(M\le 1\,000\).
• Subtask 4 (27 điểm): \(K\le 8\); nghĩa là trong mọi bộ kiểm thử đều tồn tại một cách xoay các vòi phun sao cho công suất không quá \(8\) là đủ để tưới tất cả hoa.
• Subtask 5 (47 điểm): Không có ràng buộc bổ sung.

Ví dụ

3 3
10 10 10
5 11 16

6
LLR

1 2
1000
1 2000

-1