Bishwock is a chess figure that consists of three squares resembling an "L-bar". This figure can be rotated by 90, 180 and 270 degrees so it can have four possible states:

 

XX   XX   .X   X.

X.   .X   XX   XX

 

Bishwocks don't attack any squares and can even occupy on the adjacent squares as long as they don't occupy the same square. 

Vasya has a board with $2\times n$ squares onto which he wants to put some bishwocks. To his dismay, several squares on this board are already occupied by pawns and Vasya can't put bishwocks there. However, pawns also don't attack bishwocks and they can occupy adjacent squares peacefully.

Knowing the positions of pawns on the board, help Vasya to determine the maximum amount of bishwocks he can put onto the board so that they wouldn't occupy the same squares and wouldn't occupy squares with pawns.


-----Input-----

The input contains two nonempty strings that describe Vasya's board. Those strings contain only symbols "0" (zero) that denote the empty squares and symbols "X" (uppercase English letter) that denote the squares occupied by pawns. Strings are nonempty and are of the same length that does not exceed $100$.


-----Output-----

Output a single integer — the maximum amount of bishwocks that can be placed onto the given board.


-----Examples-----
Input
00
00

Output
1
Input
00X00X0XXX0
0XXX0X00X00

Output
4
Input
0X0X0
0X0X0

Output
0
Input
0XXX0
00000

Output
2

Difficulty: interview

Starter code:

Solutions:
f = []
for i in range(2):
    f.append(list(input()))


answer = 0

n = len(f[0])
for i in range(n):
    if f[0][i] == f[1][i] == '0' and i + 1 < n:
        if f[0][i + 1] == '0':
            answer += 1
            f[0][i + 1] = 'X'
        elif f[1][i + 1] == '0':
            answer += 1
            f[1][i + 1] = 'X'

    elif (f[1][i] == '0' or f[0][i] == '0') and i + 1 < n and f[0][i + 1] == f[1][i + 1] == '0':
        answer += 1
        f[0][i + 1] = f[1][i + 1] = 'X'


print(answer)


3

def o(c):
    return c == '0'


def solve(A, B, N):
    A += 'XXX'
    B += 'XXX'

    i = 0
    c = 0
    while i < N:
        if (o(A[i]) and o(A[i + 1]) and o(A[i + 2])
            and o(B[i]) and o(B[i + 1]) and o(B[i + 2])):
            c += 2
            i += 3
            continue

        x = len([x for x in [o(A[i]), o(A[i + 1]), o(B[i]), o(B[i + 1])] if x])
        if x >= 3:
            c += 1
            i += 2
            continue

        i += 1

    return c


def main():
    A = input()
    B = input()
    N = len(A)
    assert len(B) == N
    print(solve(A, B, N))


def __starting_point():
    main()

__starting_point()

first = input()
second = input()
adad = list()
for i in range(len(first)):
	num = 0
	if first[i] == '0':
		num += 1
	if second[i] == '0':
		num += 1
	adad.append(num)

cnt = 0
last_fill = -1
for i in range(1, len(adad)):
	if adad[i] + adad[i-1] == 3:
		cnt += 1
		adad[i] = adad[i-1] = 0
	elif adad[i] + adad[i-1] == 4:
		cnt += 1
		adad[i] = 1
		adad[i-1] = 0
print(cnt)


s=input()
t=input()
dp=[]
n=len(s)
a=[]
b=[]
for i in range(n+1):
    dp.append((0,0))
for i in range(n):
    a.append(s[i])
    b.append(t[i])
ans=0
for i in range(n):
    if a[i]=='0' and b[i]=='0':
        if i>0 and (a[i-1]=='0' or b[i-1]=='0'):
            if a[i-1]=='0':
                a[i]=b[i]=a[i-1]='X'
                ans+=1
            elif b[i-1]=='0':
                a[i]=b[i]=b[i-1]='X'
                ans+=1
        elif i+1<n:
            if a[i+1]=='0':
                a[i]=b[i]=a[i+1]='X'
                ans+=1
            elif b[i+1]=='0':
                a[i]=b[i]=b[i+1]='X'
                ans+=1
