题目描述

你有一个长度为 $n$ 的 $01$ 串 $s$(下标从 $1$ 开始)，现在有 $q$ 个询问，每次取出一个子串，并将该子串从左到右读，左边是高位，所组成的二进制数计为 $P$。你需要进行若干次操作，每次操作可以将 $P$ 加上或减去 $2^k$。$k$ 可以由你任意选定，但是必须保证 $P$ 在任意时刻大于等于 $0$，希望你能求出最小的操作步数使 $P$ 变为 $0$。另外，题目可能会修改 $01$ 串的任意一位。

输入格式

第一行一个数 $n$。

第二行一个长度为 $n$ 的字符串 $s$。

第三行一个数 $q$ 表示询问与修改次数之和。

以下 $q$ 行，每行格式如下:

第一个数 $1 \leq type \leq 2$ 表示类型。

$type = 1$ 表示是一次询问接下来两个数 $l , r$ 表示询问的区间。

$type = 2$ 表示一次修改接下来两个数 $x，y$ 表示把 $s_x$ 改为 $y$。

输出格式

对于每个询问输出一个数表示最少次数。

样例

样例输入

4
1101
1
1 1 4

样例输出

3

数据范围与提示

对于 $20\%$ 的数据，$n, q \leq 10$。

对于 $50\%$ 的数据, $n, q \leq 5000$。

对于另外 $20\%$ 的数据, 没有 $2$ 操作。

对于 $100\%$ 的数据,$n, q \leq 300000$。