Mike and some bears are playing a game just for fun. Mike is the judge. All bears except Mike are standing in an n × m grid, there's exactly one bear in each cell. We denote the bear standing in column number j of row number i by (i, j). Mike's hands are on his ears (since he's the judge) and each bear standing in the grid has hands either on his mouth or his eyes. [Image] 

They play for q rounds. In each round, Mike chooses a bear (i, j) and tells him to change his state i. e. if his hands are on his mouth, then he'll put his hands on his eyes or he'll put his hands on his mouth otherwise. After that, Mike wants to know the score of the bears.

Score of the bears is the maximum over all rows of number of consecutive bears with hands on their eyes in that row.

Since bears are lazy, Mike asked you for help. For each round, tell him the score of these bears after changing the state of a bear selected in that round. 


-----Input-----

The first line of input contains three integers n, m and q (1 ≤ n, m ≤ 500 and 1 ≤ q ≤ 5000).

The next n lines contain the grid description. There are m integers separated by spaces in each line. Each of these numbers is either 0 (for mouth) or 1 (for eyes).

The next q lines contain the information about the rounds. Each of them contains two integers i and j (1 ≤ i ≤ n and 1 ≤ j ≤ m), the row number and the column number of the bear changing his state.


-----Output-----

After each round, print the current score of the bears.


-----Examples-----
Input
5 4 5
0 1 1 0
1 0 0 1
0 1 1 0
1 0 0 1
0 0 0 0
1 1
1 4
1 1
4 2
4 3

Output
3
4
3
3
4

Difficulty: interview

Starter code:

Solutions:
def cons(l):
    m = 0
    res = 0
    for v in l:
        if v:
            res += 1
            if res > m:
                m = res
        else:
            res = 0
    return m

n, m, q = list(map(int, input().split()))
grid = []
curr = [0] * n
for i in range(n):
    grid.append(list(map(int, input().split())))
    curr[i] = cons(grid[i])

for _ in range(q):
    i, j = list(map(int, input().split()))
    i -= 1
    j -= 1
    grid[i][j] = 0 if grid[i][j] else 1
    curr[i] = cons(grid[i])
    print(max(curr))


n, m, q = list(map(int, input().split()))

s = []
t = []

def getMax(line):
    cur = 0
    res = 0
    for v in line:
        if v == 1:
            cur += 1
        else:
            res = max(res, cur)
            cur = 0
    res = max(res, cur)
    return res

for i in range(n):
    si = list(map(int, input().split()))
    s.append(si)
    t.append(getMax(si))

# res = max(t)

# print(t)

for qi in range(q):
    i, j = list(map(int, input().split()))
    s[i - 1][j - 1] = int(not s[i - 1][j - 1])
    t[i - 1] = getMax(s[i - 1])
    # print(t)
    res = max(t)
    print(res)


import math
def linescore(line):
    acc = 0
    ret = 0
    for eye in line:
        if eye:
            acc += 1
            ret = max(ret, acc)
        else:
            acc = 0
    return ret
    
def main():
    items = input().split()
    n = int(items[0])
    m = int(items[1])
    q = int(items[2])
    e = [[None for _ in range(m)] for _ in range(n)]
    ls = [0 for _ in range(n)]
    for i in range(n):
        items = input().split()
        for j in range(m):
            e[i][j] = (items[j]=='1')
    for i in range(n):
        ls[i] = linescore(e[i])
    for qi in range(q):
        items = input().split()
        x = int(items[0])-1
        y = int(items[1])-1
        e[x][y] = not e[x][y]
        ls[x] = linescore(e[x])
        print(max(ls))
        
def __starting_point():
    main()

__starting_point()

import math,string,itertools,fractions,heapq,collections,re,array,bisect
from itertools import chain, dropwhile, permutations, combinations
from collections import defaultdict

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

def get_score(x):
    b = 0
    best = 0
    running = 0
    for i,v in enumerate(x):
        if v==1:
            if running:
                b += 1
            else:
                b = 1
            running = 1
        else:
            if running:
                if b > best:
                    best = b
            running = 0
    if b > best:
        best = b
    return best


def main_input(info=0):
    n,m,q = VI()
    g = list(range(n))
    sc = list(range(n))
    for i in range(n):
        g[i] = VI() # m elem
        sc[i] = get_score(g[i])
    r = list(range(q))
    for k in range(q):
        i,j = VI() # i,j - 2 elem
        i,j = i-1, j-1
        g[i][j] = 1 - g[i][j]
        sc[i] = get_score(g[i])
        print(max(sc))


def __starting_point():
    main_input()

__starting_point()


n, m, q = [int(c) for c in input().split()]

matrix = []
for i in range(n):

    matrix.append([int(c) for c in input().split()])

maxperrow = []

for a in range(n):
    maxrow = 0
    maxmax = 0
    for b in range(m):
        if matrix[a][b] == 1:
            maxrow += 1
            if maxrow > maxmax:
                maxmax = maxrow
        else:
            maxrow = 0
    maxperrow.append(maxmax)

winner = []
for step in range(q):
    i, j = [int(c) for c in input().split()]
    matrix[i-1][j-1] = 1 - matrix[i-1][j-1]

    maxmax = 0

    maxrow = 0
    for b in range(m):
        if matrix[i-1][b] == 1:
            maxrow += 1
            if maxrow > maxmax:
                maxmax = maxrow
        else:
            maxrow = 0
    maxperrow[i-1] = maxmax
    winner.append(max(maxperrow))


for w in winner:
    print(w)

__author__ = 'Andrey'


def retest(row):
    nonlocal table
    row_n = table[row]
    m_ax = 0
    curr = 0
    for item in row_n:
        if item == 1:
            curr += 1
        if item == 0:
            m_ax = max(curr, m_ax)
            curr = 0
    m_ax = max(curr, m_ax)
    return m_ax


n, m, q = list(map(int, input().split()))
table = []
for x in range(n):
    table.append(list(map(int, input().split())))
maximums = []
for y in range(n):
    maximums.append(retest(y))
for z in range(q):
    i, j = list(map(int, input().split()))
    table[i - 1][j - 1] = 1 - table[i - 1][j - 1]
    maximums[i - 1] = retest(i - 1)
    print(max(maximums))


a = list()
b = list()
n, m, q = [int(s) for s in input().split()]
for i in range(n):
    a.append([s for s in input().split()])
    b.append(max([len(s) for s in "".join(a[i]).split('0')]))
for i in range(q):
    p, o = [int(s)-1 for s in input().split()]
    a[p][o] = str(1-int(a[p][o]))
    b[p] = max([len(s) for s in "".join(a[p]).split('0')])
    print(max(b))


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time
def res(row):
    ans = 0
    buf = 0
    for i in row:
        if i == 1:
            buf += 1
        else:
            if buf !=0:
                ans = max(ans, buf)
                buf = 0
    ans = max(ans, buf)
    return ans

(n, m, q) = (int(i) for i in input().split())
desk  = []
score = []

start = time.time()

for j in range(n):
    row = [ int(i) for i in input().split()]
    desk.append(row)
    score.append(res(row))

ans = []
for k in range(q):
    (i, j) = (int(l) for l in input().split())
    i -= 1
    j -= 1
    desk[i][j] = 1 if desk[i][j] == 0 else 0
    score[i]=res(desk[i])
    ans.append(max(score))

for i in ans:
    print(i)
finish = time.time()
#print (finish - start), "sec"


n, m, q = list(map(int, input().split()))
a = [[]]
for i in range(n):
    a.append([0] + list(map(int, input().split())))
x, y = list(map(int, input().split()))
a[x][y] = (a[x][y] + 1) % 2
ma = 0
curr = 0
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i][j] == 0:
            ma = max(curr, ma)
            curr = 0
        else:
            curr += 1
    ma = max(ma, curr)
    curr = 0
