만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

C=A+B

시간 제한2초메모리 제한1024 MB

요약
A, B, C로 칠해진 수열에서 구간에 값을 더하고, 각 C 원소를 대응하는 A와 B 원소의 합으로 바꾸며, 구간 합을 구하는 문제입니다.
난이도

어려움10점 중 8점

유형
세그먼트 트리, 배열, 구현
정답자
아직 제출이 없습니다

문제

길이가 NN인 수열 XX가 있다. NN은 33의 배수이다. 수열 XX의 모든 원소는 AA, BB, CC 중 하나의 색깔로 칠해져 있으며, 각 색깔로 칠한 원소의 개수는 모두 N3\frac{N}{3}개로 같다. 수열의 앞에서부터 AA로 칠한 원소를 차례대로 A1,A2,⋯ ,AN3A_1, A_2, \cdots, A_{\frac{N}{3}}이라고 정의한다. BB와 CC도 같은 방식으로 BiB_i, CiC_i를 정의한다.

다음 세 종류의 쿼리를 처리하는 프로그램을 작성하라.

  • 1 i j k: 수열 XX의 ii번째 원소부터 jj번째 원소까지에 kk를 더한다.
  • 2 i j: 수열 XX의 ii번째 원소부터 jj번째 원소 중 CC로 칠해진 원소에 대해 Ct=At+BtC_t = A_t + B_t를 적용한다.
  • 3 i j: 수열 XX의 ii번째 원소부터 jj번째 원소까지의 합을 출력한다.

입력

첫 번째 줄에 33의 배수인 NN이 주어진다. (3≤N≤300 000)(3 \leq N \leq 300\,000)

두 번째 줄에 정수 X1,X2,⋯ ,XNX_1, X_2, \cdots, X_N이 공백으로 구분되어 순서대로 주어진다. (1≤Xi≤100 000)(1 \leq X_i \leq 100\,000)

세 번째 줄에는 A, B, C로만 이루어진 길이 NN의 문자열이 주어진다. 문자열의 ii번째 문자는 XiX_i가 칠해진 색깔이다.

네 번째 줄에 쿼리의 개수 QQ가 주어진다. (1≤Q≤100 000)(1 \leq Q \leq 100\,000)

다음 QQ개의 줄에 쿼리가 한 줄에 하나씩 주어진다. (1≤i≤j≤N; 1≤k≤100 000)(1 \leq i \leq j \leq N;\ 1 \leq k \leq 100\,000)

입력되는 값은 모두 정수이다.

출력

33번 쿼리가 주어질 때마다 한 줄에 하나씩 그 결과를 출력한다.

예제1

  1. 예제 1

    입력
    6
1 2 3 4 5 6
ABBCAC
4
1 4 6 3
3 3 5
2 4 6
3 1 6
    예상 출력
    18
28