덱에서의 팰린드롬

초기에 빈 문자열 $s$가 있다. 쿼리 $Q$개를 처리한다.

• 0 $c$: 문자열 $s$의 맨 앞에 문자 $c$을 추가한다.
• 1 $c$: 문자열 $s$의 맨 뒤에 문자 $c$을 추가한다.
• 2: 문자열 $s$의 맨 앞에 있는 문자를 제거한다.
• 3: 문자열 $s$의 맨 뒤에 있는 문자를 제거한다.

각 쿼리를 처리한 후, 다음 $3$개의 값을 순서대로 출력한다.

• $s$의 서로 다른 비어 있지 않은 팰린드롬 부분 문자열의 개수
• $s$의 가장 긴 팰린드롬 접두사의 길이
• $s$의 가장 긴 팰린드롬 접미사의 길이

$s$가 빈 문자열이면, 대신 0 0 0을 출력한다.

제한 조건

• $1 \leq Q \leq 500000$
• $c$는 영문 소문자이다.
• 쿼리 $2$ 또는 쿼리 $3$가 주어질 때 문자열 $s$는 비어 있지 않다.

$Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
$\vdots$
$\textrm{Query}_{Q - 1}$

각 쿼리를 처리한 후, 다음 $3$개의 값을 순서대로 출력한다.

$s$가 빈 문자열이면, 대신 0 0 0을 출력한다.