res = 0
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i][j] == 0:
            if curr == ma: res += 1
            curr = 0
        else:
            curr += 1
    if curr == ma: res += 1
    curr = 0
print(ma)
for i in range(q - 1):
    x, y = list(map(int, input().split()))
    if a[x][y] == 1:
        j = y - 1
        here = 1
        while j >= 0 and a[x][j] == 1:
            j -= 1
            here += 1
        j = y + 1
        while j <= m and a[x][j] == 1:
            j += 1
            here += 1
        a[x][y] = 0
        if here == ma: res -=1
        if res >= 1: print(ma)
        else:
            ma = 0
            curr = 0
            for i in range(1, n + 1):
                for j in range(1, m + 1):
                    if a[i][j] == 0:
                        ma = max(curr, ma)
                        curr = 0
                    else:
                        curr += 1
                ma = max(ma, curr)
                curr = 0
            res = 0
            for i in range(1, n + 1):
                for j in range(1, m + 1):
                    if a[i][j] == 0:
                        if curr == ma: res += 1
                        curr = 0
                    else:
                        curr += 1
                if curr == ma: res += 1
                curr = 0
            print(ma)       
    else:
        a[x][y] = 1
        j = y - 1
        here = 1
        while j >= 0 and a[x][j] == 1:
            j -= 1
            here += 1
        j = y + 1
        while j <= m and a[x][j] == 1:
            j += 1
            here += 1      
        if here > ma:
            ma = here
            res = 1
        elif here == ma:
            res += 1
        print(ma)
        
        