print(ans)


S1 = input()
S2 = input()

L = len(S1)

memo = {}
def dfs(i, p1, p2):
    if i == L:
        return 0
    key = (i, p1, p2)
    if key in memo:
        return memo[key]
    r = 0
    if S1[i] == S2[i] == '0':
        if p1 > 0 or p2 > 0:
            if p1 > 0 < p2:
                r = max(dfs(i+1, 1, 0), dfs(i+1, 0, 1)) + 1
            else:
                r = dfs(i+1, 0, 0) + 1
        else:
            r = dfs(i+1, 1, 1)
    elif S1[i] == '0':
        if p1 > 0 and p2 > 0:
            r = dfs(i+1, 0, 0) + 1
        else:
            r = dfs(i+1, 1, 0)
    elif S2[i] == '0':
        if p1 > 0 and p2 > 0:
            r = dfs(i+1, 0, 0) + 1
        else:
            r = dfs(i+1, 0, 1)
    else:
        r = dfs(i+1, 0, 0)
    memo[key] = r
    return r
print(dfs(0, 0, 0))


a2 = input()
b2 = input()
a = []
b = []
for i in range(len(a2)):
    a.append(a2[i])
    b.append(b2[i])
k = 0
for i in range(len(a)):
    if i == 0 and (len(a) > 1):
        if a[0] == '0' and b[0] == '0' and a[1] == '0':
            a[0] = 'X'
            b[0] = 'X'
            a[1] = 'X'
            k += 1
        elif a[0] == '0' and b[0] == '0' and b[1] == '0':
            a[0] = 'X'
            b[0] = 'X'
            b[1] = 'X'
            k += 1
    elif i == len(a) - 1 and (len(a) > 1):
        if a[i] == '0' and b[i] == '0' and a[i - 1] == '0':
            a[i] = 'X'
            b[i] = 'X'
            a[i - 1] = 'X'
            k += 1
        elif a[i] == '0' and b[i] == '0' and b[i - 1] == '0':
            a[i] = 'X'
            b[i] = 'X'
            b[i - 1] = 'X'
            k += 1
    elif (len(a) > 1):
        if a[i] == '0' and b[i] == '0' and a[i - 1] == '0':
            a[i] = 'X'
            b[i] = 'X'
            a[i - 1] = 'X'
            k += 1
        elif a[i] == '0' and b[i] == '0' and b[i - 1] == '0':
            a[i] = 'X'
            b[i] = 'X'
            b[i - 1] = 'X'
            k += 1
        elif a[i] == '0' and b[i] == '0' and a[i + 1] == '0':
            a[i] = 'X'
            b[i] = 'X'
            a[i + 1] = 'X'
            k += 1
        elif a[i] == '0' and b[i] == '0' and b[i + 1] == '0':
            a[i] = 'X'
            b[i] = 'X'
            b[i + 1] = 'X'
            k += 1
    else:
         k = 0
print(k)

        


topboard = list(input())
botboard = list(input())

bish = 0
left = 0
while left + 1 < len(topboard):
    if topboard[left] == '0' and botboard[left] == '0':
        if topboard[left+1] == '0':
            bish += 1
            topboard[left] = 'X'
            topboard[left+1] = 'X'
            botboard[left] = 'X'
        elif botboard[left+1] == '0':
            bish += 1
            topboard[left] = 'X'
            botboard[left] = 'X'
            botboard[left+1] = 'X'
    elif topboard[left+1] == '0' and botboard[left+1] == '0':
        if topboard[left] == '0':
            bish += 1
            topboard[left] = 'X'
            topboard[left+1] = 'X'
            botboard[left+1] = 'X'
        elif botboard[left] == '0':
            bish += 1
            topboard[left+1] = 'X'
            botboard[left] = 'X'
            botboard[left+1] = 'X'

    left += 1

