2^k teams participate in a playoff tournament. The tournament consists of 2^k - 1 games. They are held as follows: first of all, the teams are split into pairs: team 1 plays against team 2, team 3 plays against team 4 (exactly in this order), and so on (so, 2^{k-1} games are played in that phase). When a team loses a game, it is eliminated, and each game results in elimination of one team (there are no ties). After that, only 2^{k-1} teams remain. If only one team remains, it is declared the champion; otherwise, 2^{k-2} games are played: in the first one of them, the winner of the game "1 vs 2" plays against the winner of the game "3 vs 4", then the winner of the game "5 vs 6" plays against the winner of the game "7 vs 8", and so on. This process repeats until only one team remains.

For example, this picture describes the chronological order of games with k = 3:

<image>

Let the string s consisting of 2^k - 1 characters describe the results of the games in chronological order as follows:

  * if s_i is 0, then the team with lower index wins the i-th game; 
  * if s_i is 1, then the team with greater index wins the i-th game; 
  * if s_i is ?, then the result of the i-th game is unknown (any team could win this game). 



Let f(s) be the number of possible winners of the tournament described by the string s. A team i is a possible winner of the tournament if it is possible to replace every ? with either 1 or 0 in such a way that team i is the champion.

You are given the initial state of the string s. You have to process q queries of the following form: 

  * p c — replace s_p with character c, and print f(s) as the result of the query. 

Input

The first line contains one integer k (1 ≤ k ≤ 18).

The second line contains a string consisting of 2^k - 1 characters — the initial state of the string s. Each character is either ?, 0, or 1.

The third line contains one integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of queries.

Then q lines follow, the i-th line contains an integer p and a character c (1 ≤ p ≤ 2^k - 1; c is either ?, 0, or 1), describing the i-th query.

Output

For each query, print one integer — f(s).

Example

Input


3
0110?11
6
5 1
6 ?
7 ?
1 ?
5 ?
1 1


Output


1
2
3
3
5
4

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph traversal

Implementation

Tree algorithms

Dynamic programming

Data structures


Solutions:
import os
import sys
from io import BytesIO, IOBase

def solve(z, dp, s):
	n = len(dp)
	while 1:
		dp[z] = 0
		if s[z] == '?':
			if 2 * z + 1 < n:
				dp[z] += dp[2 * z + 1]
			else:
				dp[z] += 1
			if 2 * z + 2 < n:
				dp[z] += dp[2 * z + 2]
			else:
				dp[z] += 1
		elif s[z] == '1':
			if 2 * z + 1 < n:
				dp[z] += dp[2 * z + 1]
			else:
				dp[z] += 1
		elif 2 * z + 2 < n:
			dp[z] += dp[2 * z + 2]
		else:
			dp[z] += 1
		if not z:
			return
		z = (z - 1) // 2

def main():
	input()
	s = list(input().rstrip())
	s.reverse()
	n = len(s)
	dp = [0] * n
	for i in range(n - 1, -1, -1):
		if s[i] == '?':
			if 2 * i + 1 < n:
				dp[i] += dp[2 * i + 1]
			else:
				dp[i] += 1
			if 2 * i + 2 < n:
				dp[i] += dp[2 * i + 2]
			else:
				dp[i] += 1
		elif s[i] == '1':
			if 2 * i + 1 < n:
				dp[i] += dp[2 * i + 1]
			else:
				dp[i] = 1
		elif 2 * i + 2 < n:
			dp[i] += dp[2 * i + 2]
		else:
			dp[i] = 1
	for i in range(int(input())):
		(x, y) = input().split()
		x = n - int(x)
		s[x] = y
		solve(x, dp, s)
		print(dp[0])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
import io, os
input = sys.stdin.readline
k = int(input())
s = list(str(input().rstrip()))

def final():
	if s[-1] == '0':
		return c[-1][0]
	elif s[-1] == '1':
		return c[-1][1]
	else:
		return c[-1][0] + c[-1][1]
n = 2 ** k - 1
match_num = [0 for i in range(n)]
rnd_start = {}
rnd = [0 for i in range(n)]
curr = k - 1
m = 1
for i in range(n):
	match_num[i] = m - 1
	rnd[i] = curr + 1
	if 2 ** curr == m:
		m = 0
		curr -= 1
		rnd_start[curr + 2] = i - 2 ** (curr + 1) + 1
	m += 1
c = [[0, 0] for i in range(n)]
for i in range(2 ** (k - 1)):
	c[i][0] = c[i][1] = 1
for i in range(2 ** (k - 1), n):
	match = rnd_start[rnd[i] + 1] + match_num[i] * 2
	if s[match] == '0':
		c[i][0] = c[match][0]
	elif s[match] == '1':
		c[i][0] = c[match][1]
	else:
		c[i][0] = c[match][0] + c[match][1]
	match += 1
	if s[match] == '0':
		c[i][1] = c[match][0]
	elif s[match] == '1':
		c[i][1] = c[match][1]
	else:
		c[i][1] = c[match][0] + c[match][1]
for q in range(int(input())):
	(ind, v) = input().split()
	ind = int(ind)
	if s[ind - 1] == v:
		print(final())
		continue
	ind -= 1
	if True:
		prev = s[ind]
		s[ind] = v
		curr = ind
		for i in range(rnd[ind] - 1):
			match = rnd_start[rnd[curr] - 1] + match_num[curr] // 2
			if s[curr] == '0':
				c[match][match_num[curr] % 2] = c[curr][0]
			elif s[curr] == '1':
				c[match][match_num[curr] % 2] = c[curr][1]
			else:
				c[match][match_num[curr] % 2] = c[curr][0] + c[curr][1]
			curr = match
	print(final())


import sys, os
from io import BytesIO, IOBase
from functools import lru_cache
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
tc = 1
for test in range(1, tc + 1):
	(n,) = inp()
	a = list(input())[::-1]
	n = len(a)
	ans = [0] * (4 * n)
	for i in range(n, 4 * n):
		ans[i] = 1
	for i in range(n - 1, -1, -1):
		left = 2 * i + 1
		right = 2 * i + 2
		if a[i] == '0':
			ans[i] = ans[right]
		if a[i] == '1':
			ans[i] = ans[left]
		if a[i] == '?':
			ans[i] = ans[left] + ans[right]

	def fill(i, val):
		a[i] = val
		while True:
			left = 2 * i + 1
			right = 2 * i + 2
			if a[i] == '0':
				ans[i] = ans[right]
			if a[i] == '1':
				ans[i] = ans[left]
			if a[i] == '?':
				ans[i] = ans[left] + ans[right]
			if i == 0:
				break
			i = (i - 1) // 2
	for q in range(int(input())):
		(ind, val) = input().split()
		fill(n - int(ind), val)
		print(ans[0])


from sys import stdin, stdout
input = stdin.readline

def f(ind):
	if len(tree[ind]) == 0:
		if s[ind] == '?':
			return 2
		else:
			return 1
	if s[ind] == '?':
		return f(tree[ind][0]) + f(tree[ind][1])
	if s[ind] == '0':
		return f(tree[ind][1])
	return f(tree[ind][0])

def f1(ind):
	if len(tree[ind]) == 0:
		if s[ind] == '?':
			dp[ind] = 2
		else:
			dp[ind] = 1
		return dp[ind]
	x = f1(tree[ind][0])
	y = f1(tree[ind][1])
	if s[ind] == '?':
		dp[ind] = x + y
		return dp[ind]
	if s[ind] == '0':
		dp[ind] = y
		return dp[ind]
	dp[ind] = x
	return dp[ind]
t = 1
for _ in range(t):
	k = int(input())
	s1 = input().strip()
	n = len(s1)
	s1 = s1[::-1]
	s = [i for i in s1]
	dp = [-1 for i in range(n)]
	tree = [[] for i in range(n)]
	par = [-1 for i in range(n)]
	for i in range(n):
		if 2 * i + 1 >= n:
			continue
		tree[i].append(2 * i + 1)
		tree[i].append(2 * i + 2)
		par[2 * i + 1] = i
		par[2 * i + 2] = i
	f1(0)
	Q = int(input())
	for q in range(Q):
		(p, c) = input().split()
		p = int(p)
		a = n - p
		s[a] = c
		val = a
		while 1:
			if val == -1:
				stdout.write(str(dp[0]) + '\n')
				break
			if len(tree[val]) == 0:
				if s[val] == '?':
					dp[val] = 2
				else:
					dp[val] = 1
				val = par[val]
				continue
			if s[val] == '?':
				dp[val] = dp[tree[val][0]] + dp[tree[val][1]]
			elif s[val] == '1':
				dp[val] = dp[tree[val][0]]
			else:
				dp[val] = dp[tree[val][1]]
			val = par[val]


import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def dadd(d, p, val):
	if p in d:
		d[p].append(val)
	else:
		d[p] = [val]

def gi():
	return [xx for xx in input().split()]

