아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

해커

시간 제한4초메모리 제한512 MB

요약
고정된 문자열에서의 부분 문자열 복사, 부분 문자열 비교, 범위 글자 증가 연산을 순서대로 수행하는 문제.
난이도

어려움10점 중 9점

유형
세그먼트 트리, 해시맵, 문자열 매칭, 연결 리스트
정답자
아직 제출이 없습니다

문제

해커가 밀토스의 이메일 계정을 또 뚫었다. 밀토스는 비밀번호를 훨씬 더 강한 것으로 바꾸기로 했다. 옛 비밀번호 WW는 소문자 알파벳 NN개로 이루어진 문자열이고, 새 비밀번호는 처음에 WW를 그대로 복사한 것이다. 밀토스는 새 비밀번호에 연산 QQ개를 차례로 적용한다. 그 과정을 시뮬레이션해 달라고 부탁했다.

연산은 세 종류다.

  • 1 i j k: 새 비밀번호에서 ii번째부터 jj번째까지의 부분문자열과, 새 비밀번호의 kk번째에서 시작하고 길이가 j−i+1j - i + 1인 부분문자열을 비교한다. 두 부분문자열이 같으면 Y를, 다르면 N을 출력한다.
  • 2 i j k: 새 비밀번호의 ii번째부터 jj번째까지를, 옛 비밀번호 WW의 kk번째에서 시작하고 길이가 j−i+1j - i + 1인 부분문자열로 바꾼다.
  • 3 i j: 새 비밀번호의 ii번째부터 jj번째까지 모든 글자를 순환하며 다음 글자로 바꾼다. a는 b가 되고, b는 c가 되며, z는 a가 된다.

위치는 1부터 센다. 모든 연산은 유효하다. 즉 1≤i≤j≤N1 \le i \le j \le N이고, 1번과 2번 연산에서는 k+j−i≤Nk + j - i \le N이다. 옛 비밀번호 WW는 바뀌지 않으며, 새 비밀번호의 길이는 항상 NN이다.

입력

첫째 줄에 옛 비밀번호 WW가 주어진다. 둘째 줄에 연산의 개수 QQ가 주어진다. 다음 QQ개 줄에 연산이 한 줄에 하나씩 위의 형식으로 주어진다.

출력

1번 연산마다 Y 또는 N을 주어진 순서대로 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    aaaaxazyzab
8
1 1 3 2
2 1 3 7
1 1 3 2
1 2 4 8
3 2 4
1 2 4 9
2 7 10 1
1 6 8 8
    예상 출력
    Y
N
Y
Y
Y