친구들

$N$명의 친구가 게임을 한다. 게임은 $L$개의 칸이 일렬로 놓인 판에서 진행되며, 칸에는 $0$부터 $L - 1$까지 번호가 붙어 있고 칸 $i$와 칸 $i+1$은 서로 인접하다. 어느 순간에도 한 칸에는 친구가 많아야 한 명 서 있다. 게임의 각 단계에서 친구 한 명이 현재 칸에서 다른 (비어 있는) 칸으로 점프한다.

게임 중 어느 순간이든, 한 친구의 점수는 그 친구가 속한 가장 긴 연속한 친구 구간의 길이이다. 즉, 어떤 친구가 위치 $x$에 서 있고 $a, a + 1, ..., x - 1, x, x + 1, ..., b - 1, b$ 위치에 친구가 있다면 그 친구의 점수는 $b - a + 1$이다.

게임의 총점은 모든 친구의 점수를 더한 값이다. 게임 도중 여러 시점에서 친구들은 현재 총점이 얼마인지 궁금해한다.

채점기는 다음 형식으로 입력을 읽는다.

• $1$번째 줄: N L Q
• $2$번째 줄: P[0] P[1] .. P[N - 1]
• $3$번째 줄부터 $3 + Q - 1$번째 줄까지: 각 줄은 점프나 점수 질문 중 하나이다. 줄이 0 A B이면 $A$에서 $B$로 점프를 하고, 줄이 1이면 점수를 묻는다.

각 점수 질문에 대해 채점기는 score()의 반환값을 한 줄에 출력한다.

• $1 \le N \le 100\,000$
• $1 \le L \le 10^9$
• $S + J \le 200\,000$