print(bish)


a = []
a.append(input())
a.append(input())
dp = [-200] * 4
dp[1 * (a[0][0] == 'X') + 2 * (a[1][0] == 'X')] = 0
for i in range(1, len(a[0])):
	odp = dp
	dp = [-200] * 4
	state = 1 * (a[0][i] == 'X') + 2 * (a[1][i] == 'X')
	for last_state in range(4):
		dp[state] = max(dp[state], odp[last_state])
		if last_state != 3 and state == 0:
			dp[3] = max(dp[3], odp[last_state] + 1)
		if last_state == 0:
			if ((~state) & 1):
				dp[state + 1] = max(dp[state + 1], odp[last_state] + 1)
			if ((~state) & 2):
				dp[state + 2] = max(dp[state + 2], odp[last_state] + 1)
print(max(max(dp[0], dp[1]), max(dp[2], dp[3])))

s = [input(), input()]
pc = [[s[0][i],s[1][i]].count('0') for i in range(len(s[0]))]
ans = 0
for i in range(len(pc) - 1):
  if pc[i] >= 2 and pc[i + 1] >= 1:
    ans += 1
    pc[i] -= 2
    pc[i + 1] -= 1
  elif pc[i] >= 1 and pc[i + 1] >= 2:
    ans += 1
    pc[i] -= 1
    pc[i + 1] -= 2
print(ans)


a=list(input())
b=list(input())
n=len(a)
ans=0
for i in range(n-1):
    if(a[i+1]=='0' and a[i]=='0' and b[i]=='0'):
        ans+=1
        a[i]=a[i+1]=b[i]='X'
    elif(b[i+1]=='0' and a[i]=='0' and b[i]=='0'):
        ans+=1
        a[i]=b[i+1]=b[i]='X'
    elif(b[i+1]=='0' and a[i+1]=='0' and b[i]=='0'):
        ans+=1
        a[i+1]=b[i+1]=b[i]='X'
    elif(b[i+1]=='0' and a[i+1]=='0' and a[i]=='0'):
        ans+=1
        a[i+1]=b[i+1]=a[i]='X'
print(ans)

s1=input()
s2=input()
dp=[0 for i in range(len(s1))]
if (s1[0]==s2[0]) and (s1[0]=='0'):
    r=2
elif (s1[0]==s2[0]) and (s1[0]=='X'):
    r=0
else:
    r=1
for i in range(1,len(s1)):
    if (s1[i]==s2[i]) and (s1[i]=='X'):
        dp[i]=dp[i-1]
        r=0
    elif (s1[i]!=s2[i]) and (r<=1):
        dp[i]=dp[i-1]
        r=1
    elif ((s1[i]==s2[i]) and (s1[i]=='0')):
        if r==2:
            dp[i]=dp[i-1]+1
            r=1
        elif r==1:
            dp[i]=dp[i-1]+1
            r=0
        else:
            dp[i]=dp[i-1]
            r=2
    else:
        dp[i]=dp[i-1]+1
        r=0
print(dp[len(s1)-1])
        
        



board = []
board.append(input())
board.append(input())

n = len(board[0])

dp = [[0 for _ in range(n)] for _ in range(4)]

inf = float('-inf')

if board[0][0] == 'X':
    dp[0][0] = inf
    dp[2][0] = inf
if board[1][0] == 'X':
    dp[0][0] = inf
    dp[1][0] = inf