n, m, q = list(map(int, input().split()))
def csum(row):
    return max(list(map(len, "".join(map(str, row)).split("0"))))

grid = ["".join(input().split()) for i in range(n)]
score = [max(list(map(len, row.split("0")))) for row in grid]
for i in range(q):
    i, j = list(map(int, input().split()))
    row = grid[i-1]
    row = row[:j-1] + ("1" if row[j-1] == "0" else "0") + row[j:]
    grid[i-1] = row
    score[i-1] = csum(row)
    print(max(score))


n, m, q = [int(token) for token in input().split()]

g = []

for _ in range(n):
    row = [int(token) for token in input().split()]
    g.append(row)


def row_score(row):
    max_count = 0
    count = 0
    for item in row:
        if item == 1:
            count += 1
        else:
            count = 0
        max_count = max(max_count, count)
    return max_count


row_cache = [row_score(row) for row in g]


def score():
    return max(
        rc for rc in row_cache
    )


for turn in range(q):
    i, j = [int(token) - 1 for token in input().split()]
    g[i][j] = 1 - g[i][j]
    row_cache[i] = row_score(g[i])
    print(score())

values = []


def get_max(row):
    total = 0
    max_vv = 0

    for x in row:
        if x == 1:
            max_vv += 1
        else:
            if max_vv > total:
                total = max_vv
            max_vv = 0

    if max_vv > total:
        total = max_vv

    return total


def __starting_point():
    n, m, q = map(int, input().split())
    rows = []

    for i in range(n):
        rows.append(list(map(int, input().split())))
        values.append(get_max(rows[-1]))

    for i in range(q):
        i, j = map(int, input().split())
        i -= 1
        j -= 1

        rows[i][j] = 1 - rows[i][j]
        values[i] = get_max(rows[i])

        print(max(values))
__starting_point()

n, m, q = [int(x) for x in input().split()]
data = []
saveCount = []
globalMax = 0
globalMaxIndex = -1
for i in range(n):
    temp = [int(x) for x in input().split()]
    mx = 0
    curEyes = 0
    for j in range(m):
        if temp[j] == 1:
            curEyes += 1
            if curEyes > mx:
                mx = curEyes
        else:
            curEyes = 0
    saveCount.append(mx)
    if mx > globalMax:
        globalMaxIndex = i
        globalMax = mx
    data.append(temp)

for i in range(q):
    y,x = [int(c)-1 for c in input().split()]
    data[y][x] = 0 if data[y][x] else 1
    mx = 0
    curEyes = 0
    if y == globalMaxIndex:
        saveCount[y] = 0
        globalMax = 0
        for j in range(n):
            if saveCount[j] > globalMax:
                globalMax = saveCount[j]
                globalMaxIndex = j
    for j in range(m):
        if data[y][j] == 1:
            curEyes += 1
            if curEyes > mx:
                mx = curEyes
        else:
            curEyes = 0
    if mx > globalMax:
        print(mx)
        globalMax = mx
        globalMaxIndex = y
    else:
        print(globalMax)
    saveCount[y] = mx


