USACO 2023 - Tháng 1 - Hạng Bạc

Bessie đang sử dụng phần mềm chỉnh sửa văn bản mới nhất và tuyệt vời nhất, miV! Cô ấy bắt đầu với một chuỗi đầu vào chỉ bao gồm các chữ cái tiếng Anh viết hoa và viết thường, và cô ấy muốn biến nó thành một chuỗi đầu ra mong muốn. Với chỉ một lần nhấn phím, miV cho phép cô ấy thay thế tất cả các lần xuất hiện của một chữ cái tiếng Anh \(c_1\) trong chuỗi bằng một chữ cái tiếng Anh khác \(c_2\). Ví dụ, với chuỗi \(\texttt{aAbBaaAbBa}\), nếu Bessie chọn \(c_1\) là a và \(c_2\) là B, chuỗi ban đầu sẽ biến thành \(\texttt{BAbBBBAbBB}\).

Bessie là một con bò bận rộn, vì vậy đối với mỗi trường hợp kiểm tra độc lập \(T\) (\(1≤T≤10\)), hãy in ra số lần nhấn phím tối thiểu cần thiết để biến chuỗi đầu vào của cô ấy thành chuỗi đầu ra mong muốn.

Input

• Dòng đầu tiên chứa số nguyên \(T\), số lượng trường hợp kiểm tra độc lập.
• Tiếp theo là \(T\) cặp dòng, mỗi cặp chứa một chuỗi đầu vào và một chuỗi đầu ra có độ dài bằng nhau. Tất cả các ký tự là chữ cái tiếng Anh viết hoa hoặc viết thường (A đến Z hoặc a đến z). Tổng độ dài của tất cả các chuỗi không vượt quá \(10^5\).

Output

• Đối với mỗi trường hợp kiểm tra, hãy in ra số lần nhấn phím tối thiểu để biến chuỗi đầu vào thành chuỗi đầu ra, hoặc -1 nếu không thể thực hiện.

Scoring

• Subtask 1: Các chuỗi có độ dài không quá 50.
• Subtask 2: Tất cả các chuỗi chỉ bao gồm các chữ cái viết thường từ a đến e.
• Subtask 3: Không có ràng buộc thêm.

Example

4
abc
abc
BBC
ABC
abc
bbc
ABCD
BACD

0
-1
1
3

Nông dân John có một trang trại lưới ô vuông kích thước \((N + 1) \times (N + 1)\) (\(1 \le N \le 1500\)). Ô \((i, j)\) đại diện cho ô ở hàng \(i\) từ trên xuống và cột \(j\) từ trái sang. Có một con bò sống ở mỗi ô \((i, j)\) với \(1 \le i, j \le N\), mỗi ô như vậy cũng chứa một biển hiệu hướng sang phải hoặc xuống dưới. Mỗi ô \((i, j)\) thỏa mãn \(i = N + 1\) hoặc \(j = N + 1\), ngoại trừ \((N + 1, N + 1)\), chứa một bể thức ăn cho bò. Mỗi bể chứa thức ăn có giá khác nhau, bể ở ô \((i, j)\) có giá \(c_{i, j}\) (\(1 \le c_{i, j} \le 500\)) để cho một con bò ăn.

Mỗi ngày vào giờ ăn tối, nông dân John rung chuông ăn tối, và mỗi con bò sẽ đi theo biển hiệu cho đến khi chúng đi đến một bể thức ăn, và ăn thức ăn ở bể đó. Sau đó, các con bò quay trở về chỗ ban đầu vào ngày tiếp theo.

Để quản lý chi phí, nông dân John muốn biết tổng chi phí để cho tất cả bò ăn mỗi ngày. Tuy nhiên, vào mỗi ngày, trước trời tối, con bò ở một ô \((i, j)\) nào đó lật ngược hướng của biển hiệu của nó (sang phải thành xuống dưới và ngược lại). Biển hiệu sẽ hướng về hướng này cho những ngày tiếp theo, trừ khi nó được lật lại một lần nữa.