#print([dp[j][0] for j in range(4)])
for i in range(1, n):
    prev_best = max(dp[j][i-1] for j in range(4))
    for j in range(4):
        dp[j][i] = prev_best
    if board[0][i] != 'X' or board[1][i] != 'X':
        dp[3][i] = max(dp[3][i], dp[0][i-1] + 1)
    if board[0][i] != 'X' and board[1][i] != 'X':
        dp[1][i] = max(dp[1][i], dp[0][i-1] + 1)
        dp[2][i] = max(dp[2][i], dp[0][i-1] + 1)
        dp[3][i] = max(dp[3][i], dp[1][i-1] + 1, dp[2][i-1] + 1)
    if board[0][i] == 'X':
        dp[0][i] = inf
        dp[2][i] = inf
    if board[1][i] == 'X':
        dp[0][i] = inf
        dp[1][i] = inf
    #print([dp[j][i] for j in range(4)])

print(max(max(dp[i][-1] for i in range(4)), 0))


a = [list(input()) for _ in range(2)]
n = 0
for i in range(len(a[0])):
    bljet = 0
    if a[0][i] == a[1][i] and a[0][i] == '0':
        
        if i > 0:
            if a[0][i-1] == '0':
                a[0][i-1] = 'X'
                a[0][i] = 'X'
                a[1][i] = 'X'
                bljet = 1
            if not bljet and a[1][i-1] == '0':
                a[1][i-1] = 'X'
                a[0][i] = 'X'
                a[1][i] = 'X'
                bljet = 1
        if i+1 < len(a[0]):
            if not bljet and a[0][i+1] == '0':
                a[0][i+1] = 'X'
                a[0][i] = 'X'
                a[1][i] = 'X'
                bljet = 1
            if not bljet and a[1][i+1] == '0':
                a[1][i+1] = 'X'
                a[0][i] = 'X'
                a[1][i] = 'X'
                bljet = 1
        #print(a[0])
        #print(a[1])
        
    if bljet:
        n += 1
print(n)


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

a = [list(input()), list(input())]
ans = 0
n = len(a[0])

i = 0
while i + 1 < n:
	cnt = sum(c == 'X' for c in [a[0][i], a[1][i], a[0][i + 1], a[1][i + 1]])
	if cnt > 1:
		i += 1
		continue
	if cnt == 1:
		ans += 1
		i += 2
		continue
	ans += 1
	a[0][i + 1] = 'X'
	i += 1
print(ans)



A = []
A += [input()]
A += [input()]

n = len(A[0])

B = [[0 for _ in range(4)] for _ in range(n + 1)]

B[0][0] = -1000
B[0][1] = -1000
B[0][2] = -1000
B[0][3] = 0

for i in range(1, n + 1):
    # 0
    if A[1][i - 1] == 'X':
        B[i][0] = -1000
    elif A[0][i - 1] == 'X':
        B[i][0] = max([B[i - 1][j] for j in range(4)])
    else:
        B[i][0] = max([B[i - 1][2] + 1] + [B[i - 1][0],
                                           B[i - 1][1], B[i - 1][3]])

    # 1
    if A[0][i - 1] == 'X':
        B[i][1] = -1000
    elif A[1][i - 1] == 'X':
        B[i][1] = max([B[i - 1][j] for j in range(4)])
    else:
        B[i][1] = max([B[i - 1][2] + 1] + [B[i - 1][0],
                                           B[i - 1][1], B[i - 1][3]])

    # 3
    if A[0][i - 1] == 'X' or A[1][i - 1] == 'X':
        B[i][2] = -1000
    else:
        B[i][2] = max([B[i - 1][j] for j in range(4)])

    # 4
    if A[0][i - 1] == 'X' and A[1][i - 1] == 'X':
        B[i][3] = max([B[i - 1][j] for j in range(4)])
    elif A[0][i - 1] == 'X':
        B[i][3] = B[i - 1][2] + 1
    elif A[1][i - 1] == 'X':
        B[i][3] = B[i - 1][2] + 1
    else:
        B[i][3] = max([B[i - 1][j] for j in range(3)]) + 1



print(max([B[n][j] for j in range(4)]))


l1 = list(input().strip())
l2 = list(input().strip())
r = 0

