35287번 - MC 히페리온

힙합을 이해한 hyperion1019의 모습

국어사전을 뜯어먹으며 방구석 힙합퍼 생활을 이어가던 MC 히페리온은 드디어 힙합을 이해했다! 어떤 라임이 좋은 라임인지 깨닫게 된 것이다. 그는 서울대학교를 대표하는 래퍼로서 신촌지역 학교 연합에 도전장을 내밀었다.

길고 긴 선별 과정 끝에 신촌지역 학교 연합의 대표로 선발된 clp135는 히페리온이 방심한 틈을 타 그의 라임 노트를 훔치는 데 성공했다. 이 노트에는 그가 발견한 $N$개의 좋은 단어 $S_1, S_2, \dots, S_N$과 각 단어의 영향력을 나타내는 라임 가중치 $W_i$가 적혀 있다. clp135는 이를 분석해 히페리온의 라임 파워를 역이용하기로 했다.

히페리온이 깨달은 라임 파워 법칙은 다음과 같다. 그가 가사에 사용할 라임이 길면 길수록, 그리고 그 라임을 뒷받침해 주는 좋은 단어들이 강력할수록 라임 파워는 폭발한다.

구체적으로, 문자열 $T$의 라임 파워는 다음과 같이 계산된다.

1. 노트에 적힌 좋은 단어 중 $T$가 $S_i$의 접미사(suffix)인 단어들을 모두 찾는다. 접미사는 문자열의 특정 지점부터 마지막 문자까지를 포함하는 연속된 부분 문자열을 의미한다.
2. 그 단어들의 라임 가중치를 모두 더한다.
3. 그 합에 라임 $T$의 길이 $|T|$를 곱한다.

트렌드에 민감한 신촌 지역의 특성상, 단어들의 가치는 수시로 재평가된다. clp135는 이 빠르게 변화하는 트렌드에 맞추어 떠오르는 라임의 파워를 즉시 계산해야 한다.

다음 쿼리를 처리하는 프로그램을 작성하여 신촌지역 학교 연합이 승리할 수 있도록 도와주자.

• $1 \ i \ X$: $i$번째 좋은 단어 $S_i$의 라임 가중치를 정수 $X$로 변경한다.
• $2 \ T$: 문자열 $T$의 라임 파워를 구한다.

첫 번째 줄에 좋은 단어의 개수 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. ($1 \le N, Q \le 100\,000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 좋은 단어 $S_1, S_2, \dots, S_N$이 한 줄에 하나씩 주어진다. 모든 단어는 알파벳 소문자로만 구성된다. 좋은 단어는 중복되지 않는다.

그다음 줄에 각 단어의 초기 라임 가중치를 나타내는 $N$개의 정수 $W_1, W_2, \dots, W_N$이 공백으로 구분되어 주어진다. ($0 \le W_i \le 10\,000$)

그다음 줄부터 $Q$개의 줄에 걸쳐 쿼리가 주어진다.

• $1 \ i \ X$: $i$번째 좋은 단어 $S_i$의 라임 가중치를 정수 $X$로 변경한다. ($1 \le i \le N$; $0 \le X \le 10\,000$)
• $2 \ T$: 문자열 $T$에 대한 라임 파워를 구한다. $T$는 알파벳 소문자로만 구성된다.

주어지는 모든 문자열(좋은 단어 및 쿼리 문자열)의 길이의 합은 $2\,000\,000$을 넘지 않는다.

2번 쿼리가 주어질 때마다, 해당 문자열의 라임 파워를 한 줄에 하나씩 출력한다. 만약 $T$를 접미사로 가지는 좋은 단어가 하나도 없다면 0을 출력한다.

2번 쿼리가 하나 이상 주어짐이 보장된다.

hyperion1019는 힙합을 좋아한다.