I used to believe We were burning on the edge of something beautiful Something beautiful Selling a dream Smoke and mirrors keep us waiting on a miracle On a miracle Say go through the darkest of days Heaven's a heartbreak away Never let you go Never let me down OH it's been a hell of a ride Driving the edge of a knife Never let you go Never let me down Bieber拥有一个长度为n的01 串，他每次会选出这个串的一个子串作为曲谱唱歌，考虑该子串从左往右读所组成的二进制数P。 Bieber每一秒歌唱可以让P增加或减少 2 的 k次方（k由Bieber选定），但必须保证任意时刻其P大于等于0。 Bieber 是一位追求效率的人 每次Bieber都想知道他歌唱的最少时间将这个数P变成0。 Bieber 正和 一位DJ合作，他随时可能修改串上的一个字符。

输入描述:

第一行一个数n第二行一个长度为n的字符串s第三行一个数 t 表示 询问 + 修改总次数以下 t 行， 每行格式如下第一个数 1 Type = 1 表示是一次 询问 接下来两个数 l , r 表示询问的区间。否则 表示一次修改 接下来两个数x，y 表示把 s[x] 改为y.n = 3e5, t = 3e5

输出描述:

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