시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 352 42 28 14.433%

문제

문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

  1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
  2. 알파벳 소문자로 이루어진 문자열 S가 주어진다.
  3. 문자열 S에서 문자열 W를 모두 제거하는 사람이 승리한다.

병서는 문자열 W를 모두 제거하기 위해 프로그램을 만들려고 한다.

병서가 구상한 프로그램은 아래의 명령 중 주어진 명령을 수행하는 작업을 N번 반복한다.

  • L : 문자열 S의 왼쪽에서부터 처음으로 등장하는 문자열 W를 찾아, S에서 해당 부분문자열을 제거한다.
  • R : 문자열 S의 오른쪽에서부터 처음으로 등장하는 문자열 W를 찾아, S에서 해당 부분문자열을 제거한다.

명령을 수행할 때, 제거해야 하는 문자열 W가 없다면 명령을 실패하고, 아무 일도 일어나지 않는다.

병서를 위해 N개의 명령에 따라 문자열 S에서 문자열 W를 제거하는 프로그램을 제작해주자! 

입력

첫 번째 줄과 두 번째 줄에 길이가 1 이상인 문자열 W와 문자열 S가 각각 주어진다. W와 S는 알파벳 소문자로 이루어져 있다.

W는 최대 10자, S는 최대 300,000자이다.

세 번째 줄에 명령의 개수 N이 주어진다. (1 ≤ N ≤ 30,000)

네 번째 줄부터 N개의 줄에 명령이 주어진다.

출력

첫 번째 줄에 성공한 명령의 개수를, 두 번째 줄에 프로그램을 실행한 후의 문자열 S를 출력한다.

프로그램 실행 후에 문자열이 비어있는 경우는 존재하지 않는다.

세 번째 줄에 프로그램을 실행한 후의 문자열 S에 문자열 W가 남아있으면 You Lose!를, 문자열 W를 모두 제거했으면 Perfect!를 출력한다.

예제 입력 1

zoac
aliczoacethrozoacughthelookingzoacglaszoacs
4
L
R
L
L

예제 출력 1

4
alicethroughthelookingglass
Perfect!

aliczoacethrozoacughthelookingzoacglaszoacs → L → alicethrozoacughthelookingzoacglaszoacs

alicethrozoacughthelookingzoacglaszoacs → R → alicethrozoacughthelookingzoacglass

alicethrozoacughthelookingzoacglass → L → alicethroughthelookingzoacglass

alicethroughthelookingzoacglass → L → alicethroughthelookingglass

위의 4번의 명령으로 문자열 S에서 문자열 W를 모두 제거했으므로 Perfect!를 출력한다.

예제 입력 2

poke
superaquatpoppokeokpokeekeornado
6
L
L
L
R
R
R

예제 출력 2

4
superaquatornado
Perfect!

superaquatpoppokeokpokeekeornado → L → superaquatpopokpokeekeornado

superaquatpopokpokeekeornado → L → superaquatpopokekeornado

superaquatpopokekeornado → L → superaquatpokeornado

superaquatpokeornado → R → superaquatornado

위의 4번의 명령으로 문자열 S에서 문자열 W를 제거한 후, 5번째 명령부터는 문자열 W를 찾지 못하므로 이후의 명령은 실행에 실패하고, 문자열 W를 모두 지우는 데에 성공했으므로 Perfect!를 출력한다.

예제 입력 3

erica
irederiericacavelvetu
1
L

예제 출력 3

1
iredericavelvetu
You Lose!

irederiericacavelvetu → L → iredericavelvetu

한 번의 명령 안에 문자열 W를 모두 삭제하지 못했기 때문에 You Lose!를 출력한다.