문서 제출

ICPC 왕국의 모든 시민은 왕국이 발급한 문서 $N$개를 항상 가지고 있어야 합니다. 문서에는 $1$부터 $N$까지 번호가 붙어 있습니다. 경비원은 순찰 중에 시민들에게 문서를 무작위로 요구하곤 합니다.

Adrian도 ICPC 왕국의 시민이며 이 문서들을 가지고 있습니다. 다만 부주의로 일부 문서를 잃어버렸을 수 있습니다. Adrian이 가진 문서의 상태는 길이 $N$의 문자열 $B$로 나타냅니다. 문서 $i$를 가지고 있으면 $B_i = 1$이고, 없으면 $B_i = 0$입니다.

다음 $Q$일 동안 아래 세 가지 중 하나가 정확히 한 번 일어납니다.

• $1$ $x$: Adrian이 잃어버렸던 문서 $x$를 찾습니다. 그러면 $B_x$가 $1$이 됩니다. 이 일이 일어나기 직전에 $B_x = 0$임이 보장됩니다.
• $2$ $x$: Adrian이 문서 $x$를 잃어버립니다. 그러면 $B_x$가 $0$이 됩니다. 이 일이 일어나기 직전에 $B_x = 1$임이 보장됩니다.
• $3$ $x$ $k$: 경비원이 $x \le k$인 상황에서, $1 \le x + k \cdot i \le N$을 만족하는 모든 $0 \le i$에 대해 문서 $x + k \cdot i$를 요구합니다. 그 시점에 제출하지 못한 문서 하나당 Adrian은 벌금 1코인을 냅니다.

$3$번 일이 일어날 때마다 Adrian이 내야 하는 벌금의 합을 구하세요.

첫 줄에 문서 개수 $N$($1 \le N \le 200000$)이 주어집니다. 둘째 줄에는 길이 $N$의 문자열 $B$가 주어지며, $B$의 $i$번째 글자가 문서 $i$의 초기 상태 $B_i$($B_i \in \{0, 1\}$)입니다.

셋째 줄에 일수 $Q$($1 \le Q \le 200000$)가 주어집니다. 이어지는 $Q$개의 줄에는 각각 일이 하나씩 주어지며, 정수 $t$($t \in \{1, 2, 3\}$)로 시작합니다. $t = 1$ 또는 $t = 2$이면 정수 $x$($1 \le x \le N$)가 뒤따릅니다. $t = 3$이면 정수 $x$와 $k$($1 \le x \le k \le N$)가 뒤따릅니다. $3$번 일은 최소 한 번 있습니다.

$3$번 일마다 Adrian이 내야 하는 벌금 코인 수를 한 줄에 하나씩 출력합니다.