for i in range(len(l1) - 1):
    if l1[i] == '0' and l2[i] == '0':
        if l2[i+1] == '0':
            l1[i] = 'X'
            l2[i] = 'X'
            l2[i+1] = 'X'
            r += 1
        elif l1[i+1] == '0':
            l1[i] = 'X'
            l2[i] = 'X'
            l1[i+1] = 'X'
            r += 1
    elif l1[i] == '0':
        if l1[i+1] == '0' and l2[i+1] == '0':
            l1[i] = 'X'
            l1[i+1] = 'X'
            l2[i+1] = 'X'
            r += 1
    elif l2[i] == '0':
        if l1[i+1] == '0' and l2[i+1] == '0':
            l2[i] = 'X'
            l1[i+1] = 'X'
            l2[i+1] = 'X'
            r += 1

print(r)


def go():
    matrix = []
    matrix.append(list(i for i in input()))
    matrix.append(list(i for i in input()))
    c = 0
    for i in range(len(matrix[0]) - 1):
        if matrix[0][i] == '0' and matrix[1][i] == '0':
            if matrix[0][i + 1] == '0':
                matrix[0][i] = 'X'
                matrix[1][i] = 'X'
                matrix[0][i + 1] = 'X'
                c += 1
            elif matrix[1][i + 1] == '0':
                matrix[0][i] = 'X'
                matrix[1][i] = 'X'
                matrix[1][i + 1] = 'X'
                c += 1
        elif matrix[0][i] == '0':
            if matrix[0][i + 1] == '0' and matrix[1][i + 1] == '0':
                matrix[0][i] = 'X'
                matrix[0][i + 1] = 'X'
                matrix[1][i + 1] = 'X'
                c += 1
        elif matrix[1][i] == '0':
            if matrix[0][i + 1] == '0' and matrix[1][i + 1] == '0':
                matrix[1][i] = 'X'
                matrix[0][i + 1] = 'X'
                matrix[1][i + 1] = 'X'
                c += 1
    return c

print(go())


r1=input()
r2=input()
n=len(r1)
l=[0]
for i in range(n):
	if r1[i]=='0':
		if r2[i]=='0':
			l.append(2)
		else:
			l.append(1)
	else:
		if r2[i]=='X':
			l.append(0)
		else:
			l.append(-1)
l.append(0)
s=len(l)
count=0
u=1
e=1
while(u<s-1):
	if l[u]==2 and e==1:
		if l[u+1]==2:
			e=2
			u=u+1
			continue
		elif (l[u+1]==1 or l[u+1]==-1):
			count=count+1
			u=u+2
			continue
		else:
			u=u+2
			continue
	if l[u]==2 and e==2:
		if l[u+1]==2:
			count=count+2
			u=u+2
			e=1
			continue
		else:
			count=count+1
			u=u+1
			e=1
			continue
	if l[u]==1 or l[u]==-1:
		if l[u+1]==2:
			count=count+1
			u=u+2
			continue
		else:
			u=u+1
			continue
	if l[u]==0:
		u=u+1
print (count)

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

ss = [input().strip(), input().strip()]
s = [a + b for a, b in zip(ss[0], ss[1])] + ['XX']
n = len(s)

def solve(i, j):
    c = 0
    k = i
    while k < j - 1:
        if s[k] == '0X' and s[k + 1] == '00':
            c += 1
            k += 2
        elif s[k] == 'X0' and s[k + 1] == '00':
            c += 1
            k += 2
        elif s[k] == '00' and s[k + 1] == 'X0':
            c += 1
            k += 2
        elif s[k] == '00' and s[k + 1] == '0X':
            c += 1
            k += 2
        elif s[k] == '00' and s[k + 1] == '00':
            c += 1
            s[k + 1] = '0X'
            k += 1
        else:
            k += 1
    return c