def gtc(tc, *ans):
	print('Case #' + str(tc) + ':', *ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def bits(i, n):
	p = bin(i)[2:]
	return (n - len(p)) * '0' + p

def prec(a, pre):
	for i in a:
		pre.append(pre[-1] + i)
	pre.pop(0)

def YN(flag):
	print('YES' if flag else 'NO')

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = 1
INF = 10 ** 18
uu = t
mod = 10 ** 9 + 7

def f(sm, lg, v):
	if v == '0':
		return sm
	elif v == '1':
		return lg
	else:
		return sm + lg
while t > 0:
	t -= 1
	n = fi()
	s = si()
	q = fi()
	c = 0
	dp = [[1] * (2 ** n + 1) for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		for j in range(2 ** i):
			dp[i][j] = f(dp[i + 1][2 * j], dp[i + 1][2 * j + 1], s[c + j])
		c += 2 ** i
	for _ in range(q):
		(ind, v) = input().split()
		ind = int(ind)
		s[ind - 1] = v
		for i in range(n - 1, -1, -1):
			if 2 ** i >= ind:
				break
			ind -= 2 ** i
		j = ind - 1
		c = 2 ** n - 2 ** (i + 1)
		while i >= 0:
			dp[i][j] = f(dp[i + 1][2 * j], dp[i + 1][2 * j + 1], s[c + j])
			c += 2 ** i
			i -= 1
			j //= 2
		print(dp[0][0])


import sys
input = sys.stdin.readline

def im():
	return map(int, input().split())

def ii():
	return int(input())

def il():
	return list(map(int, input().split()))

def ins():
	return input()[:-1]
k = ii()
lis = list(ins())
lis.reverse()
n = len(lis)
ldp = [1] * n
rdp = [1] * n
for i in range(n - 1, 0, -1):
	parent = (i - 1) // 2
	if lis[i] == '?':
		if i == parent * 2 + 1:
			ldp[parent] = ldp[i] + rdp[i]
		else:
			rdp[parent] = ldp[i] + rdp[i]
	elif lis[i] == '1':
		if i == parent * 2 + 1:
			ldp[parent] = ldp[i]
		else:
			rdp[parent] = ldp[i]
	elif i == parent * 2 + 1:
		ldp[parent] = rdp[i]
	else:
		rdp[parent] = rdp[i]
for _ in range(ii()):
	(i, c) = map(str, input().split())
	i = n - int(i)
	lis[i] = c
	while i != 0:
		parent = (i - 1) // 2
		if lis[i] == '?':
			if i == parent * 2 + 1:
				ldp[parent] = ldp[i] + rdp[i]
			else:
				rdp[parent] = ldp[i] + rdp[i]
		elif lis[i] == '1':
			if i == parent * 2 + 1:
				ldp[parent] = ldp[i]
			else:
				rdp[parent] = ldp[i]
		elif i == parent * 2 + 1:
			ldp[parent] = rdp[i]
		else:
			rdp[parent] = rdp[i]
		i = (i - 1) // 2
	if lis[0] == '?':
		print(ldp[0] + rdp[0])
	elif lis[0] == '0':
		print(rdp[0])
	else:
		print(ldp[0])


import sys
input = sys.stdin.readline
k = int(input())
s = list(input().rstrip())
q = int(input())
query = [input().rstrip().split() for i in range(q)]
a = [' '] + s[::-1]
n = len(a)
cnt = [0] * n
for i in range(n // 2, n):
	if a[i] == '?':
		cnt[i] = 2
	else:
		cnt[i] = 1
for i in range(1, n // 2)[::-1]:
	if a[i] == '?':
		cnt[i] = cnt[i * 2] + cnt[i * 2 + 1]
	elif a[i] == '1':
		cnt[i] = cnt[i * 2]
	else:
		cnt[i] = cnt[i * 2 + 1]
for j in range(q):
	(p, c) = query[j]
	p = int(p)
	i = n - p
	a[i] = c
	if i >= n // 2:
		if a[i] == '?':
			cnt[i] = 2
		else:
			cnt[i] = 1
		i //= 2
	while i >= 1:
		if a[i] == '?':
			cnt[i] = cnt[i * 2] + cnt[i * 2 + 1]
		elif a[i] == '1':
			cnt[i] = cnt[i * 2]
		else:
			cnt[i] = cnt[i * 2 + 1]
		i //= 2
	print(cnt[1])


class SegTree:

	def __init__(self, arr):
		self.size = len(arr)
		self.tree = [-1] * self.size
		self.winners = list(arr[::-1])
		self.init_tree(0)

	def left(self, x):
		return self.tree[2 * x + 1]

	def right(self, x):
		return self.tree[2 * x + 2]

	def init_tree(self, x):
		if x >= self.size:
			return 1
		if self.winners[x] == '?':
			self.tree[x] = self.init_tree(2 * x + 1) + self.init_tree(2 * x + 2)
		elif self.winners[x] == '1':
			self.tree[x] = self.init_tree(2 * x + 1)
			self.init_tree(2 * x + 2)
		else:
			self.tree[x] = self.init_tree(2 * x + 2)
			self.init_tree(2 * x + 1)
		return self.tree[x]

	def insert(self, i, x):
		change_index = self.size - int(i)
		if self.winners[change_index] == x:
			return
		self.winners[change_index] = x
		old = self.tree[change_index]
		new = self.get_winner_nr(change_index)
		if old == new:
			return
		cur = (change_index - 1) // 2
		while cur >= 0:
			old = self.tree[cur]
			winner = self.winners[cur]
			if winner == '?':
				new = self.tree[2 * cur + 1] + self.tree[2 * cur + 2]
			elif winner == '1':
				new = self.tree[2 * cur + 1]
			else:
				new = self.tree[2 * cur + 2]
			self.tree[cur] = new
			if old == new:
				break
			cur = (cur - 1) // 2

	def get_winner_nr(self, change_index):
		if 2 * change_index + 2 >= self.size:
			res = 1 if self.winners[change_index] != '?' else 2
			self.tree[change_index] = res
			return res
		x = change_index
		return self.get_winner_inner(x)

	def get_winner_inner(self, x):
		if self.winners[x] == '?':
			self.tree[x] = self.tree[2 * x + 1] + self.tree[2 * x + 2]
		elif self.winners[x] == '1':
			self.tree[x] = self.tree[2 * x + 1]
		else:
			self.tree[x] = self.tree[2 * x + 2]
		return self.tree[x]
import sys

def solve(bits, queries):
	seg = SegTree(bits)
	for q in queries:
		(index, value) = q.split(' ')
		seg.insert(index, value)
		sys.stdout.write(str(seg.tree[0]) + '\n')
import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
k = int(input().decode().strip())
bits = input().decode().strip()
N = int(input().decode().strip())
queries = [0] * N
for i in range(N):
	queries[i] = input().decode().strip()
res = solve(bits, queries)


import sys
input = sys.stdin.readline
k = int(input())
s = input().strip()
a = ['*'] + list(s[::-1])
dp = [0] * (1 << k)
for i in range((1 << k) - 1, 0, -1):
	if 2 * i < 1 << k:
		if a[i] == '1':
			dp[i] = dp[2 * i]
		elif a[i] == '0':
			dp[i] = dp[2 * i + 1]
		else:
			dp[i] = dp[2 * i] + dp[2 * i + 1]
	elif a[i] == '?':
		dp[i] = 2
	else:
		dp[i] = 1

def solve():
	(idx, char) = input().split()
	idx = int(idx)
	idx = (1 << k) - idx
	a[idx] = char
	cur = idx
	while cur:
		if 2 * cur >= 1 << k:
			if a[cur] == '?':
				dp[cur] = 2
			else:
				dp[cur] = 1
			cur //= 2
			continue
		if a[cur] == '1':
			dp[cur] = dp[2 * cur]
		elif a[cur] == '0':
			dp[cur] = dp[2 * cur + 1]
		else:
			dp[cur] = dp[2 * cur] + dp[2 * cur + 1]
		cur //= 2
	cur = 1
	ans = 1
	while 2 * cur < 1 << k:
		if a[cur] == '1':
			cur = 2 * cur
		elif a[cur] == '0':
			cur = 2 * cur + 1
		else:
			break
	print(dp[cur])
for nq in range(int(input())):
	solve()


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
k = int(input())
s = [c for c in input()]
segment_val = [1 for i in range(2 ** (k + 1))]
game_idx_to_segment_idx = [-1 for i in range(2 ** k)]
segment_idx_to_game_idx = [-1 for i in range(2 ** k)]
next_idx = 0
for i in range(k - 1, -1, -1):
	for n in range(2 ** i, 2 ** (i + 1)):
		game_idx_to_segment_idx[next_idx] = n
		segment_idx_to_game_idx[n] = next_idx
		next_idx += 1

def init():
	for i in range(2 ** k - 1, 0, -1):
		game_idx = segment_idx_to_game_idx[i]
		t = s[game_idx]
		if t == '0':
			segment_val[i] = segment_val[2 * i]
		elif t == '1':
			segment_val[i] = segment_val[2 * i + 1]
		else:
			segment_val[i] = segment_val[2 * i] + segment_val[2 * i + 1]

def update(k, c):
	i = game_idx_to_segment_idx[k - 1]
	s[k - 1] = c
	while i:
		game_idx = segment_idx_to_game_idx[i]
		t = s[game_idx]
		if t == '0':
			segment_val[i] = segment_val[2 * i]
		elif t == '1':
			segment_val[i] = segment_val[2 * i + 1]
		else:
			segment_val[i] = segment_val[2 * i] + segment_val[2 * i + 1]
		i >>= 1
init()
for _ in range(int(input())):
	(k, c) = input().split()
	k = int(k)
	update(k, c)
	print(segment_val[1])


import sys
from sys import stdin
ANS = []
k = int(stdin.readline())
n = 2 ** k - 1
s = list(stdin.readline()[:-1])
s.reverse()
dp = [0] * n
for i in range(n - 1, -1, -1):
	if 2 * i + 1 >= n:
		if s[i] == '?':
			dp[i] = 2
		else:
			dp[i] = 1
	else:
		if s[i] == '1' or s[i] == '?':
			dp[i] += dp[2 * i + 1]
		if s[i] == '0' or s[i] == '?':
			dp[i] += dp[2 * i + 2]
q = int(stdin.readline())
for loop in range(q):
	(p, c) = stdin.readline()[:-1].split()
	p = n - int(p)
	s[p] = c
	while True:
		dp[p] = 0
		if 2 * p + 1 >= n:
			if s[p] == '?':
				dp[p] = 2
			else:
				dp[p] = 1
		else:
			if s[p] == '1' or s[p] == '?':
				dp[p] += dp[2 * p + 1]
			if s[p] == '0' or s[p] == '?':
				dp[p] += dp[2 * p + 2]
		if p == 0:
			break
		p = (p - 1) // 2
	ANS.append(str(dp[0]))
print('\n'.join(ANS))


def solve(s: str) -> int:
	n = len(s)
	dp = [-1] * n
	for idx in range(n - 1, -1, -1):
		if idx * 2 + 1 >= n:
			dp[idx] = 2 if s[idx] == '?' else 1
		elif s[idx] == '?':
			dp[idx] = dp[idx * 2] + dp[idx * 2 + 1]
		elif s[idx] == '0':
			dp[idx] = dp[idx * 2 + 1]
		else:
			dp[idx] = dp[idx * 2]
	return dp
input()
s = ' ' + input()[::-1]
dp = solve(s)
s = [i for i in s]
q = []
for _ in range(int(input())):
	q.append(input().split())
for (idx, c) in q:
	idx = len(s) - int(idx)
	s[idx] = c
	while idx:
		if idx * 2 + 1 >= len(s):
			if s[idx] == '?':
				dp[idx] = 2
			else:
				dp[idx] = 1
		elif s[idx] == '?':
			dp[idx] = dp[idx * 2] + dp[idx * 2 + 1]
		elif s[idx] == '0':
			dp[idx] = dp[idx * 2 + 1]
		else:
			dp[idx] = dp[idx * 2]
		idx //= 2
	print(dp[1])


from sys import stdin
input = stdin.readline

def answer():
	for i in range(n, 0, -1):
		i = -i
		if 2 * -i > n:
			if s[i] == '0' or s[i] == '1':
				dp[i] = 1
			else:
				dp[i] = 2
		else:
			if s[i] == '1':
				dp[i] = dp[2 * i]
			elif s[i] == '0':
				dp[i] = dp[2 * i - 1]
			else:
				dp[i] = dp[2 * i] + dp[2 * i - 1]
			parent[2 * i] = i
			parent[2 * i - 1] = i

def update_ans(i):
	if 2 * -i > n:
		if s[i] == '0' or s[i] == '1':
			dp[i] = 1
		else:
			dp[i] = 2
	elif s[i] == '1':
		dp[i] = dp[2 * i]
	elif s[i] == '0':
		dp[i] = dp[2 * i - 1]
	else:
		dp[i] = dp[2 * i] + dp[2 * i - 1]
	while parent[i]:
		if 2 * parent[i] == i:
			left = i
			right = i - 1
		else:
			left = i + 1
			right = i
		if s[parent[i]] == '1':
			dp[parent[i]] = dp[left]
		elif s[parent[i]] == '0':
			dp[parent[i]] = dp[right]
		else:
			dp[parent[i]] = dp[left] + dp[right]
		i = parent[i]
k = int(input())
s = list(input()[:-1])
n = len(s)
dp = [0] * (n + 1)
parent = [0] * (n + 1)
answer()
for q in range(int(input())):
	(ind, ch) = input().split()
	ind = int(ind)
	s[ind - 1] = ch
	update_ans(-(n - ind + 1))
	print(dp[n])


def get_total(total, char, left, right, idx):
	if left[idx] == -1:
		if char[idx] == '?':
			return 2
		else:
			return 1
	elif char[idx] == '?':
		return total[left[idx]] + total[right[idx]]
	elif char[idx] == '0':
		return total[left[idx]]
	else:
		return total[right[idx]]

def main():
	k = int(input())
	s = list(input())
	q = int(input())
	l = []
	for i in range(q):
		(p, c) = input().split()
		l.append((int(p), c))
	left = []
	right = []
	parent = []
	total = []
	d = 2 ** k
	z = z2 = 0
	for i in range(k):
		d //= 2
		for j in range(d):
			parent.append(-1)
			if i:
				left.append(z2)
				right.append(z2 + 1)
				parent[z2] = parent[z2 + 1] = z
				z2 += 2
			else:
				left.append(-1)
				right.append(-1)
			total.append(get_total(total, s, left, right, z))
			z += 1
	for i in range(q):
		idx = l[i][0] - 1
		s[idx] = l[i][1]
		total[idx] = get_total(total, s, left, right, idx)
		while parent[idx] != -1:
			idx = parent[idx]
			total[idx] = get_total(total, s, left, right, idx)
		print(total[-1])
main()


import sys

def input():
	return sys.stdin.readline().strip()
k = int(input())
s = [''] + list(reversed(list(input())))
out = [1] * 2 ** (k + 1)

def update(i):
	if s[i] == '1':
		out[i] = out[i * 2]
	elif s[i] == '0':
		out[i] = out[i * 2 + 1]
	else:
		out[i] = out[i * 2] + out[i * 2 + 1]
for i in range(2 ** k - 1, 0, -1):
	update(i)
ans = []
q = int(input())
for _ in range(q):
	(i, c) = input().split()
	i = 2 ** k - int(i)
	if c == s[i]:
		ans.append(out[1])
	else:
		s[i] = c
		update(i)
		while i > 1 and (s[i // 2] == '?' or i & 1 ^ int(s[i // 2])):
			i //= 2
			update(i)
		ans.append(out[1])
print('\n'.join(map(str, ans)))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
import bisect, string, math, time, functools, random, fractions
from bisect import *
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby
rep = range
R = range

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def AI():
	return map(int, open(0).read().split())

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def NLI(n):
	return [[int(i) for i in input().split()] for i in range(n)]

def NLI_(n):
	return [[int(i) - 1 for i in input().split()] for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def RLI(n=8, a=1, b=10):
	return [random.randint(a, b) for i in range(n)]

def RI(a=1, b=10):
	return random.randint(a, b)

def INP():
	N = 10
	n = random.randint(1, N)
	a = RLI(n, 0, n - 1)
	return (n, a)

def Rtest(T):
	(case, err) = (0, 0)
	for i in range(T):
		inp = INP()
		a1 = naive(*inp)
		a2 = solve(*inp)
		if a1 != a2:
			print(inp)
			print('naive', a1)
			print('solve', a2)
			err += 1
		case += 1
	print('Tested', case, 'case with', err, 'errors')

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in R(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in R(base ** n):
		s = [tb // base ** bt % base for bt in R(n)]
		rt += [s]
	return rt

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y

def YN(x):
	print(['NO', 'YES'][x])

def Yn(x):
	print(['No', 'Yes'][x])

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
mo = 10 ** 9 + 7
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
alp = [chr(ord('a') + i) for i in range(26)]

def gcj(c, x):
	print('Case #{0}:'.format(c + 1), x)
show_flg = False
show_flg = True

class SegTree:

	def __init__(self, n, ls, init_val=1, function=lambda a, b: a + b, ide=0):
		self.size = n
		self.ls = ls
		self.ide_ele = ide
		self.num = 1 << (self.size - 1).bit_length()
		self.table = [self.ide_ele] * 2 * self.num
		self.index = [0] * 2 * self.num

		def function(a, b, k):
			if self.ls[k] == 1:
				res = self.table[k * 2 + 1]
			elif self.ls[k] == 0:
				res = self.table[k * 2 + 2]
			else:
				res = self.table[k * 2 + 1] + self.table[k * 2 + 2]
			return res
		self.func = function
		if not hasattr(init_val, '__iter__'):
			init_val = [init_val] * self.size
		for (i, val) in enumerate(init_val):
			self.table[i + self.num - 1] = val
			self.index[i + self.num - 1] = i
		for i in range(self.num - 2, -1, -1):
			self.table[i] = self.func(self.table[2 * i + 1], self.table[2 * i + 2], i)
			if self.table[i] == self.table[i * 2 + 1]:
				self.index[i] = self.index[i * 2 + 1]
			else:
				self.index[i] = self.index[i * 2 + 2]

	def build(self):
		for i in range(self.num - 2, -1, -1):
			self.table[i] = self.func(self.table[2 * i + 1], self.table[2 * i + 2], i)
			if self.table[i] == self.table[i * 2 + 1]:
				self.index[i] = self.index[i * 2 + 1]
			else:
				self.index[i] = self.index[i * 2 + 2]

	def update(self, k, x):
		self.ls[k] = x
		while k > -1:
			res = self.func(self.table[k * 2 + 1], self.table[k * 2 + 2], k)
			self.table[k] = res
			k = (k - 1) // 2

	def query(self):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = self.func(res, self.table[p])
			if q & 1 == 1:
				res = self.func(res, self.table[q])
				q -= 1
			p = p >> 1
			q = q - 1 >> 1
		if p == q:
			res = self.func(res, self.table[p])
		else:
			res = self.func(self.func(res, self.table[p]), self.table[q])
		return res

	def __str__(self):
		rt = self.table[self.num - 1:self.num - 1 + self.size]
		return str(rt)
n = int(input())
dc = dict(zip('01?', [0, 1, 2]))
s = [dc[i] for i in input()][::-1]
sg = SegTree(2 ** n, s)
y = 2 ** n - 1
for i in range(int(input())):
	(x, c) = input().split()
	x = int(x) - 1
	c = dc[c]
	sg.update(y - x - 1, c)
	ans = sg.table[0]
	print(ans)


import sys
input = sys.stdin.readline

def conv(p):
	return (1 << k) - p
k = int(input())
s = [0] + [i for i in input().strip()[::-1]]
can_win = [0] * len(s)
st = [1]
vis = [0] * len(s)
while st:
	c = st[-1]
	if not vis[c]:
		vis[c] = 1
		if 2 * c + 1 < len(s):
			st.append(2 * c)
			st.append(2 * c + 1)
	else:
		if 2 * c + 1 >= len(s):
			can_win[c] = 1 + (s[c] == '?')
		elif s[c] == '?':
			can_win[c] = can_win[2 * c] + can_win[2 * c + 1]
		else:
			can_win[c] = can_win[2 * c + (s[c] == '0')]
		st.pop()
q = int(input())
for i in range(q):
	a = input().split()
	p = conv(int(a[0]))
	c = a[1]
	s[p] = c
	c = p
	while c:
		if 2 * c + 1 >= len(s):
			can_win[c] = 1 + (s[c] == '?')
		elif s[c] == '?':
			can_win[c] = can_win[2 * c] + can_win[2 * c + 1]
		else:
			can_win[c] = can_win[2 * c + (s[c] == '0')]
		c >>= 1
	print(can_win[1])


import sys
input = sys.stdin.readline

def solve(s: str) -> int:
	n = len(s)
	dp = [-1] * n
	for idx in range(n - 1, -1, -1):
		if idx * 2 + 1 >= n:
			dp[idx] = 2 if s[idx] == '?' else 1
		elif s[idx] == '?':
			dp[idx] = dp[idx * 2] + dp[idx * 2 + 1]
		elif s[idx] == '0':
			dp[idx] = dp[idx * 2 + 1]
		else:
			dp[idx] = dp[idx * 2]
	return dp
input()
s = ' ' + input().rstrip()[::-1]
dp = solve(s)
s = list(s)
q = []
for _ in range(int(input())):
	q.append(input().rstrip().split())
for (idx, c) in q:
	idx = len(s) - int(idx)
	s[idx] = c
	while idx:
		if idx * 2 + 1 >= len(s):
			if s[idx] == '?':
				dp[idx] = 2
			else:
				dp[idx] = 1
		elif s[idx] == '?':
			dp[idx] = dp[idx * 2] + dp[idx * 2 + 1]
		elif s[idx] == '0':
			dp[idx] = dp[idx * 2 + 1]
		else:
			dp[idx] = dp[idx * 2]
		idx //= 2
	print(dp[1])


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7

def build():
	for i in range(p - 1, -1, -1):
		if i >= p - q:
			tr[i] = 1 if s[i] != '?' else 2
		else:
			tr[i] = tr[i * 2 + 1] if s[i] == '1' else tr[i * 2 + 2] if s[i] == '0' else tr[i * 2 + 1] + tr[i * 2 + 2]

def update(i, c):
	s[i] = c
	while i != -1:
		if i >= p - q:
			tr[i] = 1 if s[i] != '?' else 2
		else:
			tr[i] = tr[i] = tr[i * 2 + 1] if s[i] == '1' else tr[i * 2 + 2] if s[i] == '0' else tr[i * 2 + 1] + tr[i * 2 + 2]
		i = pr[i]
n = I()
s = list(S()[::-1])
p = 2 ** n - 1
q = 2 ** n // 2
tr = [0] * p
pr = [-1] * p
stk = [0]
while stk:
	g = stk.pop()
	if g < p - q:
		pr[g * 2 + 1] = g
		pr[g * 2 + 2] = g
		stk += (g * 2 + 1,)
		stk += (g * 2 + 2,)
build()
for i in range(I()):
	(ind, c) = S().split()
	ind = int(ind)
	update(p - ind, c)
	print(tr[0])


import sys
import math
input = sys.stdin.readline
imp = 'IMPOSSIBLE'
k = int(input())
s = input()[:-1]
n = len(s)
g = {}
le_old = 1
ind = 0
for i in range(n):
	le = k - math.floor(math.log2(2 ** k - 1 - i))
	if le == le_old:
		ind += 1
	else:
		ind = 1
	le_old = le
	if le == 1:
		if s[i] == '?':
			g[i + 1] = 2
		else:
			g[i + 1] = 1
	else:
		ind2 = i - ind - 2 ** (k - le + 1) + (ind - 1) * 2 + 1
		if s[i] == '?':
			g[i + 1] = g[ind2 + 1] + g[ind2 + 2]
		elif s[i] == '0':
			g[i + 1] = g[ind2 + 1]
		else:
			g[i + 1] = g[ind2 + 2]
q = int(input())
s = [s[i] for i in range(n)]
for i in range(q):
	(p, c) = input()[:-1].split(' ')
	p = int(p)
	odohrane = 0
	s[p - 1] = c
	for le in range(1, k + 1):
		odohrane = odohrane + 2 ** (k - le)
		if odohrane < p:
			continue
		else:
			ind = p - odohrane + 2 ** (k - le)
			if le == 1:
				if c == '?':
					g[p] = 2
				else:
					g[p] = 1
			else:
				ind2 = p - ind - 2 ** (k - le + 1) + (ind - 1) * 2
				g1 = g[ind2 + 1]
				g2 = g[ind2 + 2]
				if s[p - 1] == '?':
					g[p] = g1 + g2
				elif s[p - 1] == '0':
					g[p] = g1
				else:
					g[p] = g2
			p = odohrane + math.ceil(ind / 2)
	print(g[2 ** k - 1])


import sys
input = sys.stdin.readline

class segtree:
	global s

	def __init__(self, init_val, segfunc, k):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = 0
		self.k2 = 2 ** k
		self.k3 = 2 ** (k - 1)
		self.num = self.k2
		self.tree = [0] * self.num

	def update(self, k, x):
		self.tree[k] = x
		if k < self.k3:
			t = s[self.k2 - k - 1]
			if t == '?':
				self.tree[k] = self.tree[k * 2] + self.tree[k * 2 ^ 1]
			elif t == '1':
				self.tree[k] = self.tree[min(k * 2, k * 2 ^ 1)]
			else:
				self.tree[k] = self.tree[max(k * 2, k * 2 ^ 1)]
		while k > 1:
			t = s[self.k2 - (k >> 1) - 1]
			if t == '?':
				self.tree[k >> 1] = self.tree[k] + self.tree[k ^ 1]
			elif t == '1':
				self.tree[k >> 1] = self.tree[min(k, k ^ 1)]
			else:
				self.tree[k >> 1] = self.tree[max(k, k ^ 1)]
			k >>= 1

	def get(self, k):
		return self.tree[k]

	def deb(self):
		return self.tree

def segf(x, y):
	return x + y
k = int(input())
s = list(input())
q = int(input())
num2 = 2 ** (k - 1)
n = 2 ** k
seg = segtree([0] * 2 ** k, segf, k)
for i in range(num2):
	if s[i] == '?':
		seg.update(n - i - 1, 2)
	else:
		seg.update(n - i - 1, 1)
for i in range(q):
	(p, c) = input().split()
	p = int(p)
	s[p - 1] = c
	if p <= num2:
		if c == '?':
			seg.update(n - p, 2)
		else:
			seg.update(n - p, 1)
	seg.update(n - p, seg.get(n - p))
	print(seg.get(1))


import sys
input = sys.stdin.readline

def I():
	return input().strip()

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import copy, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, combinations, groupby
from operator import itemgetter
n = II()
if n == 1:
	s = I()
	q = II()
	for _ in range(q):
		inp = input().strip().split()
		b = inp[1]
		if b == '?':
			print(2)
		else:
			print(1)
	sys.exit()
s = I()
s = s[::-1]
s = list(s)
size = len(s)
dp = [0] * size
for i in range(size - 1, size - 1 - (size + 1) // 2, -1):
	if s[i] == '0' or s[i] == '1':
		dp[i] = 1
	if s[i] == '?':
		dp[i] = 2
for i in range(size - 1, 0, -2):
	if s[i // 2 - 1] == '0':
		dp[i // 2 - 1] = dp[i]
	if s[i // 2 - 1] == '1':
		dp[i // 2 - 1] = dp[i - 1]
	if s[i // 2 - 1] == '?':
		dp[i // 2 - 1] = dp[i] + dp[i - 1]
q = II()
for _ in range(q):
	inp = input().strip().split()
	a = size - 1 - (int(inp[0]) - 1)
	b = inp[1]
	s[a] = b
	while True:
		if a == 0:
			if b == '0':
				dp[a] = dp[2 * a + 2]
			if b == '1':
				dp[a] = dp[2 * a + 1]
			if b == '?':
				dp[a] = dp[2 * a + 1] + dp[2 * a + 2]
			break
		if a >= pow(2, n - 1) - 1:
			if b == '1' or b == '0':
				dp[a] = 1
			if b == '?':
				dp[a] = 2
			a = (a - 1) // 2
			b = s[a]
		else:
			if b == '0':
				dp[a] = dp[2 * a + 2]
			if b == '1':
				dp[a] = dp[2 * a + 1]
			if b == '?':
				dp[a] = dp[2 * a + 1] + dp[2 * a + 2]
			a = (a - 1) // 2
			b = s[a]
	print(dp[0])


from __future__ import print_function
from sys import stdin
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(k,) = gil()
n = 1 << k
state = gcl()
state.append('*')
state.reverse()
ans = [1] * n
fin = []

def update(gIdx):
	while gIdx:
		d = gIdx * 2
		if gIdx * 2 < n:
			(l, r) = (ans[d], ans[d + 1])
			if state[gIdx] == '?':
				ans[gIdx] = l + r
			else:
				ans[gIdx] = l if state[gIdx] == '1' else r
		else:
			ans[gIdx] = 2 if state[gIdx] == '?' else 1
		gIdx //= 2
for gIdx in reversed(range(1, n)):
	d = gIdx * 2
	if gIdx * 2 < n:
		(l, r) = (ans[d], ans[d + 1])
		if state[gIdx] == '?':
			ans[gIdx] = l + r
		else:
			ans[gIdx] = l if state[gIdx] == '1' else r
	else:
		ans[gIdx] = 2 if state[gIdx] == '?' else 1
(q,) = gil()
for _ in range(q):
	l = gl()
	gIdx = n - int(l[0])
	newState = l[1]
	if state[gIdx] != newState:
		state[gIdx] = newState
		update(gIdx)
	fin.append(str(ans[1]))
print('\n'.join(fin))


import sys
input = sys.stdin.readline

def build(curr):
	l = curr << 1
	r = (curr << 1) + 1
	if tree[l] == -1:
		build(l)
	if tree[r] == -1:
		build(r)
	if s[curr - 1] == '0':
		tree[curr] = tree[r]
	elif s[curr - 1] == '1':
		tree[curr] = tree[l]
	else:
		tree[curr] = tree[l] + tree[r]
k = int(input())
s = list(input().strip())
s.reverse()
n = len(s)
tree = [-1] * (2 * (n + 1) + 2)
for i in range(n + 1):
	tree[n + i + 1] = 1
build(1)
q = int(input())
for i in range(q):
	inp = input().split()
	ind = int(inp[0])
	val = inp[1]
	s[n - ind] = val
	curr = n - ind + 1
	while curr > 0:
		l = curr << 1
		r = (curr << 1) + 1
		if s[curr - 1] == '?':
			tree[curr] = tree[l] + tree[r]
		elif s[curr - 1] == '1':
			tree[curr] = tree[l]
		else:
			tree[curr] = tree[r]
		curr >>= 1
	print(tree[1])


from io import BytesIO, IOBase
import sys
import math
import os
import heapq
from collections import defaultdict, deque
from math import ceil
from bisect import bisect_left, bisect_left
from time import perf_counter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def mint():
	return map(int, input().split())

def mfloat():
	return map(float, input().split())

def intin():
	return int(input())

class Node:

	def __init__(self, a, no):
		self.possible = a
		self.child = None
		self.parent1 = self.parent2 = None
		self.no = no

	def __str__(self):
		return f'{self.possible} winners possible till here, no = {self.no}'

def decrease(a, idx, c, s):
	r = len(a[1])
	level = 1
	while idx > r:
		level += 1
		idx -= r
		r //= 2
	idx -= 1
	current_node = a[level][idx]
	s[current_node.no] = c
	while current_node is not None:
		if s[current_node.no] == '?':
			current_node.possible = current_node.parent1.possible + current_node.parent2.possible
		elif s[current_node.no] == '1':
			current_node.possible = current_node.parent2.possible
		else:
			current_node.possible = current_node.parent1.possible
		ans = current_node.possible
		current_node = current_node.child
	return ans

def solve():
	n = int(input())
	s = list(input())
	a = []
	for i in range(-1, n):
		a.append([0] * (1 << n - 1 - i))
	for i in range(1 << n):
		a[0][i] = Node(1, -1)
	pointer = 0
	for level in range(1, n + 1):
		for j in range(1 << n - level):
			parent_1 = a[level - 1][2 * j]
			parent_2 = a[level - 1][2 * j + 1]
			if s[pointer] == '?':
				a[level][j] = Node(parent_2.possible + parent_1.possible, pointer)
			elif s[pointer] == '1':
				a[level][j] = Node(parent_2.possible, pointer)
			else:
				a[level][j] = Node(parent_1.possible, pointer)
			a[level][j].parent1 = parent_1
			a[level][j].parent2 = parent_2
			parent_1.child = a[level][j]
			parent_2.child = a[level][j]
			pointer += 1
	q = int(input())
	for _ in range(q):
		(idx, c) = input().split()
		print(decrease(a, int(idx), c, s))

def main():
	t = 1
	for _ in range(t):
		solve()
start_time = perf_counter()
main()
print(perf_counter() - start_time, file=sys.stderr)


from itertools import product
import itertools
import sys
import math
import heapq
from collections import deque
MOD = 1000000000007

def find(parent, i):
	if parent[i] != i:
		parent[i] = find(parent, parent[i])
	return parent[i]

def union(parent, rank, xx, yy):
	x = find(parent, xx)
	y = find(parent, yy)
	if rank[x] > rank[y]:
		parent[y] = x
	elif rank[y] > rank[x]:
		parent[x] = y
	else:
		parent[y] = x
		rank[x] += 1
ans = 0
K = int(sys.stdin.readline().strip())
ol = list(sys.stdin.readline().strip())
k = 2 ** K
l = [1 for i in range(k * 2)]
for i in range(k - 1):
	j = k - 1 - i
	if ol[i] == '?':
		l[j] = l[j * 2] + l[j * 2 + 1]
	elif ol[i] == '0':
		l[j] = l[j * 2 + 1]
	else:
		l[j] = l[j * 2]
Q = int(sys.stdin.readline().strip())
for i in range(Q):
	(p, c) = sys.stdin.readline().strip().split()
	p = int(p)
	j = k - p
	ol[p - 1] = c
	while j > 0:
		if ol[p - 1] == '?':
			l[j] = l[j * 2] + l[j * 2 + 1]
		elif ol[p - 1] == '0':
			l[j] = l[j * 2 + 1]
		else:
			l[j] = l[j * 2]
		j = j // 2
		p = k - j
	print(l[1])


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
inf = 10 ** 16
md = 10 ** 9 + 7
k = II()
n = 1 << k
s = SI()
vv = [2] * n
tt = [2] * n
for (i, c) in enumerate(s, 1):
	i = n - i
	if c == '?':
		tt[i] = 2
		if i >= n // 2:
			vv[i] = 2
		else:
			vv[i] = vv[i * 2] + vv[i * 2 + 1]
	else:
		tt[i] = int(c)
		if i >= n // 2:
			vv[i] = 1
		else:
			vv[i] = vv[i * 2 + 1 - int(c)]
for _ in range(II()):
	(p, c) = SI().split()
	p = n - int(p)
	if c == '?':
		tt[p] = 2
	else:
		tt[p] = int(c)
	while p:
		if p >= n // 2:
			if tt[p] == 2:
				vv[p] = 2
			else:
				vv[p] = 1
		elif tt[p] == 2:
			vv[p] = vv[p * 2] + vv[p * 2 + 1]
		else:
			vv[p] = vv[p * 2 + 1 - tt[p]]
		p //= 2
	print(vv[1])


import os
import sys
import math
import collections
import functools
import itertools
import heapq
import bisect
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcde'
M = 10 ** 9 + 7
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def INT():
	return int(input())

def STR():
	return input()

def INTs():
	return tuple(map(int, input().split()))

def ARRINT():
	return [int(i) for i in input().split()]

def ARRSTR():
	return [i for i in input().split()]
k = INT()
n = 2 ** k - 1
s = list(STR())
s = s[::-1]
SegmentTree = [0] * n
for i in range(n - 1, -1, -1):
	if 2 * i + 1 >= n:
		if s[i] == '?':
			SegmentTree[i] = 2
		else:
			SegmentTree[i] = 1
	else:
		if s[i] == '1' or s[i] == '?':
			SegmentTree[i] += SegmentTree[2 * i + 1]
		if s[i] == '0' or s[i] == '?':
			SegmentTree[i] += SegmentTree[2 * i + 2]
for _ in range(INT()):
	(p, c) = ARRSTR()
	p = n - int(p)
	s[p] = c
	while True:
		SegmentTree[p] = 0
		if 2 * p + 1 >= 2 ** k - 1:
			if s[p] == '?':
				SegmentTree[p] = 2
			else:
				SegmentTree[p] = 1
		else:
			if s[p] == '1' or s[p] == '?':
				SegmentTree[p] += SegmentTree[2 * p + 1]
			if s[p] == '0' or s[p] == '?':
				SegmentTree[p] += SegmentTree[2 * p + 2]
		if p == 0:
			break
		p = (p - 1) // 2
	print(SegmentTree[0])


import sys
input = lambda : sys.stdin.readline().strip()
k = int(input())
S = list(input())
N = len(S)
dp = [0] * N
for (i, s) in enumerate(S):
	if i <= N // 2:
		dp[i] += 2 if s == '?' else 1
	else:
		d = N - i
		(l, r) = (N - d * 2 - 1, N - d * 2)
		if s == '?':
			dp[i] = dp[l] + dp[r]
		elif s == '1':
			dp[i] = dp[r]
		elif s == '0':
			dp[i] = dp[l]
for _ in range(int(input())):
	(i, to) = input().split()
	i = int(i) - 1
	S[i] = to
	while i < N:
		s = S[i]
		d = N - i
		(l, r) = (N - d * 2 - 1, N - d * 2)
		if i <= N // 2:
			dp[i] = 2 if s == '?' else 1
		elif s == '?':
			dp[i] = dp[l] + dp[r]
		elif s == '1':
			dp[i] = dp[r]
		elif s == '0':
			dp[i] = dp[l]
		d = (N - i) // 2
		i = N - d
	print(dp[-1])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
k = int(input())
s = input()
s = s[-1::-1]
n = 2 ** k - 1
arr = [None] + [i for i in s]

class node:

	def __init__(self, val):
		self.val = val
		self.low = None
		self.high = None
		self.ans = 0
		self.parent = 0
for i in range(1, n + 1):
	arr[i] = node(arr[i])
for i in range(1, n + 1):
	if 2 * i < n + 1:
		arr[i].low = arr[2 * i]
		arr[2 * i].parent = arr[i]
	if 2 * i < n:
		arr[i].high = arr[2 * i + 1]
		arr[2 * i + 1].parent = arr[i]

def solve(node):
	if node == None:
		return 1
	if node.val == '?':
		node.ans = solve(node.low) + solve(node.high)
	elif node.val == '1':
		node.ans = solve(node.low)
		solve(node.high)
	else:
		node.ans = solve(node.high)
		solve(node.low)
	return node.ans
solve(arr[1])

def update(index, a):
	index = n + 1 - index
	arr[index].val = a
	currnode = arr[index]
	if currnode.val == '?':
		if currnode.high != None and currnode.low != None:
			currnode.ans = currnode.low.ans + currnode.high.ans
		else:
			currnode.ans = 2
	elif currnode.val == '1' and currnode.low != None:
		currnode.ans = currnode.low.ans
	elif currnode.val == '0' and currnode.high != None:
		currnode.ans = currnode.high.ans
	else:
		currnode.ans = 1
	while currnode.parent != 0:
		currnode = currnode.parent
		if currnode.val == '?':
			currnode.ans = currnode.low.ans + currnode.high.ans
		elif currnode.val == '1':
			currnode.ans = currnode.low.ans
		else:
			currnode.ans = currnode.high.ans
q = int(input())
for i in range(q):
	(index, a) = input().split()
	update(int(index), a)
	sys.stdout.write(str(arr[1].ans) + '\n')


import math, heapq
from collections import deque, defaultdict
import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	s = list(input())
	s.reverse()
	val = pow(2, n)
	segT = [[1, 1] for i in range(val)]
	ind = 0
	for i in range(val // 2 - 1, 0, -1):
		if s[2 * i] == '?':
			segT[i][0] = sum(segT[2 * i + 1])
		elif s[2 * i] == '0':
			segT[i][0] = segT[2 * i + 1][0]
		else:
			segT[i][0] = segT[2 * i + 1][1]
		if s[2 * i - 1] == '?':
			segT[i][1] = sum(segT[2 * i])
		elif s[2 * i - 1] == '0':
			segT[i][1] = segT[2 * i][0]
		else:
			segT[i][1] = segT[2 * i][1]
	q = int(input())
	for i in range(q):
		(ind, c) = input().split()
		ind = int(ind)
		i = (val - ind) // 2
		s[val - ind - 1] = c
		while i != 0:
			if s[2 * i] == '?':
				segT[i][0] = sum(segT[2 * i + 1])
			elif s[2 * i] == '0':
				segT[i][0] = segT[2 * i + 1][0]
			else:
				segT[i][0] = segT[2 * i + 1][1]
			if s[2 * i - 1] == '?':
				segT[i][1] = sum(segT[2 * i])
			elif s[2 * i - 1] == '0':
				segT[i][1] = segT[2 * i][0]
			else:
				segT[i][1] = segT[2 * i][1]
			i = i // 2
		if s[0] == '1':
			print(segT[1][1])
		elif s[0] == '0':
			print(segT[1][0])
		else:
			print(sum(segT[1]))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	k = ii()
	s = list(si())
	n = len(s)
	p = [0] * n
	idx = [0] * (2 * n)
	idx[1] = n - 1
	ans = [0] * n
	for i in range(n - 2, -1, -1):
		x = n - i
		p[i] = idx[x // 2]
		idx[x] = i
	for i in range(pow(2, k - 1)):
		if s[i] == '?':
			ans[i] = 2
		else:
			ans[i] = 1
	lft = [-1] * n
	right = [0] * n
	for i in range(n - 1):
		if lft[p[i]] != -1:
			right[p[i]] = i
		else:
			lft[p[i]] = i
	res = 0
	for i in range(pow(2, k - 1), n):
		if s[i] == '?':
			ans[i] = ans[lft[i]] + ans[right[i]]
		elif s[i] == '1':
			ans[i] = ans[right[i]]
		else:
			ans[i] = ans[lft[i]]
	q = ii()
	for i in range(q):
		(a, c) = map(str, input().split())
		a = int(a)
		a -= 1
		s[a] = c
		if a < pow(2, k - 1):
			if s[a] == '?':
				ans[a] = 2
			else:
				ans[a] = 1
			a = p[a]
		while a:
			if s[a] == '?':
				ans[a] = ans[lft[a]] + ans[right[a]]
			elif s[a] == '1':
				ans[a] = ans[right[a]]
			else:
				ans[a] = ans[lft[a]]
			a = p[a]
		print(ans[-1])
if file:
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


def solve():
	k = int(input())
	s = list(input())
	q = int(input())
	queries = [tuple(input().split()) for _ in range(q)]
	lim = 2 ** k
	seg = [1] * lim
	seg[0] = 0
	for i in range(lim // 2):
		if s[i] == '?':
			seg[lim - i - 1] = 2
	for i in range(lim // 2, lim - 1):
		j = lim - i - 1
		if s[i] == '?':
			seg[j] = seg[j * 2] + seg[j * 2 + 1]
		elif s[i] == '1':
			seg[j] = seg[j * 2]
		else:
			seg[j] = seg[j * 2 + 1]
	for (p, c) in queries:
		s[int(p) - 1] = c
		j = lim - int(p)
		if 2 * j + 1 < lim:
			if c == '?':
				seg[j] = seg[j * 2] + seg[j * 2 + 1]
			elif c == '1':
				seg[j] = seg[j * 2]
			else:
				seg[j] = seg[j * 2 + 1]
		elif c == '?':
			seg[j] = 2
		else:
			seg[j] = 1
		while j // 2 > 0:
			j = j // 2
			i = lim - j - 1
			if s[i] == '?':
				seg[j] = seg[j * 2] + seg[j * 2 + 1]
			elif s[i] == '1':
				seg[j] = seg[j * 2]
			else:
				seg[j] = seg[j * 2 + 1]
		print(seg[1])
solve()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def A2(n, m):
	return [[0] * m for i in range(n)]

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def popcnt(x):
	ans = 0
	while x:
		ans += 1
		x &= x - 1
	return ans

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

class UF:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n
		self.size = AI(n, 1)
		self.edge = A(n)

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			self.edge[pu] += 1
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			self.edge[pu] += self.edge[pv] + 1
			self.size[pu] += self.size[pv]
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv
			self.edge[pv] += self.edge[pu] + 1
			self.size[pv] += self.size[pu]

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = AI(n, inf)
	d[s] = 0
	heap = [(0, s)]
	vis = A(n)
	while heap:
		(dis, u) = heappop(heap)
		if vis[u]:
			continue
		vis[u] = 1
		for (v, w) in graph[u]:
			if d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

def michange(a, b):
	d = defaultdict(deque)
	for (i, x) in enumerate(b):
		d[x].append(i)
	order = A(len(a))
	for (i, x) in enumerate(a):
		if not d:
			return -1
		order[i] = d[x].popleft()
	return RP(order)

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None

class SMT:

	def __init__(self, size, qf):
		n = 1
		while n < size:
			n <<= 1
		self.size = n
		self.node = [1] * (2 * n)
		self.qf = qf

	def q(self, k):
		if self.qf[k] == '?':
			return self.node[k * 2] + self.node[k * 2 + 1]
		if self.qf[k] == '0':
			return self.node[k * 2]
		return self.node[k * 2 + 1]

	def get(self, k):
		return self.node[k + self.size]

	def build(self):
		for k in range(self.size - 1, 0, -1):
			self.node[k] = self.q(k)

	def update(self, k, x):
		self.qf[k] = x
		while k >= 1:
			self.node[k] = self.q(k)
			k >>= 1

	def query(self, l, r):
		vl = vr = self.I
		l += self.size
		r += self.size
		while l < r:
			if l & 1:
				vl = self.op(vl, self.node[l])
				l += 1
			if r & 1:
				r -= 1
				vr = self.op(self.node[r], vr)
			l >>= 1
			r >>= 1
		return self.op(vl, vr)
t = 1
for i in range(t):
	k = N()
	s = input()
	qf = [0] * (1 << k)
	cur = 0
	d = [0] * (1 << k)
	for i in range(k - 1, -1, -1):
		for j in range(1 << i):
			ind = cur + j
			d[ind] = (1 << i) + j
			qf[d[ind]] = s[ind]
		cur += 1 << i
	smt = SMT(1 << k, qf)
	smt.build()
	q = N()
	for i in range(q):
		(ind, ch) = input().split()
		cur = d[int(ind) - 1]
		smt.update(cur, ch)
		print(smt.node[1])


import sys
input = lambda : sys.stdin.readline().rstrip()
K = int(input())
S = list(input())
G = 2 ** K - 1
W = [2 if c == '?' else 1 for c in S[:2 ** (K - 1)]]
W += [0] * (G - len(W))
start = 0
for k in range(K - 2, -1, -1):
	nstart = start + 2 ** (k + 1)
	for i in range(2 ** k):
		a = W[start + 2 * i]
		b = W[start + 2 * i + 1]
		p = nstart + i
		c = S[p]
		if c in '0?':
			W[p] += a
		if c in '1?':
			W[p] += b
	start = nstart
O = []
for _ in range(int(input())):
	(ps, c) = input().split()
	p = int(ps) - 1
	S[p] = c
	nstart = 0
	for k in range(K - 1, -1, -1):
		games = 2 ** k
		if p < games:
			if k == K - 1:
				W[p] = 2 if S[p] == '?' else 1
			else:
				a = W[start + 2 * p]
				b = W[start + 2 * p + 1]
				W[nstart + p] = 0
				c = S[nstart + p]
				if c in '0?':
					W[nstart + p] += a
				if c in '1?':
					W[nstart + p] += b
			p //= 2
		else:
			p -= games
		start = nstart
		nstart += games
	O.append(W[-1])
print('\n'.join(map(str, O)))


import sys
import math

class SegmentTree:

	def __init__(self, arr):
		self.STarr = []
		length = 1
		while len(arr) > length:
			length *= 2
		self.length = length

	def init(self, arr, ll):
		self.STarr = [0] * self.length * 2
		for i in range(len(arr)):
			self.STarr[self.length + i] = arr[i]
		for i in range(self.length - 1, 0, -1):
			if ll[i] == '?':
				self.STarr[i] = self.STarr[2 * i] + self.STarr[2 * i + 1]
			elif ll[i] == '0':
				self.STarr[i] = self.STarr[2 * i]
			else:
				self.STarr[i] = self.STarr[2 * i + 1]

	def change(self, i, ll):
		while i > 0:
			if ll[i] == '?':
				self.STarr[i] = self.STarr[2 * i] + self.STarr[2 * i + 1]
			elif ll[i] == '0':
				self.STarr[i] = self.STarr[2 * i]
			else:
				self.STarr[i] = self.STarr[2 * i + 1]
			i = i // 2

	def intervalCalc(self, idxStart, idxEnd):
		a = self.length + idxStart
		b = self.length + idxEnd + 1
		(sml, smr) = (0, 0)
		while a < b:
			if a & 1 == 1:
				sml += self.STarr[a]
				a += 1
			if b & 1 == 1:
				smr += self.STarr[b - 1]
				b -= 1
			a = a // 2
			b = b // 2
		return sml + smr

	def print(self):
		print(self.STarr[1])
inp = int(sys.stdin.readline())
l = sys.stdin.readline().strip()
ll = [0] * 2 ** inp
for i in range(1, 2 ** inp):
	if l[2 ** inp - i - 1] == '0':
		ll[i] = '1'
	elif l[2 ** inp - i - 1] == '1':
		ll[i] = '0'
	else:
		ll[i] = l[2 ** inp - i - 1]
ST = SegmentTree([1] * 2 ** inp)
ST.init([1] * 2 ** inp, ll)
for _ in range(int(sys.stdin.readline())):
	(a, b) = sys.stdin.readline().strip().split()
	a = int(a)
	if b == '1':
		b = '0'
	elif b == '0':
		b = '1'
	ll[2 ** inp - a] = b
	ST.change(2 ** inp - a, ll)
	ST.print()


import sys
input = sys.stdin.readline
n = int(input())
s = list(input())[::-1]
s = s[1:]
temp = [1 for i in range(2000000)]
for ind in range((1 << n) - 2, -1, -1):
	if s[ind] == '0':
		temp[ind] = temp[2 * ind + 2]
	elif s[ind] == '1':
		temp[ind] = temp[2 * ind + 1]
	else:
		temp[ind] = temp[2 * ind + 1] + temp[2 * ind + 2]
for _ in range(int(input())):
	(a, b) = [x for x in input().split()]
	a = int(a) - 1
	a = (1 << n) - 2 - a
	s[a] = b
	ind = a
	while ind >= 0:
		if s[ind] == '0':
			temp[ind] = temp[2 * ind + 2]
		elif s[ind] == '1':
			temp[ind] = temp[2 * ind + 1]
		else:
			temp[ind] = temp[2 * ind + 1] + temp[2 * ind + 2]
		if ind == 0:
			break
		ind = (ind - 1) // 2
	print(temp[0])


import sys
n = int(sys.stdin.readline())
string = list(sys.stdin.readline().strip())
arr = list(reversed(string))
length = len(arr)
ans_arr = [1 for item in range(2 * (length + 1) + 1)]
for i in range(length - 1, -1, -1):
	pos = i + 1
	if arr[i] == '0':
		ans_arr[pos] = ans_arr[2 * pos + 1]
	elif arr[i] == '1':
		ans_arr[pos] = ans_arr[2 * pos]
	else:
		ans_arr[pos] = ans_arr[2 * pos] + ans_arr[2 * pos + 1]
q = int(input())
for j in range(q):
	(change_index, value) = map(str, sys.stdin.readline().split())
	v_index = len(string) - int(change_index)
	arr[v_index] = value
	while v_index + 1 > 0:
		if arr[v_index] == '0':
			ans_arr[v_index + 1] = ans_arr[2 * (v_index + 1) + 1]
		elif arr[v_index] == '1':
			ans_arr[v_index + 1] = ans_arr[2 * (v_index + 1)]
		else:
			ans_arr[v_index + 1] = ans_arr[2 * (v_index + 1)] + ans_arr[2 * (v_index + 1) + 1]
		v_index = (v_index - 1) // 2
	print(ans_arr[1])


import sys
import io, os
input = sys.stdin.readline
k = int(input())
s = list(str(input().rstrip()))
s.reverse()
n = 1 << k
C = [1] * (2 * n)

def update(i):
	if s[i] == '0':
		C[i] = C[2 * i + 2]
	elif s[i] == '1':
		C[i] = C[2 * i + 1]
	else:
		C[i] = C[2 * i + 1] + C[2 * i + 2]
for i in range(n - 2, -1, -1):
	update(i)
q = int(input())
for i in range(q):
	(p, c) = map(str, input().split())
	p = int(p)
	p = n - 1 - p
	s[p] = c
	while p:
		update(p)
		p = (p - 1) // 2
	update(0)
	print(C[0])


from sys import stdout, stdin, setrecursionlimit
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
k = getInt()
s = listStr()
s.reverse()
n = 1 << k
C = [1] * (2 * n)

def update(i):
	if s[i] == '0':
		C[i] = C[2 * i + 2]
	elif s[i] == '1':
		C[i] = C[2 * i + 1]
	else:
		C[i] = C[2 * i + 1] + C[2 * i + 2]
for i in range(n - 2, -1, -1):
	update(i)
q = int(input())
for i in range(q):
	(p, c) = map(str, input().split())
	p = int(p)
	p = n - 1 - p
	s[p] = c
	while p:
		update(p)
		p = (p - 1) // 2
	update(0)
	print(C[0])


import sys, os, io
from math import gcd
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def build(curr):
	l = curr << 1
	r = (curr << 1) + 1
	if tree[l] == -1:
		build(l)
	if tree[r] == -1:
		build(r)
	if s[curr - 1] == '0':
		tree[curr] = tree[r]
	elif s[curr - 1] == '1':
		tree[curr] = tree[l]
	else:
		tree[curr] = tree[l] + tree[r]
k = int(input())
s = list(input().strip())
s.reverse()
n = len(s)
tree = [-1] * (2 * (n + 1) + 2)
for i in range(n + 1):
	tree[n + i + 1] = 1
build(1)
q = int(input())
for i in range(q):
	inp = input().split()
	ind = int(inp[0])
	val = inp[1]
	s[n - ind] = val
	curr = n - ind + 1
	while curr > 0:
		l = curr << 1
		r = (curr << 1) + 1
		if s[curr - 1] == '?':
			tree[curr] = tree[l] + tree[r]
		elif s[curr - 1] == '1':
			tree[curr] = tree[l]
		else:
			tree[curr] = tree[r]
		curr >>= 1
	print(tree[1])


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	k = int(input())
	s = list('-' + input()[::-1])
	cnt = [0] * len(s)
	for i in range(len(s) // 2, len(s)):
		cnt[i] = 2 if s[i] == '?' else 1
	for i in range(len(s) // 2, len(s)):
		i >>= 1
		while i:
			if s[i] == '?':
				cnt[i] = cnt[i * 2] + cnt[i * 2 + 1]
			elif s[i] == '1':
				cnt[i] = cnt[i * 2]
			else:
				cnt[i] = cnt[i * 2 + 1]
			i >>= 1
	q = int(input())
	for _ in range(q):
		(p, c) = input().split()
		p = len(s) - int(p)
		s[p] = c
		if p >= len(s) // 2:
			cnt[p] = 2 if s[p] == '?' else 1
			p >>= 1
		while p:
			if s[p] == '?':
				cnt[p] = cnt[p * 2] + cnt[p * 2 + 1]
			elif s[p] == '1':
				cnt[p] = cnt[p * 2]
			else:
				cnt[p] = cnt[p * 2 + 1]
			p >>= 1
		print(cnt[1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import defaultdict
import sys
input = sys.stdin.readline
k = int(input())
s = list(str(input()))
n = 2 ** k
tree = [0] * (2 ** (k + 1) - 1)
dictt = defaultdict(int)
dict2 = defaultdict(int)
val = n - 2
for i in range(1, k + 1):
	for ii in range(2 ** i - 2, 2 ** (i - 1) - 2, -1):
		dictt[val] = ii
		dict2[ii] = val
		val -= 1
for i in range(n - 1, len(tree)):
	tree[i] = 1
for i in range(len(s)):
	index = dictt[i]
	if s[i] == '1':
		tree[index] = tree[index * 2 + 2]
	elif s[i] == '0':
		tree[index] = tree[index * 2 + 1]
	else:
		tree[index] = tree[index * 2 + 1] + tree[index * 2 + 2]
for _ in range(int(input())):
	(p, c) = map(str, input().split())
	p = int(p)
	s[p - 1] = str(c)
	ind = dictt[p - 1]
	while 1:
		c = s[dict2[ind]]
		if c == '?':
			tree[ind] = tree[2 * ind + 1] + tree[2 * ind + 2]
		elif c == '0':
			tree[ind] = tree[2 * ind + 1]
		else:
			tree[ind] = tree[2 * ind + 2]
		if ind == 0:
			break
		ind -= 1
		ind //= 2
	print(tree[0])


import sys
input = sys.stdin.readline
k = int(input())
n = 1 << k
s = list(input()[:-1][::-1])
d = [1] * (n * 2)
for i in range(n - 2, -1, -1):
	if s[i] == '0':
		d[i] = d[i * 2 + 2]
	elif s[i] == '1':
		d[i] = d[i * 2 + 1]
	else:
		d[i] = d[i * 2 + 1] + d[i * 2 + 2]
q = int(input())
for _ in range(q):
	(a, c) = input().split()
	a = n - 1 - int(a)
	s[a] = c
	if c == '0':
		d[a] = d[a * 2 + 2]
	elif c == '1':
		d[a] = d[a * 2 + 1]
	else:
		d[a] = d[a * 2 + 1] + d[a * 2 + 2]
	while a > 0:
		a = (a - 1) // 2
		if s[a] == '0':
			d[a] = d[a * 2 + 2]
		elif s[a] == '1':
			d[a] = d[a * 2 + 1]
		else:
			d[a] = d[a * 2 + 1] + d[a * 2 + 2]
	print(d[0])


import io
import os
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop, heapify
from math import gcd, inf
DEBUG = False

def solve(K, S, Q, PC):
	assert 2 ** K - 1 == len(S)
	assert len(PC) == Q
	S = [-1] + ['01?'.index(x) for x in S[::-1]]
	data = [0] * len(S)

	def update(idx, c):
		S[idx] = c
		while idx:
			if idx * 2 + 1 > len(S):
				data[idx] = 2 if S[idx] == 2 else 1
			elif S[idx] == 2:
				data[idx] = data[2 * idx] + data[2 * idx + 1]
			else:
				data[idx] = data[2 * idx + S[idx] ^ 1]
			idx >>= 1
	for (i, x) in enumerate(S):
		if i != 0:
			update(i, x)
	ans = []
	for (p, c) in PC:
		p = int(p)
		c = '01?'.index(c)
		p = 2 ** K - p
		old = S[p]
		update(p, c)
		if DEBUG:
			print()
			print('query', p, c)
			print(S)
			print(data)
		ans.append(data[1])
	assert len(ans) == Q
	return '\n'.join(map(str, ans))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = 1
for tc in range(1, TC + 1):
	(K,) = [int(x) for x in input().split()]
	S = input().decode().rstrip()
	(Q,) = [int(x) for x in input().split()]
	PC = [input().decode().split() for i in range(Q)]
	ans = solve(K, S, Q, PC)
	print(ans)


import sys
input = sys.stdin.readline

def solution(k, res, q, queries):
	bij = [-1 for _ in range(2 ** k)]
	count = 1
	end = 2 ** k
	for p in range(0, k):
		beg = end - 2 ** p
		for orig in range(beg, end):
			bij[orig] = count
			count += 1
		end = beg
	winners = ['1' for _ in range(2 ** k)]
	for pos_them in range(1, 2 ** k):
		val = res[pos_them - 1]
		pos_moi = bij[pos_them]
		winners[pos_moi] = val
	nb_gagnants = [1 for _ in range(2 ** k)]
	for pos_me in range(2 ** k - 1, -1, -1):
		if pos_me >= 2 ** (k - 1):
			if winners[pos_me] == '?':
				nb_gagnants[pos_me] = 2
			else:
				nb_gagnants[pos_me] = 1
		elif winners[pos_me] == '?':
			nb_gagnants[pos_me] = nb_gagnants[2 * pos_me] + nb_gagnants[2 * pos_me + 1]
		elif winners[pos_me] == '1':
			nb_gagnants[pos_me] = nb_gagnants[2 * pos_me + 1]
		else:
			nb_gagnants[pos_me] = nb_gagnants[2 * pos_me]
	for [pos_them, elem] in queries:
		pos_them = int(pos_them)
		pos_me = bij[pos_them]
		winners[pos_me] = elem
		while pos_me > 0:
			if pos_me >= 2 ** (k - 1):
				if winners[pos_me] == '?':
					nb_gagnants[pos_me] = 2
				else:
					nb_gagnants[pos_me] = 1
			elif winners[pos_me] == '?':
				nb_gagnants[pos_me] = nb_gagnants[2 * pos_me] + nb_gagnants[2 * pos_me + 1]
			elif winners[pos_me] == '1':
				nb_gagnants[pos_me] = nb_gagnants[2 * pos_me + 1]
			else:
				nb_gagnants[pos_me] = nb_gagnants[2 * pos_me]
			pos_me = pos_me // 2
		print(nb_gagnants[1])
k = int(input())
res = input().strip()
q = int(input())
queries = []
for t in range(q):
	queries.append(input().split())
solution(k, res, q, queries)


import math, sys
from itertools import permutations
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
MOD = int(1000000000.0) + 7
INF = float('inf')

class SegTree:

	def __init__(self, k):
		self.n = 2 ** k
		self.size = self.n * 2 - 1
		self.arr = [0 for i in range(self.size)]

	def get(self):
		return self.arr[0]

	def update(self, j, val, decision, mapped_index1, mapped_index2):
		j = mapped_index2[j]
		while j >= 0:
			index = mapped_index1[j]
			if decision[index] == '1':
				self.arr[j] = self.arr[j * 2 + 2]
			elif decision[index] == '0':
				self.arr[j] = self.arr[j * 2 + 1]
			else:
				self.arr[j] = self.arr[j * 2 + 1] + self.arr[j * 2 + 2]
			j = (j - 1) // 2

	def __set(self, l, r, i, j, val, decision, mapped_index):
		if r - l == 1:
			self.arr[j] = 1
			return
		m = (l + r) // 2
		if i < m:
			self.__set(l, m, i, j * 2 + 1, val, decision, mapped_index)
		else:
			self.__set(m, r, i, j * 2 + 2, val, decision, mapped_index)
		index = mapped_index[j]
		if decision[index] == '1':
			self.arr[j] = self.arr[j * 2 + 2]
		elif decision[index] == '0':
			self.arr[j] = self.arr[j * 2 + 1]
		else:
			self.arr[j] = self.arr[j * 2 + 1] + self.arr[j * 2 + 2]

	def set(self, i, val, decision, mapped_index):
		self.__set(0, self.n, i, 0, val, decision, mapped_index)

def solve():
	k = int(input())
	s = list(input())
	mapped_index1 = [0 for i in range(len(s))]
	mapped_index2 = {}
	idx = 0
	(i, p) = (0, 1)
	while i < len(s):
		tmp = []
		stop = i + p
		add = p - 1
		while i < len(s) and i < stop:
			mapped_index1[i] = len(s) - (i + add) - 1
			add -= 2
			i += 1
		p *= 2
	st = SegTree(k)
	for i in range(2 ** k):
		st.set(i, 1, s, mapped_index1)
	for i in range(len(mapped_index1)):
		mapped_index2[mapped_index1[i]] = i
	q = int(input())
	for _ in range(q):
		(j, val) = input().split()
		j = int(j) - 1
		s[j] = val
		st.update(j, val, s, mapped_index1, mapped_index2)
		print(st.get())

def input():
	return sys.stdin.readline().rstrip('\n').strip()
ts = 1
for t in range(1, ts + 1):
	solve()


def main():
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
	inf = 1e+17
	mod = 10 ** 9 + 7

	def factorial(n):
		f = 1
		for i in range(1, n + 1):
			f = f * i % mod
		return f

	def ncr(n, r):
		num = den = 1
		for i in range(r):
			num = num * (n - i) % mod
			den = den * (i + 1) % mod
		return num * pow(den, mod - 2, mod) % mod

	def solve(k, arr):
		arr = [0] + arr
		dp = [0] * pow(2, k) + [1] * pow(2, k)
		for i in range(pow(2, k) - 1, 0, -1):
			if arr[i] == '0':
				dp[i] = dp[2 * i + 1]
			elif arr[i] == '1':
				dp[i] = dp[2 * i]
			else:
				dp[i] = dp[2 * i] + dp[2 * i + 1]
		q = int(input())
		for _ in range(q):
			query = input().split()
			index = pow(2, k) - int(query[0])
			type = query[1]
			arr[index] = type
			while index != 0:
				if arr[index] == '0':
					dp[index] = dp[2 * index + 1]
				elif arr[index] == '1':
					dp[index] = dp[2 * index]
				else:
					dp[index] = dp[2 * index] + dp[2 * index + 1]
				index //= 2
			print(dp[1])
		pass
	t = 1
	ans = []
	for _ in range(t):
		k = int(input())
		arr = list(input())[:-1][::-1]
		ans.append(solve(k, arr))
import sys, threading
import bisect
import math
import itertools
from sys import stdout
import heapq
from queue import PriorityQueue
input = sys.stdin.readline
thread = threading.Thread(target=main)
thread.start()
thread.join()


import sys
input = sys.stdin.readline
k = int(input())
n = 1 << k
s = list(input()[:-1])
dp = [1] * (2 * n)
for i in range(n - 1, 0, -1):
	if s[n - 1 - i] == '0':
		dp[i] = dp[i * 2 + 1]
	elif s[n - 1 - i] == '1':
		dp[i] = dp[i * 2]
	else:
		dp[i] = dp[i * 2] + dp[i * 2 + 1]
for _ in range(int(input())):
	(p, c) = input().split()
	p = int(p) - 1
	s[p] = c
	i = n - 1 - p
	while i:
		if s[n - 1 - i] == '0':
			dp[i] = dp[i * 2 + 1]
		elif s[n - 1 - i] == '1':
			dp[i] = dp[i * 2]
		else:
			dp[i] = dp[i * 2] + dp[i * 2 + 1]
		i //= 2
	print(dp[1])


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				pp[i] += 1
				prime[i] = False
		p += 1

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[n - 1]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = arr[mid]
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[0]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = arr[mid]
			left = mid + 1
	return res
t = 1
for _ in range(t):
	k = int(input())
	s = input()
	n = 2 ** k - 1
	s = list(s)
	s = [0] + s[::-1]
	a = [0] * 2 ** k
	for i in range(2 ** k - 1, 0, -1):
		if 2 * i <= n:
			if s[i] == '0':
				a[i] = a[2 * i + 1]
			elif s[i] == '1':
				a[i] = a[2 * i]
			else:
				a[i] = a[2 * i] + a[2 * i + 1]
		elif s[i] == '0':
			a[i] = 1
		elif s[i] == '1':
			a[i] = 1
		else:
			a[i] = 2
	q = int(input())
	for x in range(q):
		(p, c) = map(str, input().split(' '))
		p = n + 1 - int(p)
		s[p] = c
		i = p
		while i >= 1:
			if 2 * i <= n:
				if s[i] == '0':
					a[i] = a[2 * i + 1]
				elif s[i] == '1':
					a[i] = a[2 * i]
				else:
					a[i] = a[2 * i] + a[2 * i + 1]
			elif s[i] == '0':
				a[i] = 1
			elif s[i] == '1':
				a[i] = 1
			else:
				a[i] = 2
			i //= 2
		print(a[1])


from sys import stdin, gettrace
if gettrace():

	def inputi():
		return input()
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def main():
	k = int(input())
	ss = [' '] + list(input())
	q = int(input())
	qr = []
	for _ in range(q):
		(p, c) = input().split()
		qr.append((int(p), c))
	n = len(ss) - 1
	vals = [0] * (n + 1)
	for (i, c) in enumerate(ss[1:], 1):
		if i <= 2 ** (k - 1):
			vals[i] = 2 if c == '?' else 1
		else:
			hi = vals[i * 2 - n - 1]
			lo = vals[i * 2 - n - 2]
			vals[i] = hi if c == '1' else lo if c == '0' else hi + lo
	for (i, c) in qr:
		ss[i] = c
		while True:
			if i <= 2 ** (k - 1):
				vals[i] = 2 if ss[i] == '?' else 1
			else:
				hi = vals[i * 2 - n - 1]
				lo = vals[i * 2 - n - 2]
				vals[i] = hi if ss[i] == '1' else lo if ss[i] == '0' else hi + lo
			if i == n:
				break
			i = (n + i) // 2 + 1
		print(vals[n])
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def check(x):
	if x == '?' * len(x):
		return True
	i = 0
	while x[i] == '?':
		i += 1
	for j in range(len(x)):
		if x[j] == '?' or int(x[j]) == (int(x[i]) if (j - i) % 2 == 0 else 1 - int(x[i])):
			continue
		else:
			return False
	return True

def valid(s):
	ans = 0
	for i in range(n):
		for j in range(i + 1, n + 1):
			if check(s[i:j]):
				ans += 1
	return ans
k = int(input())
s = [p for p in input()]
qc = [0] * (len(s) + 2)
child = [[] for i in range(len(s) + 2)]
parents = [-1 for i in range(len(s) + 2)]
x = 2 ** (k - 1) + 1
oo = 2
for i in range(1, len(s) + 1):
	oo -= 1
	child[x] += [i]
	parents[i] = x
	if not oo:
		x += 1
		oo = 2
for i in range(1, len(s) + 1):
	if not child[i]:
		qc[i] = 1 if s[i - 1] != '?' else 2
	elif s[i - 1] != '?':
		qc[i] = qc[child[i][int(s[i - 1])]]
	else:
		qc[i] = sum((qc[kl] for kl in child[i]))
fu = 2 ** k - 1
for ___ in range(int(input())):
	(p, c) = input().split()
	q = int(p)
	s[q - 1] = c
	while q != fu + 1:
		if not child[q]:
			qc[q] = 1 if s[q - 1] != '?' else 2
		elif s[q - 1] != '?':
			qc[q] = qc[child[q][int(s[q - 1])]]
		else:
			qc[q] = sum((qc[kl] for kl in child[q]))
		q = parents[q]
	print(qc[fu])


def tree(a, k, q):
	ans = [0] * pow(2, k + 1)
	a = a + ['l']
	a = a[::-1]
	for i in range(1 << k, 1 << k + 1):
		ans[i] = 1
	for i in range((1 << k) - 1, 0, -1):
		if a[i] == '0':
			ans[i] += ans[2 * i + 1]
		elif a[i] == '1':
			ans[i] += ans[2 * i]
		else:
			ans[i] = ans[2 * i] + ans[2 * i + 1]
	for (p, ch) in q:
		p = (1 << k) - p
		a[p] = ch
		while p:
			if a[p] == '0':
				ans[p] = ans[2 * p + 1]
			elif a[p] == '1':
				ans[p] = ans[2 * p]
			else:
				ans[p] = ans[2 * p] + ans[2 * p + 1]
			p //= 2
		print(ans[1])
k = int(input())
a = list(input())
q = []
for i in range(int(input())):
	(x, y) = map(str, input().strip().split())
	x = int(x)
	q.append((x, y))
tree(a, k, q)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = list(input())[::-1]
n = len(a)
ans = [0] * (4 * n)
for i in range(n, 4 * n):
	ans[i] = 1
for i in range(n - 1, -1, -1):
	left = 2 * i + 1
	right = 2 * i + 2
	if a[i] == '0':
		ans[i] = ans[right]
	if a[i] == '1':
		ans[i] = ans[left]
	if a[i] == '?':
		ans[i] = ans[left] + ans[right]

def fill(i, val):
	a[i] = val
	while True:
		left = 2 * i + 1
		right = 2 * i + 2
		if a[i] == '0':
			ans[i] = ans[right]
		if a[i] == '1':
			ans[i] = ans[left]
		if a[i] == '?':
			ans[i] = ans[left] + ans[right]
		if i == 0:
			break
		i = (i - 1) // 2
for q in range(int(input())):
	(ind, val) = input().split()
	fill(n - int(ind), val)
	print(ans[0])


from sys import stdin, stdout
import heapq
from collections import defaultdict
import math
import bisect
import io, os

def main():
	n = int(stdin.readline())
	s = stdin.readline().strip()
	S = []
	for x in s[::-1]:
		S.append(x)
	N2 = 2 ** n
	arr = [1] * (N2 * 2)
	for i in range(N2 - 2, -1, -1):
		p = 0
		if S[i] == '?':
			p = 2
		elif S[i] == '1':
			p = 1
		if p == 2:
			arr[i] = arr[i * 2 + 1] + arr[i * 2 + 2]
		elif p == 1:
			arr[i] = arr[i * 2 + 1]
		else:
			arr[i] = arr[i * 2 + 2]
	q = int(stdin.readline())
	for _ in range(q):
		(i, x) = list(map(str, stdin.readline().split()))
		i = N2 - int(i) - 1
		S[i] = x
		while i >= 0:
			p = 0
			if S[i] == '?':
				p = 2
			elif S[i] == '1':
				p = 1
			if p == 2:
				arr[i] = arr[i * 2 + 1] + arr[i * 2 + 2]
			elif p == 1:
				arr[i] = arr[i * 2 + 1]
			else:
				arr[i] = arr[i * 2 + 2]
			i = (i - 1) // 2
		stdout.write(str(arr[0]) + '\n')
main()


def main():
	k = int(input())
	s = input()
	n = len(s)
	arr = [-1] * (n + 1)
	j = 1
	for i in range(n - 1, -1, -1):
		arr[j] = s[i]
		j += 1
	n += 1
	tree = [0] * n
	for i in range(n - 1, 0, -1):
		if i * 2 < n:
			if arr[i] == '?':
				tree[i] = tree[i * 2] + tree[i * 2 + 1]
			elif arr[i] == '0':
				tree[i] = tree[i * 2 + 1]
			else:
				tree[i] = tree[i * 2]
		elif arr[i] == '?':
			tree[i] = 2
		else:
			tree[i] = 1
	q = int(input())
	allans = []
	for _ in range(q):
		(p, c) = input().split()
		i = n - int(p)
		arr[i] = c
		while i > 0:
			if i * 2 < n:
				if arr[i] == '?':
					tree[i] = tree[i * 2] + tree[i * 2 + 1]
				elif arr[i] == '0':
					tree[i] = tree[i * 2 + 1]
				else:
					tree[i] = tree[i * 2]
			elif arr[i] == '?':
				tree[i] = 2
			else:
				tree[i] = 1
			i //= 2
		ans = tree[1]
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import sys
from math import gcd
read_line = lambda : sys.stdin.readline().strip()
read_intmap = lambda : map(int, read_line().split())

def testCase():
	k = int(input())
	k1 = (1 << k) - 1
	k2 = 1 << k - 1
	last = k1 - 1
	tree = [-1] * k1
	parent = [-1] * k1
	dp = [0] * k1
	for i in range(k1 - 1, -1, -1):
		if last <= 0:
			break
		tree[i] = [last - 2, last - 1]
		parent[last - 1] = i
		parent[last - 2] = i
		last -= 2
	s = list(read_line())

	def build(ind, char):
		if ind < k2:
			dp[ind] = 2 if char == '?' else 1
		else:
			dp[ind] = 0
			children = tree[ind]
			if char != '0':
				dp[ind] += dp[children[1]]
			if char != '1':
				dp[ind] += dp[children[0]]
	for (ind, char) in enumerate(s):
		build(ind, char)
	for q in range(int(input())):
		(p, c) = read_line().split()
		p = int(p) - 1
		s[p] = c
		while p != -1:
			build(p, s[p])
			p = parent[p]
		print(dp[-1])
t = 1
for i in range(t):
	testCase()


import sys

def input():
	return sys.stdin.readline().rstrip()

def inputa():
	return list(map(int, input().split()))

def out(var):
	sys.stdout.write(str(var) + '\n')

def outa(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def setup():
	import os
	dir_path = os.path.dirname(os.path.realpath(__file__))
	sys.stdin = open(os.path.join(dir_path, 'input.txt'), 'r')
	sys.stdout = open(os.path.join(dir_path, 'output.txt'), 'w')

def query(idx: int, s_val: str):
	if tree[idx][1] == s_val:
		return
	tree[idx][1] = s_val
	i = idx
	while i != 0:
		if 2 * i not in tree:
			tree[i][0] = 2 if tree[i][1] == '?' else 1
			i = i // 2
			continue
		if tree[i][1] == '?':
			tree[i][0] = tree[i * 2][0] + tree[i * 2 + 1][0]
		elif tree[i][1] == '0':
			tree[i][0] = tree[i * 2 + 1][0]
		else:
			tree[i][0] = tree[i * 2][0]
		i = i // 2
pow2 = int(input())
s = input()
num_games = len(s)
tree = {}
for i in range(num_games):
	idx = num_games - i
	if idx * 2 > num_games:
		tree[idx] = [1, s[i]] if s[i] != '?' else [2, s[i]]
	elif s[i] == '?':
		tree[idx] = [tree[idx * 2][0] + tree[idx * 2 + 1][0], s[i]]
	elif s[i] == '0':
		tree[idx] = [tree[idx * 2 + 1][0], s[i]]
	else:
		tree[idx] = [tree[idx * 2][0], s[i]]
for _ in range(int(input())):
	(idx, s_val) = input().split()
	idx = num_games - int(idx) + 1
	query(idx, s_val)
	out(tree[1][0])


import sys
input = sys.stdin.readline
K = int(input())
S = input().rstrip()
Q = int(input())
PC = [input().split() for i in range(Q)]
A = [''] + list(S)[::-1]
N = len(A)
C = [0] * N
for i in range(N // 2, N):
	if A[i] == '?':
		C[i] = 2
	else:
		C[i] = 1
for i in range(N // 2 - 1, 0, -1):
	if A[i] == '?':
		C[i] = C[i * 2] + C[i * 2 + 1]
	elif A[i] == '1':
		C[i] = C[i * 2]
	else:
		C[i] = C[i * 2 + 1]
ans = []
for (p, c) in PC:
	i = N - int(p)
	if c == A[i]:
		ans.append(C[1])
		continue
	A[i] = c
	if i >= N // 2:
		if c == '?':
			C[i] = 2
		else:
			C[i] = 1
		i //= 2
	while i >= 1:
		if A[i] == '?':
			C[i] = C[i * 2] + C[i * 2 + 1]
		elif A[i] == '1':
			C[i] = C[i * 2]
		else:
			C[i] = C[i * 2 + 1]
		i //= 2
	ans.append(C[1])
print(*ans, sep='\n')


import os
import sys
from bisect import bisect_right, bisect_left
from collections import Counter
from io import BytesIO, IOBase
from math import gcd, inf, sqrt, ceil

def lcm(a, b):
	return a * b // gcd(a, b)

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = Counter()
	while x != 1:
		ret[spf[x]] += 1
		x = x // spf[x]
	return ret

def printDivisors(n):
	i = 2
	z = [1, n]
	while i <= sqrt(n):
		if n % i == 0:
			if n / i == i:
				z.append(i)
			else:
				z.append(i)
				z.append(n // i)
		i = i + 1
	return z

def create(n, x, f):
	pq = len(bin(n)[2:])
	if f == 0:
		tt = min
	else:
		tt = max
	dp = [[inf] * n for _ in range(pq)]
	dp[0] = x
	for i in range(1, pq):
		for j in range(n - (1 << i) + 1):
			dp[i][j] = tt(dp[i - 1][j], dp[i - 1][j + (1 << i - 1)])
	return dp

def enquiry(l, r, dp, f):
	if l > r:
		return inf if not f else -inf
	if f == 1:
		tt = max
	else:
		tt = min
	pq1 = len(bin(r - l + 1)[2:]) - 1
	return tt(dp[pq1][l], dp[pq1][r - (1 << pq1) + 1])

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	x = []
	for i in range(2, n + 1):
		if prime[i]:
			x.append(i)
	return x

def main():
	sys.setrecursionlimit(2 * 100000)

	def dfs(node):
		if node >= len(s):
			return 1
		if dp[node] != -1:
			return dp[node]
		if s[node] == '1':
			dp[node] = dfs(2 * node + 1)
		elif s[node] == '0':
			dp[node] = dfs(2 * node + 2)
		else:
			dp[node] = dfs(2 * node + 1) + dfs(2 * node + 2)
		return dp[node]

	def update(node):
		if s[node] == '1':
			if 2 * node + 1 < len(s):
				dp[node] = dfs(2 * node + 1)
			else:
				dp[node] = 1
			if node != 0:
				update((node - 1) // 2)
		elif s[node] == '0':
			if 2 * node + 2 < len(s):
				dp[node] = dfs(2 * node + 2)
			else:
				dp[node] = 1
			if node != 0:
				update((node - 1) // 2)
		else:
			if 2 * node + 1 < len(s):
				dp[node] = dfs(2 * node + 1)
			else:
				dp[node] = 1
			if 2 * node + 2 < len(s):
				dp[node] += dfs(2 * node + 2)
			else:
				dp[node] += 1
			if node != 0:
				update((node - 1) // 2)
	k = int(input())
	s = list(input().strip())
	dp = [-1] * len(s)
	s = s[::-1]
	dfs(0)
	for i in range(int(input())):
		(u, v) = input().split()
		s[len(s) - int(u)] = v
		update(len(s) - int(u))
		print(dfs(0))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
from itertools import permutations
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
k = int(input())
l = list(input())
l.reverse()
n = pow(2, k) - 1
qw = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	qw[i] = 1
	if l[i] == '0':
		if 2 * i + 2 < n:
			qw[i] = qw[2 * i + 2]
	elif l[i] == '1':
		if 2 * i + 1 < n:
			qw[i] = qw[2 * i + 1]
	elif 2 * i + 2 < n:
		qw[i] = qw[2 * i + 1] + qw[2 * i + 2]
	else:
		qw[i] = 2
q = int(input())
for ik in range(q):
	(a, b) = map(str, input().split())
	a = int(a)
	a = n - a
	l[a] = b
	i = a
	if l[i] == '0':
		qw[i] = 1
		if 2 * i + 2 < n:
			qw[i] = qw[2 * i + 2]
	elif l[i] == '1':
		qw[i] = 1
		if 2 * i + 1 < n:
			qw[i] = qw[2 * i + 1]
	elif 2 * i + 2 < n:
		qw[i] = qw[2 * i + 1] + qw[2 * i + 2]
	else:
		qw[i] = 2
	cur = i
	for j in range(k):
		cur = (cur - 1) // 2
		i = cur
		if l[i] == '0':
			if 2 * i + 2 < n:
				qw[i] = qw[2 * i + 2]
		elif l[i] == '1':
			if 2 * i + 1 < n:
				qw[i] = qw[2 * i + 1]
		elif 2 * i + 2 < n:
			qw[i] = qw[2 * i + 1] + qw[2 * i + 2]
		else:
			qw[i] = 2
		if cur == 0:
			break
	print(qw[0])


from sys import stdin, stdout, setrecursionlimit as srl
from threading import stack_size
from collections import deque, defaultdict as dd
from math import gcd, ceil, log2
a = 0
l = []
input = stdin.readline
flush = stdout.flush

def update(i, v):
	global a, l, s
	l[i - 1] = v
	node = a - 1 - i
	if node > (a - 3) // 2:
		s[node] = (v == '?') * 2 + 1 * (v in ['0', '1'])
		node = (node - 1) // 2
	while node > 0:
		if l[a - 2 - node] == '0':
			s[node] = s[2 * node + 2]
		elif l[a - 2 - node] == '1':
			s[node] = s[2 * node + 1]
		else:
			s[node] = s[2 * node + 1] + s[2 * node + 2]
		node = (node - 1) // 2
	if a == 2:
		return
	if l[a - 2 - node] == '0':
		s[node] = s[2 * node + 2]
	elif l[a - 2 - node] == '1':
		s[node] = s[2 * node + 1]
	else:
		s[node] = s[2 * node + 1] + s[2 * node + 2]
tc = 1
for _ in range(tc):
	k = int(input())
	s = input()[:-1]
	l = [i for i in s]
	a = 1 << k
	s = [-1 for i in range(a - 1)]
	for i in range(a - 2, a - 2 - a // 2, -1):
		s[i] = 1 * (l[a - 2 - i] in ['0', '1']) + 2 * (l[a - 2 - i] == '?')
	for i in range(a - 2 - a // 2, -1, -1):
		if l[a - 2 - i] == '0':
			s[i] = s[2 * i + 2]
		elif l[a - 2 - i] == '1':
			s[i] = s[2 * i + 1]
		else:
			s[i] = s[2 * i + 1] + s[2 * i + 2]
	q = int(input())
	for i in range(q):
		(p, c) = map(str, input().split())
		p = int(p)
		update(p, c)
		print(s[0])


import os, sys
from io import BytesIO, IOBase
from collections import deque, Counter, defaultdict as dft
from heapq import heappop, heappush
from math import log, sqrt, factorial, cos, tan, sin, radians, log2, ceil, floor, gcd
from bisect import bisect, bisect_left, bisect_right
from decimal import *
import sys, threading
from itertools import permutations, combinations
from copy import deepcopy
input = sys.stdin.readline
ii = lambda : int(input())
si = lambda : input().rstrip()
mp = lambda : map(int, input().split())
ms = lambda : map(str, input().strip().split(' '))
ml = lambda : list(mp())
mf = lambda : map(float, input().split())
alphs = 'abcdefghijklmnopqrstuvwxyz'

def solve():

	def do(x):
		if 2 * x + 1 >= total - 1:
			if s[tre[x]] == '?':
				arr[x] = 2
			else:
				arr[x] = 1
		else:
			do(x * 2 + 1)
			do(x * 2 + 2)
			if s[tre[x]] == '0':
				arr[x] = arr[2 * x + 1]
			elif s[tre[x]] == '1':
				arr[x] = arr[2 * x + 2]
			else:
				arr[x] = arr[2 * x + 1] + arr[2 * x + 2]
	idx = dft(int)
	tre = dft(int)
	n = ii()
	total = 2 ** n
	s = list(input())
	arr = [0 for i in range(2 ** n + 5)]
	j = total - 2
	ls = deque([0])
	while ls:
		ln = len(ls)
		for i in range(ln):
			t = ls.popleft()
			idx[j] = t
			tre[t] = j
			j -= 1
			if 2 * t + 1 < total - 1:
				ls.append(2 * t + 2)
				ls.append(2 * t + 1)
	do(0)
	q = ii()
	for _ in range(q):
		(a, b) = input().split()
		s[int(a) - 1] = b
		x = idx[int(a) - 1]
		while x >= 0:
			if 2 * x + 1 >= total - 1:
				if s[tre[x]] == '?':
					arr[x] = 2
				else:
					arr[x] = 1
			elif s[tre[x]] == '0':
				arr[x] = arr[2 * x + 1]
			elif s[tre[x]] == '1':
				arr[x] = arr[2 * x + 2]
			else:
				arr[x] = arr[2 * x + 1] + arr[2 * x + 2]
			x = (x - 1) // 2
		print(arr[0])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
tc = 1
for i in range(tc):
	solve()


import sys
import math
mod = 10 ** 9 + 7
LI = lambda : [int(k) for k in input().split()]
SLI = lambda : [str(k) for k in input().split()]
input = lambda : sys.stdin.readline().rstrip()
IN = lambda : int(input())
S = lambda : input()
r = range

def match(ind):
	p = ll - 1 - ind
	if s[p] == '?':
		tr[ind] = tr[2 * ind + 1] + tr[2 * ind + 2]
	elif s[p] == '0':
		tr[ind] = tr[2 * ind + 2]
	else:
		tr[ind] = tr[2 * ind + 1]
	return tr
k = IN()
s = S()
s = list(s)
q = IN()
ll = 2 ** k - 1
tr = [0] * ll
for i in r(ll):
	ind = ll - 1 - i
	if i < 2 ** (k - 1):
		if s[i] == '?':
			tr[ind] = 2
		else:
			tr[ind] = 1
	elif s[i] == '?':
		tr[ind] = tr[2 * ind + 1] + tr[2 * ind + 2]
	elif s[i] == '0':
		tr[ind] = tr[2 * ind + 2]
	else:
		tr[ind] = tr[2 * ind + 1]
for i in r(q):
	(p, c) = SLI()
	p = int(p)
	p -= 1
	ind = ll - 1 - p
	if p < 2 ** (k - 1):
		if c == '?':
			tr[ind] = 2
		else:
			tr[ind] = 1
	elif c == '?':
		tr[ind] = tr[2 * ind + 1] + tr[2 * ind + 2]
	elif c == '0':
		tr[ind] = tr[2 * ind + 2]
	else:
		tr[ind] = tr[2 * ind + 1]
	while ind:
		ind -= 1
		ind //= 2
		tr = match(ind)
	s[p] = c
	print(tr[0])


import sys
import math

def inpu():
	return sys.stdin.readline()

def pow(h):
	anss = 1
	for i in range(h):
		anss *= 2
	return anss
k = int(inpu())
a = list(inpu())
q = int(inpu())
done = False
n = 1
for i in range(k):
	n *= 2
n -= 1
m = (n + 1) // 2
g = [0] * n
for i in range(m):
	if a[i] == '?':
		g[i] = 2
	else:
		g[i] = 1
for i in range(m, n):
	if a[i] == '?':
		g[i] = g[2 * (i - m)] + g[2 * (i - m) + 1]
	else:
		g[i] = g[2 * (i - m) + int(a[i])]
for i in range(q):
	(iq, nq) = inpu().split()
	iq = int(iq) - 1
	a[iq] = nq
	j = iq
	if nq == '?' and iq < m:
		g[iq] = 2
		j //= 2
		j += m
	elif iq < m:
		g[iq] = 1
		j //= 2
		j += m
	while j < n:
		g0 = g[j]
		if a[j] == '?':
			g[j] = g[2 * (j - m)] + g[2 * (j - m) + 1]
		else:
			g[j] = g[2 * (j - m) + int(a[j])]
		if g[j] == g0:
			break
		j //= 2
		j += m
	print(g[-1])


import sys
input = sys.stdin.readline
k = int(input())
A = [0] + list(input().strip())
x = k - 1
B = []
r = 1
while x >= 0:
	B = list(range(r, r + (1 << x))) + B
	r += 1 << x
	x -= 1
B = [-1] + B
B_INV = [-1] * (1 << k)
for i in range(1, 1 << k):
	B_INV[B[i]] = i
C = [-1] * (1 << k)
for i in range(len(A)):
	if A[B[i]] == '0':
		C[i] = 0
	elif A[B[i]] == '1':
		C[i] = 1
	else:
		C[i] = 2
q = int(input())
seg_el = 1 << k
SEG = [1] * (2 * seg_el)
for i in range(seg_el - 1, 0, -1):
	if C[i] == 1:
		SEG[i] = SEG[i * 2 + 1]
	elif C[i] == 0:
		SEG[i] = SEG[2 * i]
	else:
		SEG[i] = SEG[2 * i] + SEG[2 * i + 1]

def update(i, s):
	while i != 0:
		if C[i] == 1:
			SEG[i] = SEG[i * 2 + 1]
		elif C[i] == 0:
			SEG[i] = SEG[2 * i]
		else:
			SEG[i] = SEG[2 * i] + SEG[2 * i + 1]
		i >>= 1
for queries in range(q):
	(x, y) = input().split()
	x = int(x)
	if y == '0':
		y = 0
	elif y == '1':
		y = 1
	else:
		y = 2
	C[B_INV[x]] = y
	update(B_INV[x], y)
	print(SEG[1])


import sys, os
import math
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
from io import BytesIO, IOBase

def main():
	for _ in range(1):
		dd = {}
		k = int(input())
		s = list(input())
		(c, u) = (2 ** k - 1, 2 ** k - 1)
		for i in s:
			if c * 2 + 1 <= u:
				if i == '?':
					dd[c] = dd[c * 2 + 1] + dd[c * 2]
				elif i == '1':
					dd[c] = dd[c * 2]
				else:
					dd[c] = dd[c * 2 + 1]
			elif i == '?':
				dd[c] = 2
			else:
				dd[c] = 1
			c -= 1
		for q in range(int(input())):
			(p, c) = input().split()
			p = int(p)
			comp = 2 ** k - p
			s[p - 1] = c
			while comp:
				if comp * 2 + 1 <= u:
					if s[u - comp] == '?':
						dd[comp] = dd[2 * comp + 1] + dd[2 * comp]
					elif s[u - comp] == '1':
						dd[comp] = dd[2 * comp]
					else:
						dd[comp] = dd[2 * comp + 1]
				elif s[u - comp] == '?':
					dd[comp] = 2
				else:
					dd[comp] = 1
				comp = comp // 2
			print(dd[1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def MI():
	return map(int, input().split())

def outP(var):
	sys.stdout.write(str(var) + '\n')
MOD = 10 ** 9 + 7
mod = 998244353
main()


maxN = 2 ** 18 + 5
t = [0] * maxN

def build(a, n):
	for v in range(n, 0, -1):
		if v * 2 > n:
			if a[v] == '?':
				t[v] = 2
			else:
				t[v] = 1
		elif a[v] == '?':
			t[v] = t[v * 2] + t[v * 2 + 1]
		elif a[v] == '0':
			t[v] = t[v * 2 + 1]
		else:
			t[v] = t[v * 2]

def query():
	return t[1]

def update(a, v, n):
	while v > 0:
		if v * 2 > n:
			if a[v] == '?':
				t[v] = 2
			else:
				t[v] = 1
		elif a[v] == '?':
			t[v] = t[v * 2] + t[v * 2 + 1]
		elif a[v] == '0':
			t[v] = t[v * 2 + 1]
		else:
			t[v] = t[v * 2]
		v //= 2

def main():
	k = int(input())
	a = list(input())
	n = 2 ** k - 1
	a.reverse()
	a = [None] + a
	build(a, n)
	allans = []
	q = int(input())
	for _ in range(q):
		(idx, c) = input().split()
		idx = int(idx)
		idx = n - idx + 1
		a[idx] = c
		update(a, idx, n)
		allans.append(query())
	multiLineArrayPrint(allans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import sys
input = sys.stdin.readline
K = int(input())
N = 1 << K
Conv = list(range(N - 1))
i = 0
for j in range(K):
	j = 1 << j
	Conv[i:i + j] = Conv[i:i + j][::-1]
	i += j
Conv.reverse()
func = lambda x: 0 if x == '0' else 1 if x == '1' else 2
Tmp = input()
S = [0] * (N - 1)
for i in range(N - 1):
	S[Conv[i]] = func(Tmp[i])
A = [0] * (N * 2)

def make(i):
	if i >= N - 1:
		A[i] = 1
	elif S[i] == 0:
		A[i] = make(i * 2 + 1)
		make(i * 2 + 2)
	elif S[i] == 1:
		make(i * 2 + 1)
		A[i] = make(i * 2 + 2)
	else:
		A[i] = make(i * 2 + 1) + make(i * 2 + 2)
	return A[i]
make(0)
func2 = lambda x, y: (Conv[int(x) - 1], 0 if y == '0' else 1 if y == '1' else 2)
Q = int(input())
for _ in range(Q):
	(i, s) = func2(*input().split())
	S[i] = s
	while True:
		if S[i] == 0:
			A[i] = A[i * 2 + 1]
		elif S[i] == 1:
			A[i] = A[i * 2 + 2]
		else:
			A[i] = A[i * 2 + 1] + A[i * 2 + 2]
		if i == 0:
			break
		i = (i - 1) // 2
	print(A[0])


import sys
input = sys.stdin.readline
k = int(input())
s = list(input().rstrip())
n = len(s) + 1
x = [0]
p2 = 1
d = dict()
for _ in range(k):
	for i in range(2 * p2, p2, -1):
		x.append(s[-(i - 1)])
		d[-(i - 1) % n] = len(x) - 1
	p2 *= 2
cnt = [1] * (2 * n)
for i in range(n - 1, 0, -1):
	if x[i] == '?':
		cnt[i] = cnt[2 * i] + cnt[2 * i + 1]
	else:
		cnt[i] = cnt[2 * i + int(x[i])]
q = int(input())
for _ in range(q):
	(p, c) = input().rstrip().split()
	u = d[int(p)]
	x[u] = c
	if c == '?':
		cnt[u] = cnt[2 * u] + cnt[2 * u + 1]
	else:
		cnt[u] = cnt[2 * u + int(c)]
	while u ^ 1:
		u //= 2
		if x[u] == '?':
			cnt[u] = cnt[2 * u] + cnt[2 * u + 1]
		else:
			cnt[u] = cnt[2 * u + int(x[u])]
	ans = cnt[1]
	print(ans)


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
k = int(input())
a = input()
b = [-1] + [i for i in reversed(a)]
ans = [-1] * len(b) + [1] * 2 ** k
for j in range(len(b) - 1, 0, -1):
	if b[j] == '?':
		ans[j] = ans[2 * j] + ans[2 * j + 1]
	elif b[j] == '0':
		ans[j] = ans[2 * j + 1]
	else:
		ans[j] = ans[2 * j]

def update(i, v):
	j = len(b) - i
	b[j] = v
	while j:
		if b[j] == '?':
			ans[j] = ans[2 * j] + ans[2 * j + 1]
		elif b[j] == '0':
			ans[j] = ans[2 * j + 1]
		else:
			ans[j] = ans[2 * j]
		j //= 2
for _ in range(int(input())):
	(i, v) = input().split()
	i = int(i)
	update(i, v)
	print(ans[1])


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	c = dict(Counter(l))
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
import sys, os, io
from math import gcd
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve():
	k = int(input())
	n = 2 ** k - 1
	s = list(input().strip())
	s = s[::-1]
	q = ii()
	ans = [0] * 2 ** k
	for i in range(2 ** k - 2, -1, -1):
		ans[i] = 1
		if s[i] == '1':
			if i * 2 + 1 < n:
				ans[i] = ans[i * 2 + 1]
		if s[i] == '0':
			if i * 2 + 2 < n:
				ans[i] = ans[i * 2 + 2]
		if s[i] == '?':
			ans[i] = 2
			if i * 2 + 1 < n:
				ans[i] = ans[i * 2 + 1]
			if i * 2 + 2 < n:
				ans[i] += ans[i * 2 + 2]
	for _ in range(q):
		(ind, c) = [x for x in input().split()]
		ind = int(ind) - 1
		ind = 2 ** k - 1 - ind - 1
		s[ind] = c
		i = ind
		if c == '0':
			if i * 2 + 2 < n:
				ans[i] = ans[i * 2 + 2]
			else:
				ans[i] = 1
		if c == '1':
			if i * 2 + 1 < n:
				ans[i] = ans[i * 2 + 1]
			else:
				ans[i] = 1
		if c == '?':
			ans[i] = 2
			if i * 2 + 1 < n:
				ans[i] = ans[i * 2 + 1]
			if i * 2 + 1 < n:
				ans[i] += ans[i * 2 + 2]
		ind = (ind - 1) // 2
		while ind >= 0:
			i = ind
			ans[i] = 1
			c = s[i]
			if c == '0':
				if i * 2 + 2 < n:
					ans[i] = ans[i * 2 + 2]
				else:
					ans[i] = 1
			if c == '1':
				if i * 2 + 1 < n:
					ans[i] = ans[i * 2 + 1]
				else:
					ans[i] = 1
			if c == '?':
				ans[i] = 2
				if i * 2 + 1 < n:
					ans[i] = ans[i * 2 + 1]
				if i * 2 + 1 < n:
					ans[i] += ans[i * 2 + 2]
			ind = (ind - 1) // 2
		print(ans[0])
t = 1
for _ in range(t):
	solve()


import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
from collections import deque, defaultdict
from functools import lru_cache, reduce
from heapq import heappush, heappop, heapify, _heappop_max, _heapify_max

def _heappush_max(heap, item):
	heap.append(item)
	heapq._siftdown_max(heap, 0, len(heap) - 1)
from math import gcd as Gcd
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
k = int(readline())
N = 1 << k
f = [0] * N
S = list(readline())
for i in range(N - 1, N // 2 - 1, -1):
	if S[N - i - 1] in '01':
		f[i] = 1
	else:
		f[i] = 2
for i in range(N // 2 - 1, 0, -1):
	if S[N - i - 1] in '0?':
		f[i] += f[2 * i + 1]
	if S[N - i - 1] in '1?':
		f[i] += f[2 * i]
Q = int(readline())
for _ in range(Q):
	(p, c) = readline().split()
	p = N - int(p)
	S[N - p - 1] = c
	if N // 2 <= p:
		if c in '01':
			f[p] = 1
		else:
			f[p] = 2
		p //= 2
	while p:
		f[p] = 0
		if S[N - p - 1] in '0?':
			f[p] += f[2 * p + 1]
		if S[N - p - 1] in '1?':
			f[p] += f[2 * p]
		p //= 2
	print(f[1])


import sys
from math import gcd
input = sys.stdin.readline

def solve():
	k = int(input())
	s1 = list(input().strip())
	a = [1] * (len(s1) * 2 + 1)
	j = 0
	s = [None] * len(s1)
	p = [None] * len(s1)
	for i in range(k):
		w = (1 << k - i - 1) - 1
		for z in range(1 << k - 1 - i):
			p[j] = w
			s[w] = s1[j]
			j += 1
			w += 1
	for i in range(len(s1) - 1, -1, -1):
		if s[i] == '1':
			a[i] = a[i * 2 + 2]
		elif s[i] == '0':
			a[i] = a[i * 2 + 1]
		else:
			a[i] = a[i * 2 + 1] + a[i * 2 + 2]
	for i in range(int(input())):
		(x, c) = input().split()
		x = p[int(x) - 1]
		s[x] = c
		while True:
			if s[x] == '1':
				a[x] = a[x * 2 + 2]
			elif s[x] == '0':
				a[x] = a[x * 2 + 1]
			else:
				a[x] = a[x * 2 + 1] + a[x * 2 + 2]
			if x == 0:
				break
			x = (x - 1) // 2
		print(a[0])
solve()


import sys, io, os
try:
	Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
	Z = lambda : sys.stdin.readline().encode()
Y = lambda : map(int, Z().split())
k = int(Z())
n = 1 << k
l = n + n - 1
s = list(Z().strip())
d = [1] * l
(b, p) = (n, 0)
for y in range(k - 1, -1, -1):
	for i in range(1 << y):
		if s[b - n + i] == 48:
			d[b + i] = d[p + 2 * i]
		elif s[b - n + i] == 49:
			d[b + i] = d[p + 2 * i + 1]
		else:
			d[b + i] = d[p + 2 * i] + d[p + 2 * i + 1]
	(b, p) = (b + (1 << y), b)
O = []
for _ in range(int(Z())):
	(i, c) = Z().split()
	i = int(i) - 1
	s[i] = c[0]
	(b, p) = (n, 0)
	f = 0
	for y in range(k - 1, -1, -1):
		v = 1 << y
		if not f and b + v - n > i:
			i -= b - n
			f = 1
		if f:
			if s[b - n + i] == 48:
				d[b + i] = d[p + 2 * i]
			elif s[b - n + i] == 49:
				d[b + i] = d[p + 2 * i + 1]
			else:
				d[b + i] = d[p + 2 * i] + d[p + 2 * i + 1]
			i >>= 1
		(b, p) = (b + v, b)
	O.append(str(d[-1]))
print('\n'.join(O))


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]

def update_game(k, i, value):
	if value == '0':
		if k == K - 1:
			V[k][i] = 1
		else:
			V[k][i] = V[k + 1][2 * i]
	elif value == '1':
		if k == K - 1:
			V[k][i] = 1
		else:
			V[k][i] = V[k + 1][2 * i + 1]
	elif k == K - 1:
		V[k][i] = 2
	else:
		V[k][i] = V[k + 1][2 * i] + V[k + 1][2 * i + 1]
K = int(input())
S = input()
T = [list() for _ in range(K)]
V = [list() for _ in range(K)]
j = 0
for k in reversed(range(K)):
	for i in range(2 ** k):
		T[k].append(S[j])
		V[k].append(-1)
		update_game(k, i, S[j])
		j += 1
Q = int(input())
for _ in range(Q):
	(p, c) = input().split()
	p = int(p) - 1
	k = K - 1
	i = p
	while i >= 2 ** k:
		i -= 2 ** k
		k -= 1
	T[k][i] = c
	update_game(k, i, c)
	i1 = i
	for k1 in range(k - 1, -1, -1):
		i1 //= 2
		update_game(k1, i1, T[k1][i1])
	ans = V[0][0]
	print(ans)


from math import log2
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, d2, d1, k):
		self.size = 2 ** (k + 1)
		self.default = 1
		self.data = [self.default] * self.size
		self.process(d2, d1)

	def fun(self, val, l1, l2):
		if val == '1':
			return l2
		elif val == '0':
			return l1
		else:
			return l1 + l2

	def process(self, d2, d1):
		for i in range(self.size // 2 - 1, 0, -1):
			self.data[i] = self.fun(d1[d2[i]], self.data[2 * i], self.data[2 * i + 1])

	def build(self, index, d2, d1):
		while index:
			self.data[index] = self.fun(d1[d2[index]], self.data[2 * index], self.data[2 * index + 1])
			index >>= 1

	def query(self):
		return self.data[1]

	def update(self, value, d2, d1):
		self.build(value, d2, d1)
k = int(input())
s = input()
req = 2 ** k
d1 = [0 for i in range(req)]
d = [0 for i in range(req)]
d2 = [0 for i in range(req)]
for j in range(len(s)):
	d1[j + 1] = s[j]
curr = 2
curr1 = 0
last = req - 1
while curr1 < req - 2:
	p1 = req - curr
	while p1 < last:
		d[p1 + 1] = curr1 + 1
		d2[curr1 + 1] = p1 + 1
		curr1 += 1
		p1 += 1
	last = req - curr
	curr *= 2
q = int(input())
if k > 1:
	s1 = SegmentTree(d2, d1, k)
	for j in range(q):
		(p, c) = map(str, input().split())
		p = int(p)
		d1[p] = c
		s1.update(d[p], d2, d1)
		print(s1.query())
else:
	for j in range(q):
		(p, c) = map(str, input().split())
		p = int(p)
		d1[p] = c
		if d1[p] == '?':
			print(2)
		else:
			print(1)


import sys
input = sys.stdin.readline
k = int(input())
s = input()[:-1]
poss = [0] * (k + 1)
slist = [0] * (k + 1)
cur = 0
for i in range(k + 1):
	poss[i] = [1] * 2 ** (k - i)
	slist[i] = [1] * 2 ** (k - i)
	if i:
		for j in range(2 ** (k - i)):
			char = s[cur]
			slist[i][j] = char
			if char == '?':
				poss[i][j] = poss[i - 1][2 * j] + poss[i - 1][2 * j + 1]
			if char == '0':
				poss[i][j] = poss[i - 1][2 * j]
			if char == '1':
				poss[i][j] = poss[i - 1][2 * j + 1]
			cur += 1
for f in range(int(input())):
	(x, y) = input().split()
	x = int(x) - 1
	lv = 1
	while x >= 2 ** (k - lv):
		x -= 2 ** (k - lv)
		lv += 1
	pos = x
	slist[lv][pos] = y
	while lv <= k:
		char = slist[lv][pos]
		if char == '?':
			poss[lv][pos] = poss[lv - 1][2 * pos] + poss[lv - 1][2 * pos + 1]
		if char == '0':
			poss[lv][pos] = poss[lv - 1][2 * pos]
		if char == '1':
			poss[lv][pos] = poss[lv - 1][2 * pos + 1]
		lv += 1
		pos //= 2
	print(poss[-1][0])


import sys
import getpass
import math, random
import functools, itertools, collections, heapq, bisect
from collections import Counter, defaultdict, deque
input = sys.stdin.readline
M9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def minus_one(arr):
	return [x - 1 for x in arr]

def minus_one_matrix(mrr):
	return [[x - 1 for x in row] for row in mrr]

def solve_(srr, qrr, k):
	mappping = {'?': 2, '1': 1, '0': 0}
	status = [mappping[x] for x in srr]
	counts = [1 for _ in srr]
	nextidx = [-1 for _ in srr]
	prevsmall_arr = [-1 for _ in srr]
	prevlarge_arr = [-1 for _ in srr]
	idx = 0
	for j in range(k - 1, -1, -1):
		prevsize = 2 ** (j + 1)
		startidx = idx
		for i in range(2 ** j):
			if j == k - 1:
				if status[idx] == 2:
					counts[idx] = 2
			else:
				prevsmall = startidx - prevsize + (idx - startidx) * 2
				prevlarge = prevsmall + 1
				nextidx[prevsmall] = idx
				nextidx[prevlarge] = idx
				prevsmall_arr[idx] = prevsmall
				prevlarge_arr[idx] = prevlarge
				if status[idx] == 0:
					counts[idx] = counts[prevsmall]
				if status[idx] == 1:
					counts[idx] = counts[prevlarge]
				if status[idx] == 2:
					counts[idx] = counts[prevsmall] + counts[prevlarge]
			idx += 1
	res = []
	for row in qrr:
		(idx, op) = row.split()
		idx = int(idx) - 1
		op = mappping[op]
		status[idx] = op
		if idx < 2 ** (k - 1):
			if status[idx] == 0:
				counts[idx] = 1
			if status[idx] == 1:
				counts[idx] = 1
			if status[idx] == 2:
				counts[idx] = 2
		else:
			prevsmall = prevsmall_arr[idx]
			prevlarge = prevlarge_arr[idx]
			if status[idx] == 0:
				counts[idx] = counts[prevsmall]
			if status[idx] == 1:
				counts[idx] = counts[prevlarge]
			if status[idx] == 2:
				counts[idx] = counts[prevsmall] + counts[prevlarge]
		while nextidx[idx] != -1:
			idx = nextidx[idx]
			prevsmall = prevsmall_arr[idx]
			prevlarge = prevlarge_arr[idx]
			if status[idx] == 0:
				counts[idx] = counts[prevsmall]
			if status[idx] == 1:
				counts[idx] = counts[prevlarge]
			if status[idx] == 2:
				counts[idx] = counts[prevsmall] + counts[prevlarge]
		res.append(counts[-1])
	return res
for case_num in [0]:
	k = int(input())
	srr = input().strip()
	q = int(input())
	qrr = read_strings(q)
	res = solve(srr, qrr, k)
	res = '\n'.join((str(x) for x in res))
	print(res)


from sys import stdin, stdout
from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as cmb, permutations as pmb
from math import factorial as f, ceil, gcd, sqrt, log, inf
mi = lambda : map(int, input().split())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
mati = lambda r: [li() for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)
MOD = 10 ** 9 + 7

def soe(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def ncr(n, r):
	(p, k) = (1, 1)
	if n - r < r:
		r = n - r
	if r != 0:
		while r:
			(p, k) = (p * n, k * r)
			m = gcd(p, k)
			(p, k) = (p // m, k // m)
			(n, r) = (n - 1, r - 1)
	else:
		p = 1
	return p

def solve():
	k = ii()
	s = [x for x in input()]
	q = ii()
	queries = [tuple(input().split()) for _ in range(q)]
	lim = 2 ** k
	seg = [1] * lim
	seg[0] = 0
	for i in range(lim // 2):
		if s[i] == '?':
			seg[lim - i - 1] = 2
	for i in range(lim // 2, lim - 1):
		j = lim - i - 1
		if s[i] == '?':
			seg[j] = seg[j * 2] + seg[j * 2 + 1]
		elif s[i] == '1':
			seg[j] = seg[j * 2]
		else:
			seg[j] = seg[j * 2 + 1]
	for (p, c) in queries:
		s[int(p) - 1] = c
		j = lim - int(p)
		if 2 * j + 1 < lim:
			if c == '?':
				seg[j] = seg[j * 2] + seg[j * 2 + 1]
			elif c == '1':
				seg[j] = seg[j * 2]
			else:
				seg[j] = seg[j * 2 + 1]
		elif c == '?':
			seg[j] = 2
		else:
			seg[j] = 1
		while j // 2 > 0:
			j = j // 2
			i = lim - j - 1
			if s[i] == '?':
				seg[j] = seg[j * 2] + seg[j * 2 + 1]
			elif s[i] == '1':
				seg[j] = seg[j * 2]
			else:
				seg[j] = seg[j * 2 + 1]
		print(seg[1])
for _ in range(1):
	solve()


import sys
k = int(input())
s = list(input())[::-1]
n = 2 ** k - 1
dp = [0] * n
for i in range(n - 1, -1, -1):
	x = 2 * i + 1
	y = 2 * i + 2
	if x < n and y < n:
		if s[i] == '1':
			dp[i] = dp[x]
		if s[i] == '0':
			dp[i] = dp[y]
		if s[i] == '?':
			dp[i] = dp[x] + dp[y]
	elif s[i] == '?':
		dp[i] = 2
	else:
		dp[i] = 1
q = int(input())
for q in range(q):
	(x, y) = sys.stdin.readline().split()
	a = int(x)
	b = str(y)
	ind = n - a
	if s[ind] == b:
		print(dp[0])
		continue
	s[ind] = b
	f = 0
	while f != 1:
		x = 2 * ind + 1
		y = 2 * ind + 2
		if x < n and y < n:
			if s[ind] == '1':
				dp[ind] = dp[x]
			elif s[ind] == '0':
				dp[ind] = dp[y]
			else:
				dp[ind] = dp[x] + dp[y]
		elif s[ind] == '?':
			dp[ind] = 2
		else:
			dp[ind] = 1
		if ind == 0:
			f = 1
		ind = ind // 2 + ind % 2 - 1
	sys.stdout.write(str(dp[0]) + '\n')


import sys
K = int(input())
two_K = 1 << K
S = list(sys.stdin.readline()[:-1])
dp = [1] * (two_K << 1)
for i in range(two_K - 1, 0, -1):
	c = S[two_K - i - 1]
	if c == '1':
		dp[i] = dp[i << 1]
	elif c == '0':
		dp[i] = dp[(i << 1) + 1]
	else:
		dp[i] = dp[i << 1] + dp[(i << 1) + 1]
Q = int(input())
ans = []
for _ in range(Q):
	(match_number, winner) = sys.stdin.readline().strip().split()
	match_number = int(match_number) - 1
	S[match_number] = winner
	i = two_K - match_number - 1
	while i:
		c = S[two_K - i - 1]
		if c == '1':
			dp[i] = dp[i << 1]
		elif c == '0':
			dp[i] = dp[(i << 1) + 1]
		else:
			dp[i] = dp[i << 1] + dp[(i << 1) + 1]
		i //= 2
	ans.append(dp[1])
for a in ans:
	print(a)