from io import StringIO

import sys
data = sys.stdin

def score_line(row):
    score = 0
    max_score = 0
    combo = False
    for b in row:
        if b == 1:
            if combo:
                score += 1
            else:
                score = 1
                combo = True
        else:
            score = 0
            combo = False
        
        max_score = max(score, max_score)
    return max_score
        
rows = []

n, m, q = map(int, data.readline().split(' '))
for i in range(n):
    rows.append(list(map(int, data.readline().split(' '))))

row_scores = list(map(score_line, rows))
    
for i in range(q):
    r, c  = map(int, data.readline().split(' '))
    rows[r-1][c-1] = 1 - rows[r-1][c-1]
    row_scores[r-1] = score_line(rows[r-1])
    print(max(row_scores))

n, m, q = map(int, input().split(" "))
l = []

def maxx(l):
    cmax = 0
    count = 0
    for i in range(len(l)):
        for j in range(len(l[i])):
            if l[i][j] == 1:
                count += 1
                if j == (len(l[i])-1) and count > cmax:
                    cmax = count
            else:
                if count > cmax:
                    cmax = count
                count = 0
        count = 0 
    return cmax   

def maxi(l):
    c = 0
    cmax = 0
    for i in range(len(l)):
        if l[i] == 1:
            c+=1
            if c > cmax:
                cmax = c
        else:
            c = 0
    return cmax
        
for i in range(n):
    li = list(map(int, input().split(" ")))
    l.append(li)

foo = []

for i in range(len(l)):
    foo.append(maxi(l[i]))

for i in range(q):
    i, j = map(int, input().split(" "))
    l[i-1][j-1] = 1 - l[i-1][j-1]
    foo[i-1] = maxi(l[i-1])
    
    print(max(foo))   

import re

def maxString(a,i,n):
	s2 = ''.join(a[i])
	if '1' not in s2:
		return 0
	r = len(max(re.findall("1+",s2),key=len))
	return r

def flip(x):
	if(x == '1'):
		return '0'
	else:
		return '1'

n,m,q = map(int,input().split())

a = []
x = []

for i in range(n):
	x = list(input().split())
	a.append(x)

y = []

for i in range(n):
	y.append(maxString(a,i,n))

#print(y)
z = max(y)
r = y.index(z)

for i in range(q):
	x1,y1 = map(int,input().split())
	a[x1-1][y1-1] = flip(a[x1-1][y1-1])
	y[x1-1] = maxString(a,x1-1,n)
	z = max(y)
	print(z)

n, m, q = [int(i) for i in input().split()]
t = []
u = []
for i in range(n):
    t.append([int(i) for i in input().split()])
    s = 0
    o = 0
    for k in t[-1]:
        if k == 1:
            s+=1
            o = max(s, o)
        else:
            s = 0
    u.append(o)
answer = []
for i in range(q):
    a, b = [int(i)-1 for i in input().split()]
    if t[a][b] == 1:
        t[a][b] = 0
    else:
        t[a][b] = 1
    s = 0
    o = 0
    for k in t[a]:
        if k == 1:
            s+=1
            o = max(s, o)
        else:
            s = 0
    u[a] = o
    answer.append(max(u))
for i in answer:
    print(i)


def func(a):
    s=0
    per= 0
    for i in range(len(a)):
        if a[i] == '1':
            
            per+=1
        else:
            s=max(s, per)
            per=0
    s=max(per, s)
    return s
def main(a):
    A= []
    B = [0] * int(a[0])
    for i in range(int(a[0])):
        A.append(input().split())
    for i in range(int(a[0])):
        B[i] = func(A[i])
    for i in range(int(a[2])):
        s = 0
        k = input().split()
        A[int(k[0]) - 1][int(k[1]) - 1] = str((int(A[int(k[0]) - 1][int(k[1]) - 1]) + 1) % 2)
        B[int(k[0]) - 1] = func(A[int(k[0]) - 1])
        for i in B:
            s = max(s, i)
        print(s)