i = 0
c = 0
while i < n:
    if s[i] == 'XX':
        i += 1
        continue
    j = i + 1
    while s[j] != 'XX':
        j += 1
    c += solve(i, j)
    i = j
print(c)

def main():
    a, b = [i for i in input()], [i for i in input()]
    l = len(a)
    c = 0
    for i in range(l - 1):
        if a[i] == '0':
            if b[i] == '0':
                if a[i + 1] == '0':
                    c += 1
                    a[i], b[i], a[i + 1] = 1, 1, 1
                elif b[i + 1] == '0':
                    c += 1
                    a[i], b[i], b[i + 1] = 1, 1, 1
            elif a[i + 1] == '0' and b[i + 1] == '0':
                c += 1
                a[i], a[i + 1], b[i + 1] = 1, 1, 1
        elif b[i] == '0' and b[i + 1] == '0' and a[i + 1] == '0':
            c += 1
            b[i], a[i + 1], b[i + 1] = 1, 1, 1
    print(c)
    return 0
main()


#!/usr/bin/env python3

ss = [input().strip() for _ in range(2)]
n = len(ss[0])

cnt = 0
had1 = False
had2 = False

for i in range(n):
	ccur = sum(s[i] == '0' for s in ss)
	if ccur == 2:
		if had1:
			cnt += 1
			had1 = False
		elif had2:
			cnt += 1
			had2 = False
			had1 = True
		else:
			had2 = True
	elif ccur == 1:
		if had1:
			had1 = True
		elif had2:
			cnt += 1
			had2 = False
		else:
			had1 = True
	else:
		had1 = False
		had2 = False
	
print (cnt)


l1=list(str(input()))
l2=list(str(input()))
n=len(l1)
count=0
for i in range(n-1):
    if l1[i]=='0' and l1[i+1]=='0':
        if l2[i]=='0':
            l1[i],l1[i+1],l2[i]='X','X','X'
            count+=1
        elif l2[i+1]=='0':
            l1[i],l1[i+1],l2[i+1]='X','X','X'
            count+=1
    if l2[i]=='0' and l2[i+1]=='0':
        if l1[i]=='0':
            l2[i],l2[i+1],l1[i]='X','X','X'
            count+=1
        elif l1[i+1]=='0':
            l2[i],l2[i+1],l1[i+1]='X','X','X'
            count+=1
print(count)

s1 = input()
s2 = input()

desk = [list(s1), list(s2)]

ln = len(s1)
ans = 0


def need(i):
    return [desk[0][i: i + 2], desk[1][i: i + 2]]


for i in range(ln - 1):
    if need(i) == [['0', '0'], ['0', '0']] or need(i) == [['0', '0'], ['0', 'X']]:
        desk[0][i] = 'X'
        desk[0][i + 1] = 'X'
        desk[1][i] = 'X'

    elif need(i) == [['0', '0'], ['X', '0']]:
        desk[0][i] = 'X'
        desk[0][i + 1] = 'X'
        desk[1][i + 1] = 'X'

    elif need(i) == [['0', 'X'], ['0', '0']]:
        desk[0][i] = 'X'
        desk[1][i] = 'X'
        desk[1][i + 1] = 'X'

    elif need(i) == [['X', '0'], ['0', '0']]:
        desk[0][i + 1] = 'X'
        desk[1][i] = 'X'
        desk[1][i + 1] = 'X'

    else:
        continue

    ans += 1

print(ans)



l1=[]
l2=[]
for i in input():
	l1.append(i)
for i in input():
	l2.append(i)
count=0	
c=0
while c<len(l1)-1:
	newli=[l1[c],l1[c+1],l2[c],l2[c+1]]
	try:
		if l1[c]==l1[c+1]==l1[c+2]==l2[c]==l2[c+1]==l2[c+2]=='0':
			count+=2
			c+=3
			continue
	except:
		pass
	if newli.count('0')>=3:
		count+=1
		c+=2
	else:
		c+=1	
print(count)