캠핑장 전력 패킷의 유효 구간

문제

캠핑장의 전력 관제기는 세 구역에서 보내는 전력 변화량과 초기화 명령을 하나의 통신 기록에 저장한다. 임베디드 장치 담당자는 이 기록을 해석하여, 변화량의 합이 지정된 범위에 들어가는 관측 구간의 개수를 구하려 한다. 통신 기록의 문자 하나는 정확히 하나의 6비트 패킷을 나타낸다. 문자표는 대문자 A부터 Z, 소문자 a부터 z, 숫자 0부터 9, 문자 +와 /를 차례로 이어 붙인 것이다. 문자표의 맨 앞 문자를 0번으로 할 때, 문자의 번호가 패킷의 정숫값이다. 비트 번호는 최하위 비트부터 0번이다. 패킷의 상위 2비트가 0, 1, 2 중 하나이면 해당 번호 구역의 측정 패킷이다. 하위 4비트를 부호 있는 4비트 정수로 해석한 값이 전력 변화량이다. 즉, 하위 4비트의 정숫값이 d일 때 d가 8 미만이면 변화량은 d이고, 그렇지 않으면 d−16이다. 상위 2비트가 3이면 초기화 패킷이다. 이때 3번 비트는 반드시 0이며, 하위 3비트 중 적어도 하나는 1이다. 하위 비트 중 c번 비트가 1이면 c번 구역을 초기화한다. 한 패킷으로 여러 구역을 동시에 초기화할 수 있다. 각 구역의 측정값을 도착 순서대로 모으되, 그 구역을 초기화하는 패킷이 나올 때마다 측정값 목록을 나눈다. 초기화 이전과 이후의 측정값은 같은 목록에 속할 수 없다. 다른 구역의 측정 패킷과 해당 구역을 초기화하지 않는 패킷은 목록에 영향을 주지 않는다. 관측 구간은 이렇게 나눈 목록 하나에서 연속한 측정값을 하나 이상 고른 것이다. 변화량의 합이 L 이상 R 이하인 관측 구간을 유효하다고 한다. 값이 같더라도 구역이나 시작 또는 끝 측정 패킷이 다르면 서로 다른 구간이다. 세 구역의 유효한 관측 구간 개수를 모두 더하여 출력한다.

입력

첫째 줄에 정수 N, L, R이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000이고, −1,600,000 ≤ L ≤ R ≤ 1,600,000이다.
둘째 줄에 패킷 N개를 나타내는 길이 N의 문자열이 주어진다. 각 문자는 지문에 정의한 문자표에 속한다. 모든 초기화 패킷은 지문의 비트 조건을 만족한다.

출력

유효한 관측 구간의 총개수를 정수 하나로 출력한다. 유효한 구간이 없으면 0을 출력한다.

7 1 2
BCRPBxC

8

5 0 0
AAQxA

5

3 1 7
IIP

0

출처: Devin.KR 자체 제작