a =input().split()
main(a)

def fff(i):
    nonlocal a
    nonlocal m
    t=0
    max=0
    for j in range(m+1):
        if a[i][j]==0:
            if t>max:
                max=t
            t=0
        else:
            t=t+1
    return max

n,m,q=list(map(int,input().split()))
a=[]
s=[]
for i in range(0,n):
    w=list(map(int,input().split()))
    w.append(0)
    a.append(w)
    s.append(fff(i))
for i in range(q):
    x,y=list(map(int, input().split()))
    a[x-1][y-1]=(a[x-1][y-1]+1)%2
    s[x-1]=fff(x-1)
    print(max(s))
        



def condMax(row):
    flag = False
    ret, cnt = 0, 0
    for x in row:
        if flag == False and x == 1:
            cnt = 1
            flag = True
        elif flag == True and x == 1:
            cnt += 1
        elif flag == True and x == 0:
            ret = max(cnt, ret)
            flag = False
    if flag == True:
        ret = max(cnt, ret)
    return ret

N, M, Q = list(map(int, input().split()))
board = [list(map(int, input().split())) for _ in range(N)]
rows = [condMax(row[:]) for row in board]
    
ans = max(rows)
for i in range(Q):
    i, j = [int(x)-1 for x in input().split()]
    board[i][j] ^= 1
    rows[i] = condMax(board[i][:])
    ans = max(rows)
    print(ans)


n, m, q = map(int, input().split())
def csum(row):
    return max(map(len, "".join(map(str, row)).split("0")))

grid = ["".join(input().split()) for i in range(n)]
score = [max(map(len, row.split("0"))) for row in grid]
for i in range(q):
    i, j = map(int, input().split())
    row = grid[i-1]
    row = row[:j-1] + ("1" if row[j-1] == "0" else "0") + row[j:]
    grid[i-1] = row
    score[i-1] = csum(row)
    print(max(score))

r=lambda:input().split()
g=lambda s:max(map(len,"".join(s).split('0')))
n,m,q=map(int,r())
a=[r() for _ in range(n)]
b=list(map(g,a))
for _ in range(q):
    x,y=map(int,r())
    a[x-1][y-1]=str(1-int(a[x-1][y-1]))
    b[x-1]=g(a[x-1])
    print(max(b))

def func(a):
    ans = 0
    an = 0
    for i in a:
        if i == 0:
            ans = max(ans, an)
            an = 0
        else:
            an += 1
    return max(ans, an)

n, m, q = (int(x) for x in input().split(' '))
a = [[int(x) for x in input().split()] for i in range(n)]
mas = [func(a[i]) for i in range(n)]
for _ in range(q):
    x, y = (int(i) - 1 for i in input().split(' '))
    a[x][y] = 1 if a[x][y] == 0 else 0
    mas[x] = func(a[x])
    print(max(mas))

def read_data():
    n, m, q = map(int, input().split())
    grid = []
    for i in range(n):
        grid.append(list(map(int, input().split())))
    qs = []
    for i in range(q):
        x, y = map(int, input().split())
        qs.append((x-1, y-1))
    return n, m, q, grid, qs


def max_cons(row):
    mc = 0
    tmp = 0
    for v in row:
        if v:
            tmp += 1
        else:
            if tmp > mc:
                mc = tmp
            tmp = 0
    return max(mc, tmp)


def solve(n, m, q, grid, qs):
    mcc = [max_cons(row) for row in grid]
    for x, y in qs:
        row = grid[x]
        row[y] = 1 - row[y]
        mcc[x] = max_cons(row)
        print(max(mcc))

param = read_data()
solve(*param)

rows, cols, changes_count = list(map(int, input().split()))

grid = [
    input().split() for _ in range(rows)
]

changes = [
    list(map(int, input().split())) for __ in range(changes_count)
]

max_line = [
    max(list(map(len, "".join(row).split("0")))) for row in grid
]

for r, c in changes:
    grid[r-1][c-1] = "0" if grid[r-1][c-1] == "1" else "1"
    max_line[r-1] = max(list(map(len, "".join(grid[r-1]).split("0"))))
    print(max(max_line))