Bạn được cho tọa độ của biển hiệu bị lật trong mỗi ngày, in ra chi phí cho mỗi ngày (tổng có \(Q\) ngày, \(1 \le Q \le 1500\)).

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 1500\)).
• \(N + 1\) dòng tiếp theo chứa các hàng của lưới từ trên xuống dưới, chứa hướng ban đầu của các biển hiệu và chi phí \(c_{i, j}\) của mỗi bể. \(N\) dòng đầu tiên chứa một xâu \(N\) chứa hướng R hoặc D (biểu diễn chỉ hướng sang phải hoặc xuống dưới), theo sau đó là chi phí \(c_{i, N + 1}\). Dòng thứ \(N + 1\) chứa \(N\) chi phí \(c_{N + 1, j}\).
• Dòng tiếp theo chứa \(Q\) (\(1 \le Q \le 1500\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i\) và \(j\) (\(1 \le i, j \le N\)), tọa độ của ô mà biển hiệu bị lật trong ngày tương ứng.

Output

• \(Q + 1\) dòng, chi phí ban đầu và theo sau là chi phi sau mỗi lần lật biển.

Scoring

• Subtask 1: \(1 \le N, Q, \le 50\)
• Subtask 2: \(1 \le N, Q \le 250\)
• Subtask 3: Các hướng ban đầu của các biển hiệu được sinh ngẫu nhiên.
• Subtask 4: Không có ràng buộc gì thêm

Example

2
RR 1
DD 10
100 500
4
1 1
1 1
1 1
2 1

602
701
602
701
1501

Nông dân Nhoj đã bỏ Bessie giữa chốn hoang vu! Tại thời điểm \(t=0\), Bessie ở vị trí \(x=0\) trên một trục số vô hạn. Cô ấy cuống cuồng tìm lối ra bằng cách di chuyển sang trái hoặc phải 1 đơn vị mỗi giây. Tuy nhiên, thực tế là không có lối ra và sau \(T\) giây, Bessie quay trở lại vị trí \(x=0\), mệt mỏi và cam chịu.

Nông dân Nhoj cố gắng theo dõi Bessie nhưng chỉ biết được số lần Bessie đi qua các vị trí \(x=.5, 1.5, 2.5, \ldots, (N-1).5\), được biểu diễn bởi mảng \(A_0, A_1, \dots, A_{N-1}\) (\(1 \leq N \leq 10^5\), \(1 \leq A_i \leq 10^6\), \(\sum A_i \leq 10^6\)). Bessie không bao giờ đi xa hơn \(x>N\) hoặc ít hơn \(x<0\).

Lộ trình của Bessie có thể được biểu diễn bằng một chuỗi gồm \(T = \sum_{i=0}^{N-1} A_i\) ký tự \(L\) và \(R\), trong đó ký tự thứ \(i\) biểu thị hướng mà Bessie di chuyển trong giây thứ \(i\). Số lần thay đổi hướng được định nghĩa là số lần xuất hiện của các chuỗi \(LR\) và \(RL\).

Hãy giúp nông dân Nhoj tìm bất kỳ lộ trình nào mà Bessie có thể đã thực hiện, phù hợp với mảng \(A\) và giảm thiểu số lần thay đổi hướng. Đảm bảo rằng luôn có ít nhất một lộ trình hợp lệ.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa các số nguyên \(A_0, A_1, \dots, A_{N-1}\).

Output

• Xuất ra một chuỗi \(S\) có độ dài \(T = \sum_{i=0}^{N-1} A_i\) với các ký tự \(S_i\) là \(L\) hoặc \(R\), biểu thị hướng Bessie di chuyển trong giây thứ \(i\). Nếu có nhiều lộ trình thỏa mãn, hãy in ra bất kỳ lộ trình nào.

Scoring

• Subtask 1: \(N \leq 2\).
• Subtask 2: \(T = A_0 + A_1 + \dots + A_{N-1} \leq 5000\).
• Subtask 3: Không có ràng buộc bổ sung.

Example

2
2 4

RRLRLL

3
2 4 4

RRRLLRRLLL

RRLRRLRLLL
RRRLRLLRLL
RRRLLRRLLL