Given a binary matrix of dimensions M * N. One can perform the given operation in the matrix.
	If the value of matrix[i][j] is 0, then traverse in the same direction and check the next value.
	If the value of matrix[i][j] is 1, then update matrix[i][j] to 0 and change the current direction from up, right, down, or left to the directions right, down, left, and up respectively.
Initially you start from cell(0, 0), moving in right direction.
The task is to find the first cell of the matrix  which leads to outside the matrix from the traversal of the given matrix from the cell (0, 0) by performing the operations.
Example 1:
Input:
matrix[][] = {{0,1},
              {1,0}}
Output: (1,1)
Explanation:
Example 2:
Input: 
matrix[][] = {{0, 1, 1, 1, 0},
                   {1, 0, 1, 0, 1},
              {1, 1, 1, 0, 0}}
Output: (2,0)
Your Task:
You don't need to read input or print anything. Complete the function endPoints() that take the matrix as input parameter and output the last cell before the pointer gets outside of the matrix.
Constrains:
1<= M, N <=1000
0<= matrix[i][j] <=1

Difficulty: EASY
Tags: Matrices

Data structures
Skill types: Data structures

Starter code:
#User function Template for python3



class Solution:

    def endPoints(self, matrix, m, n):

        ##code here



Solutions:
class Solution:

	def endPoints(self, matrix, m, n):
		di = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}
		d = 'right'
		i = j = 0
		while True:
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				if d == 'right':
					d = di['right']
				elif d == 'left':
					d = di['left']
				elif d == 'down':
					d = di['down']
				else:
					d = di['up']
			elif d == 'right':
				j += 1
				if j >= n:
					return (i, n - 1)
			elif d == 'left':
				j -= 1
				if j < 0:
					return (i, 0)
			elif d == 'down':
				i += 1
				if i >= m:
					return (m - 1, j)
			else:
				i -= 1
				if i < 0:
					return (0, j)


class Solution:

	def endPoints(self, mat, m, n):
		R = len(mat)
		C = len(mat[0])
		dire = 'R'
		i = j = 0
		(li, lj) = (0, 0)
		while i >= 0 and i < R and (j >= 0) and (j < C):
			if mat[i][j] == 1:
				mat[i][j] = 0
				if dire == 'R':
					dire = 'D'
				elif dire == 'U':
					dire = 'R'
				elif dire == 'D':
					dire = 'L'
				elif dire == 'L':
					dire = 'U'
			(li, lj) = (i, j)
			if dire == 'R':
				j += 1
			elif dire == 'U':
				i -= 1
			elif dire == 'D':
				i += 1
			elif dire == 'L':
				j -= 1
		return (li, lj)


class Solution:

	def endPoints(self, matrix, n, m):
		direction = {0: (0, 1), 1: (1, 0), 2: (0, -1), 3: (-1, 0)}
		i = 0
		j = 0
		go = 0
		while 0 <= i < n and 0 <= j < m:
			if matrix[i][j]:
				go += 1
				go %= 4
			matrix[i][j] = 0
			i += direction[go][0]
			j += direction[go][1]
		i -= direction[go][0]
		j -= direction[go][1]
		return (i, j)


class Solution:

	def endPoints(self, matrix, m, n):
		i = 0
		j = 0
		curser = 'right'
		while j < n and j >= 0 and (i < m) and (i >= 0):
			if matrix[i][j] == 0:
				if curser == 'right':
					j += 1
				elif curser == 'left':
					j -= 1
				elif curser == 'up':
					i -= 1
				elif curser == 'down':
					i += 1
			else:
				matrix[i][j] = 0
				if curser == 'up':
					curser = 'right'
					j += 1
				elif curser == 'down':
					curser = 'left'
					j -= 1
				elif curser == 'left':
					curser = 'up'
					i -= 1
				elif curser == 'right':
					curser = 'down'
					i += 1
		if i >= m:
			i = m - 1
		elif i < 0:
			i = 0
		elif j >= n:
			j = n - 1
		elif j < 0:
			j = 0
		return (i, j)


class Solution:

	def endPoints(self, matrix, m, n):

		def get(x, y, d):
			if d == 'R':
				return (x, y + 1)
			elif d == 'L':
				return (x, y - 1)
			elif d == 'U':
				return (x - 1, y)
			else:
				return (x + 1, y)

		def solve(x, y, d):
			if matrix[x][y] == 0:
				(nx, ny) = get(x, y, d)
				nd = d
			else:
				matrix[x][y] = 0
				if d == 'U':
					(nx, ny) = get(x, y, 'R')
					nd = 'R'
				elif d == 'R':
					(nx, ny) = get(x, y, 'D')
					nd = 'D'
				elif d == 'D':
					(nx, ny) = get(x, y, 'L')
					nd = 'L'
				elif d == 'L':
					(nx, ny) = get(x, y, 'U')
					nd = 'U'
			if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]):
				return solve(nx, ny, nd)
			else:
				return (x, y)
		return solve(0, 0, 'R')


class Solution:

	def endPoints(self, matrix, m, n):
		direction = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}
		(i, j) = (0, 0)
		curr = 'right'
		while True:
			if matrix[i][j] == 0:
				if curr == 'left':
					j -= 1
					if j < 0:
						return [i, j + 1]
				elif curr == 'right':
					j += 1
					if j > n - 1:
						return [i, j - 1]
				elif curr == 'down':
					i += 1
					if i > m - 1:
						return [i - 1, j]
				elif curr == 'up':
					i -= 1
					if i < 0:
						return [i + 1, j]
			else:
				matrix[i][j] = 0
				curr = direction[curr]


class Solution:

	def endPoints(self, matrix, m, n):
		dire = 'r'
		(i, j) = (0, 0)
		(x, y) = (0, 0)
		while True:
			if i >= m or i < 0 or j >= n or (j < 0):
				return [x, y]
			else:
				(x, y) = (i, j)
				if matrix[i][j] == 0:
					if dire == 'd':
						i += 1
					elif dire == 'u':
						i -= 1
					elif dire == 'l':
						j -= 1
					elif dire == 'r':
						j += 1
				else:
					if dire == 'r':
						dire = 'd'
						i += 1
					elif dire == 'u':
						dire = 'r'
						j += 1
					elif dire == 'd':
						dire = 'l'
						j -= 1
					else:
						dire = 'u'
						i -= 1
					matrix[x][y] = 0


class Solution:

	def isSafe(self, m, n, i, j):
		if i < 0 or j < 0 or i >= m or (j >= n):
			return False
		return True

	def endPoints(self, matrix, m, n):
		i = 0
		j = 0
		curr_d = 'r'
		new_d = {'r': 'd', 'l': 'u', 'u': 'r', 'd': 'l'}
		while self.isSafe(m, n, i, j):
			curr_i = i
			curr_j = j
			if matrix[curr_i][curr_j] == 1:
				turn = new_d[curr_d]
				matrix[curr_i][curr_j] = 0
				if turn == 'd':
					i += 1
				elif turn == 'u':
					i -= 1
				elif turn == 'r':
					j += 1
				elif turn == 'l':
					j -= 1
				curr_d = turn
			elif curr_d == 'd':
				i += 1
			elif curr_d == 'u':
				i -= 1
			elif curr_d == 'r':
				j += 1
			elif curr_d == 'l':
				j -= 1
		return (curr_i, curr_j)


class Solution:

	def endPoints(self, mat, m, n):

		def dfs(i, j, state):
			if i < 0:
				return (i + 1, j)
			elif i >= m:
				return (i - 1, j)
			elif j < 0:
				return (i, j + 1)
			elif j >= n:
				return (i, j - 1)
			if state == 'R':
				if mat[i][j] == 0:
					return dfs(i, j + 1, 'R')
				else:
					mat[i][j] = 0
					return dfs(i + 1, j, 'D')
			if state == 'D':
				if mat[i][j] == 0:
					return dfs(i + 1, j, 'D')
				else:
					mat[i][j] = 0
					return dfs(i, j - 1, 'L')
			if state == 'L':
				if mat[i][j] == 0:
					return dfs(i, j - 1, 'L')
				else:
					mat[i][j] = 0
					return dfs(i - 1, j, 'U')
			if state == 'U':
				if mat[i][j] == 0:
					return dfs(i - 1, j, 'U')
				else:
					mat[i][j] = 0
					return dfs(i, j + 1, 'R')
		return dfs(0, 0, 'R')


class Solution:

	def endPoints(self, matrix, m, n):
		(i, j) = (0, 0)
		dir = 0
		while True:
			dir = (dir + matrix[i][j]) % 4
			if matrix[i][j] == 1:
				matrix[i][j] = 0
			if dir == 0:
				j += 1
			elif dir == 1:
				i += 1
			elif dir == 2:
				j -= 1
			elif dir == 3:
				i -= 1
			if i < 0:
				i += 1
				break
			elif j < 0:
				j += 1
				break
			elif j >= len(matrix[0]):
				j -= 1
				break
			elif i >= len(matrix):
				i -= 1
				break
		return (i, j)


class Solution:

	def endPoints(self, matrix, m, n):
		direction = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}
		(i, j) = (0, 0)
		curr = 'right'
		while True:
			if matrix[i][j] == 0:
				if curr == 'left':
					j -= 1
					if j < 0:
						return [i, j + 1]
				elif curr == 'right':
					j += 1
					if j > n - 1:
						return [i, j - 1]
				elif curr == 'down':
					i += 1
					if i > m - 1:
						return [i - 1, j]
				elif curr == 'up':
					i -= 1
					if i < 0:
						return [i + 1, j]
			else:
				matrix[i][j] = 0
				curr = direction[curr]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(r, c) = map(int, input().strip().split())
		matrix = []
		for i in range(r):
			line = [int(x) for x in input().strip().split()]
			matrix.append(line)
		ob = Solution()
		ans = ob.endPoints(matrix, r, c)
		print('(', ans[0], ', ', ans[1], ')', sep='')


class Solution:

	def endPoints(self, matrix, m, n):
		i = 0
		j = 0
		curr_dir = 'R'
		while i < m and j < n and (j >= 0) and (i >= 0):
			if matrix[i][j] == 0 and curr_dir == 'R':
				j += 1
			elif matrix[i][j] == 0 and curr_dir == 'L':
				j -= 1
			elif matrix[i][j] == 0 and curr_dir == 'U':
				i -= 1
			elif matrix[i][j] == 0 and curr_dir == 'D':
				i += 1
			elif matrix[i][j] == 1 and curr_dir == 'R':
				matrix[i][j] = 0
				curr_dir = 'D'
				i += 1
			elif matrix[i][j] == 1 and curr_dir == 'L':
				matrix[i][j] = 0
				curr_dir = 'U'
				i -= 1
			elif matrix[i][j] == 1 and curr_dir == 'D':
				matrix[i][j] = 0
				curr_dir = 'L'
				j -= 1
			elif matrix[i][j] == 1 and curr_dir == 'U':
				matrix[i][j] = 0
				curr_dir = 'R'
				j += 1
		if i < 0:
			i += 1
		if j < 0:
			j += 1
		if i >= m:
			i -= 1
		if j >= n:
			j -= 1
		return [i, j]


class Solution:

	def endPoints(self, mat, m, n):
		guide = {'top': 'right', 'right': 'bottom', 'bottom': 'left', 'left': 'top'}
		currdir = 'right'
		row = 0
		col = 0
		top = 0
		left = 0
		right = len(mat[0])
		bottom = len(mat)
		while left <= col < right and top <= row < bottom:
			if mat[row][col] == 0:
				if currdir == 'right':
					if col != right - 1:
						col += 1
					else:
						return (row, col)
				elif currdir == 'left':
					if col != left:
						col -= 1
					else:
						return (row, col)
				elif currdir == 'top':
					if row != top:
						row -= 1
					else:
						return (row, col)
				elif currdir == 'bottom':
					if row != bottom - 1:
						row += 1
					else:
						return (row, col)
			elif mat[row][col] == 1:
				mat[row][col] = 0
				currdir = guide[currdir]
				if currdir == 'right':
					if col != right - 1:
						col += 1
					else:
						return (row, col)
				elif currdir == 'left':
					if col != left:
						col -= 1
					else:
						return (row, col)
				elif currdir == 'top':
					if row != top:
						row -= 1
					else:
						return (row, col)
				elif currdir == 'bottom':
					if row != bottom - 1:
						row += 1
					else:
						return (row, col)
		return (row, col)


class Solution:

	def endPoints(self, matrix, m, n):
		change = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		ind = 0
		i = j = 0
		while i > -1 and i < m and (j > -1) and (j < n):
			if matrix[i][j] == 1:
				ind = (ind + 1) % 4
				matrix[i][j] = 0
			cell = [i, j]
			i += change[ind][0]
			j += change[ind][1]
		return cell


class Solution:

	def endPoints(self, matrix, m, n):

		def is_safe(m, n, i, j):
			if i < 0:
				return False
			elif j < 0:
				return False
			elif i >= m:
				return False
			elif j >= n:
				return False
			return True

		def checking_the_exit():
			i = 0
			j = 0
			current_direction = 'r'
			changed_direction = {'l': 'u', 'u': 'r', 'r': 'd', 'd': 'l'}
			while is_safe(m, n, i, j):
				current_i = i
				current_j = j
				if matrix[i][j] == 1:
					move_in = changed_direction[current_direction]
					matrix[i][j] = 0
					if move_in == 'u':
						i -= 1
					elif move_in == 'd':
						i += 1
					elif move_in == 'l':
						j -= 1
					elif move_in == 'r':
						j += 1
					current_direction = move_in
				elif current_direction == 'u':
					i -= 1
				elif current_direction == 'd':
					i += 1
				elif current_direction == 'l':
					j -= 1
				elif current_direction == 'r':
					j += 1
			return (current_i, current_j)
		return checking_the_exit()


def issafe(m, n, i, j):
	if i < 0:
		return False
	if j < 0:
		return False
	if i >= m:
		return False
	if j >= n:
		return False
	return True

class Solution:

	def endPoints(self, matrix, m, n):
		i = 0
		j = 0
		cur_pos = 'r'
		di = {'l': 'u', 'u': 'r', 'r': 'd', 'd': 'l'}
		while issafe(m, n, i, j):
			cur_i = i
			cur_j = j
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				move = di[cur_pos]
				if move == 'u':
					i -= 1
				elif move == 'l':
					j -= 1
				elif move == 'r':
					j += 1
				elif move == 'd':
					i += 1
				cur_pos = move
			elif cur_pos == 'u':
				i -= 1
			elif cur_pos == 'l':
				j -= 1
			elif cur_pos == 'r':
				j += 1
			elif cur_pos == 'd':
				i += 1
		return (cur_i, cur_j)


class Solution:

	def endPoints(self, matrix, m, n):
		px = py = x = y = 0
		ds = [(0, -1), (1, 0), (0, 1), (-1, 0)]
		di = 1
		while 0 <= x and x < n and (0 <= y) and (y < m):
			if matrix[y][x] == 0:
				(px, py) = (x, y)
				x += ds[di][0]
				y += ds[di][1]
			else:
				matrix[y][x] = 0
				di = (di + 1) % 4
		return (py, px)


class Solution:

	def endPoints(self, matrix, m, n):
		up = False
		down = False
		right = True
		left = False
		start_row = start_col = 0
		while 0 <= start_row < m and 0 <= start_col < n:
			if matrix[start_row][start_col] == 0:
				if right:
					start_col += 1
				elif left:
					start_col -= 1
				elif up:
					start_row -= 1
				elif down:
					start_row += 1
			else:
				matrix[start_row][start_col] = 0
				if right:
					right = False
					down = True
				elif left:
					left = False
					up = True
				elif up:
					up = False
					right = True
				elif down:
					down = False
					left = True
		if start_row < 0:
			start_row += 1
		if start_row >= m:
			start_row -= 1
		if start_col < 0:
			start_col += 1
		if start_col >= n:
			start_col -= 1
		return (start_row, start_col)


class Solution:

	def endPoints(self, matrix, m, n):
		k = 'r'
		i = 0
		j = 0
		while i >= 0 and j >= 0 and (i < m) and (j < n):
			if matrix[i][j] == 0:
				ans1 = i
				ans2 = j
				if k == 'r':
					j += 1
				elif k == 'd':
					i += 1
				elif k == 'l':
					j -= 1
				elif k == 'u':
					i -= 1
			else:
				ans1 = i
				ans2 = j
				if k == 'r':
					matrix[i][j] = 0
					k = 'd'
					i += 1
				elif k == 'd':
					matrix[i][j] = 0
					k = 'l'
					j -= 1
				elif k == 'l':
					matrix[i][j] = 0
					k = 'u'
					i -= 1
				elif k == 'u':
					matrix[i][j] = 0
					k = 'r'
					j += 1
		return (ans1, ans2)


U = (-1, 0)
D = (1, 0)
L = (0, -1)
R = (0, 1)
changes = {U: R, R: D, D: L, L: U}

class Solution:

	def endPoints(self, matrix, m, n):
		dir = R
		(ui, uj) = (0, 0)
		prev = (0, 0)
		while ui in range(m) and uj in range(n):
			if matrix[ui][uj] == 1:
				dir = changes[dir]
				matrix[ui][uj] = 0
			else:
				prev = (ui, uj)
				(di, dj) = dir
				ui += di
				uj += dj
		return prev


class Solution:

	def endPoints(self, matrix, m, n):
		direction = {1: 2, 2: 3, 3: 4, 4: 1}
		curr_direction = 2
		(x, y) = (0, 0)
		while True:
			(prev_x, prev_y) = (x, y)
			if matrix[x][y] == 0:
				if curr_direction == 1:
					x -= 1
				elif curr_direction == 2:
					y += 1
				elif curr_direction == 3:
					x += 1
				else:
					y -= 1
			else:
				matrix[x][y] = 0
				curr_direction = direction[curr_direction]
				if curr_direction == 1:
					x -= 1
				elif curr_direction == 2:
					y += 1
				elif curr_direction == 3:
					x += 1
				else:
					y -= 1
			if x < 0 or y < 0 or x >= m or (y >= n):
				return (prev_x, prev_y)


class Solution:

	def endPoints(self, matrix, m, n):
		verticalShift = 0
		horizontalShift = 1
		i = 0
		j = 0
		while True:
			if i < 0 or i >= m:
				break
			if j < 0 or j >= n:
				break
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				if verticalShift == 0 and horizontalShift == 1:
					verticalShift = 1
					horizontalShift = 0
				elif verticalShift == 1 and horizontalShift == 0:
					verticalShift = 0
					horizontalShift = -1
				elif verticalShift == 0 and horizontalShift == -1:
					verticalShift = -1
					horizontalShift = 0
				elif verticalShift == -1 and horizontalShift == 0:
					verticalShift = 0
					horizontalShift = 1
			i += verticalShift
			j += horizontalShift
		return (i - verticalShift, j - horizontalShift)


class Solution:

	def endPoints(self, matrix, m, n):
		direction = [0, 1, 0, -1]
		dr = row = col = 0
		dc = 1
		while 0 <= row < m and 0 <= col < n:
			if matrix[row][col] == 1:
				matrix[row][col] = 0
				dr = (dr + 1) % 4
				dc = (dc + 1) % 4
			row += direction[dr]
			col += direction[dc]
		return (row - direction[dr], col - direction[dc])


class Solution:

	def endPoints(self, matrix, m, n):
		d = 0
		a = 0
		b = 0
		while 0 <= a < m and 0 <= b < n:
			v = matrix[a][b]
			if v == 0:
				if d == 0:
					b += 1
				elif d == 1:
					a += 1
				elif d == 2:
					b -= 1
				else:
					a -= 1
			else:
				d = (d + 1) % 4
				matrix[a][b] = 0
		if a == -1:
			a = 0
		elif a == m:
			a -= 1
		elif b == -1:
			b = 0
		elif b == n:
			b -= 1
		return [a, b]


change_dir = {'u': 'r', 'r': 'd', 'd': 'l', 'l': 'u'}

class Solution:

	def endPoints(self, matrix, m, n):
		return self.operation(matrix, 0, 0, 'r', m, n)

	def operation(self, matrix, r, c, d, m, n):
		if matrix[r][c]:
			matrix[r][c] = 0
			d = change_dir[d]
		new_r = r
		new_c = c
		if d == 'r':
			new_c = new_c + 1
		elif d == 'd':
			new_r = new_r + 1
		elif d == 'l':
			new_c = new_c - 1
		elif d == 'u':
			new_r = new_r - 1
		if new_r < 0 or new_r == m or new_c < 0 or (new_c == n):
			return [r, c]
		return self.operation(matrix, new_r, new_c, d, m, n)


class Solution:

	def endPoints(self, matrix, m, n):
		dir = 'right'
		i = 0
		j = 0
		while i < m and j < n and (i >= 0) and (j >= 0):
			if matrix[i][j] == 0:
				if dir == 'right':
					j += 1
				elif dir == 'left':
					j -= 1
				elif dir == 'down':
					i += 1
				elif dir == 'up':
					i -= 1
			elif matrix[i][j] == 1:
				matrix[i][j] = 0
				if dir == 'right':
					dir = 'down'
					i += 1
				elif dir == 'left':
					dir = 'up'
					i -= 1
				elif dir == 'down':
					dir = 'left'
					j -= 1
				elif dir == 'up':
					dir = 'right'
					j += 1
		if i == -1:
			return list([i + 1, j])
		elif j == -1:
			return list([i, j + 1])
		elif j == n:
			return list([i, j - 1])
		elif i == m:
			return list([i - 1, j])


class Solution:

	def endPoints(self, matrix, m, n):
		direction = 2
		(i, j) = (0, 0)
		while True:
			if matrix[i][j] == 0:
				if direction == 2:
					if j + 1 < n:
						j += 1
					else:
						break
				elif direction == -2:
					if j - 1 >= 0:
						j -= 1
					else:
						break
				elif direction == 1:
					if i - 1 >= 0:
						i -= 1
					else:
						break
				elif direction == -1:
					if i + 1 < m:
						i += 1
					else:
						break
			elif matrix[i][j] == 1:
				matrix[i][j] = 0
				if direction == 2:
					direction = -1
					if i + 1 < m:
						i += 1
					else:
						break
				elif direction == -2:
					direction = 1
					if i - 1 >= 0:
						i -= 1
					else:
						break
				elif direction == 1:
					direction = 2
					if j + 1 < n:
						j = j + 1
					else:
						break
				elif direction == -1:
					direction = -2
					if j - 1 >= 0:
						j -= 1
					else:
						break
		return tuple([i, j])


class Solution:

	def endPoints(self, matrix, n, m):
		direction = 'r'
		i = 0
		j = 0
		while i <= n and j <= m:
			if i >= n or j >= m or i < 0 or (j < 0):
				if i >= n and j >= m:
					i -= 1
					j -= 1
				elif i >= n:
					i -= 1
				elif j >= m:
					j -= 1
				elif i < 0 and j < 0:
					i += 1
					j += 1
				elif i < 0:
					i += 1
				else:
					j += 1
				tup = (i, j)
				return tup
				break
			if matrix[i][j] == 0:
				if direction == 'r':
					j += 1
				elif direction == 'd':
					i += 1
				elif direction == 'l':
					j -= 1
				else:
					i -= 1
			else:
				matrix[i][j] = 0
				if direction == 'r':
					direction = 'd'
					i += 1
				elif direction == 'd':
					direction = 'l'
					j -= 1
				elif direction == 'l':
					direction = 'u'
					i -= 1
				else:
					direction = 'r'
					j += 1


class Solution:

	def endPoints(self, matrix, m, n):

		def check(i, j, m, n):
			if i < 0 and j >= 0:
				i1 = i + 1
				return (i1, j)
			elif j < 0 and i >= 0:
				j1 = j + 1
				return (i, j1)
			elif i > m - 1 and j >= 0:
				return (m - 1, j)
			elif i >= 0 and j > n - 1:
				return (i, n - 1)
			else:
				return (-1, -1)
		i = 0
		j = 0
		direction = 'r'
		while True:
			if matrix[i][j] == 0:
				if direction == 'r':
					j += 1
				elif direction == 'u':
					i -= 1
				elif direction == 'l':
					j -= 1
				elif direction == 'd':
					i += 1
			else:
				matrix[i][j] = 0
				if direction == 'u':
					direction = 'r'
				elif direction == 'r':
					direction = 'd'
				elif direction == 'd':
					direction = 'l'
				elif direction == 'l':
					direction = 'u'
			(k, l) = check(i, j, m, n)
			if k != -1 and l != -1:
				return (k, l)


class Solution:

	def endPoints(self, matrix, m, n):
		(i, j, d) = (0, 0, 'R')
		dir = {'R': [+0, +1], 'D': [+1, +0], 'L': [+0, -1], 'U': [-1, +0]}
		while (i < m) & (j < n) & (i >= 0) & (j >= 0):
			if matrix[i][j] == 1:
				if d == 'R':
					d = 'D'
				elif d == 'D':
					d = 'L'
				elif d == 'L':
					d = 'U'
				else:
					d = 'R'
				matrix[i][j] = 0
			(i, j) = (i + dir[d][0], j + dir[d][1])
		if i == m:
			i -= 1
		elif j == n:
			j -= 1
		elif i == -1:
			i = 0
		elif j == -1:
			j = 0
		return [i, j]


class Solution:

	def endPoints(self, matrix, m, n):
		dir = 0
		i = 0
		j = 0
		while 0 <= i < m and 0 <= j < n:
			v = matrix[i][j]
			if v == 0:
				if dir == 0:
					j = j + 1
				elif dir == 1:
					i = i + 1
				elif dir == 2:
					j = j - 1
				else:
					i = i - 1
			else:
				dir = (dir + 1) % 4
				matrix[i][j] = 0
		if i == -1:
			i = 0
		elif i == m:
			i = i - 1
		elif j == -1:
			j = 0
		elif j == n:
			j = j - 1
		return [i, j]


class Solution:

	def endPoints(self, matrix, m, n):
		(i, j) = (0, 0)
		dir = 'r'
		while i >= 0 and j >= 0 and (i < m) and (j < n):
			if matrix[i][j] == 0:
				if dir == 'r':
					j += 1
				elif dir == 'l':
					j -= 1
				elif dir == 'u':
					i -= 1
				else:
					i += 1
			elif matrix[i][j] == 1:
				matrix[i][j] = 0
				if dir == 'r':
					dir = 'd'
					i += 1
				elif dir == 'l':
					dir = 'u'
					i -= 1
				elif dir == 'u':
					dir = 'r'
					j += 1
				else:
					dir = 'l'
					j -= 1
		if dir == 'l':
			return [i, j + 1]
		elif dir == 'r':
			return [i, j - 1]
		elif dir == 'u':
			return [i + 1, j]
		else:
			return [i - 1, j]


class Solution:

	def endPoints(self, matrix, m, n):
		d = 1
		i = 0
		j = 0
		while i < m and j < n and (i >= 0) and (j >= 0):
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				d = (d + 1) % 4
			elif d == 0:
				i -= 1
			elif d == 1:
				j += 1
			elif d == 2:
				i += 1
			elif d == 3:
				j -= 1
		if i == m:
			return [i - 1, j]
		elif i < 0:
			return [i + 1, j]
		elif j < 0:
			return [i, j + 1]
		else:
			return [i, j - 1]


class Solution:

	def endPoints(self, matrix, m, n):
		(i, j) = (0, 0)
		d = 'r'
		while True:
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				if d == 'r':
					d = 'd'
				elif d == 'd':
					d = 'l'
				elif d == 'l':
					d = 'u'
				elif d == 'u':
					d = 'r'
			if d == 'r':
				j += 1
			elif d == 'u':
				i -= 1
			elif d == 'd':
				i += 1
			elif d == 'l':
				j -= 1
			if i > m - 1 or j < 0 or j > n - 1 or (i < 0):
				break
		if d == 'r':
			j -= 1
		elif d == 'u':
			i += 1
		elif d == 'l':
			j += 1
		elif d == 'd':
			i -= 1
		return (i, j)


class Solution:

	def endPoints(self, matrix, m, n):
		ans1 = [[0, 0]]
		ans = []
		d = 1
		i = 0
		j = 0
		while True and i >= 0 and (i < m) and (j < n) and (j >= 0):
			try:
				if matrix[i][j] == 0:
					a = d % 4
					if a == 1:
						j += 1
					elif a == 2:
						i += 1
					elif a == 3:
						j -= 1
					else:
						i -= 1
				if i >= 0 and i < m and (j < n) and (j >= 0):
					ans = [i, j]
					ans1.append(ans)
				if matrix[i][j] == 1:
					matrix[i][j] = 0
					d += 1
					a = d % 4
					if a == 1:
						j += 1
					elif a == 2:
						i += 1
					elif a == 3:
						j -= 1
					else:
						i -= 1
				if i >= 0 and i < m and (j < n) and (j >= 0):
					ans = [i, j]
					ans1.append(ans)
			except:
				break
		return ans1[len(ans1) - 1]


class Solution:

	def endPoints(self, matrix, m, n):
		direction = 'right'
		(i, j) = (0, 0)
		while i < m and j < n:
			if i < 0 or j < 0:
				break
			if matrix[i][j] == 0:
				if direction == 'up':
					i -= 1
				elif direction == 'down':
					i += 1
				elif direction == 'right':
					j += 1
				elif direction == 'left':
					j -= 1
			else:
				matrix[i][j] = 0
				if direction == 'right':
					direction = 'down'
				elif direction == 'down':
					direction = 'left'
				elif direction == 'left':
					direction = 'up'
				elif direction == 'up':
					direction = 'right'
		if i == m:
			return (i - 1, j)
		elif j == n:
			return (i, j - 1)
		elif j < 0:
			return (i, j + 1)
		else:
			return (i + 1, j)


class Solution:

	def endPoints(self, matrix, m, n):
		d1 = {'l': 'u', 'u': 'r', 'r': 'd', 'd': 'l'}
		rowlim = m - 1
		collim = n - 1
		start = (0, 0)
		d = 'r'
		while True:
			val = matrix[start[0]][start[1]]
			if val == 1:
				matrix[start[0]][start[1]] = 0
				d = d1[d]
			else:
				pass
			if d == 'l':
				start1 = (start[0], start[1] - 1)
			elif d == 'r':
				start1 = (start[0], start[1] + 1)
			elif d == 'u':
				start1 = (start[0] - 1, start[1])
			else:
				start1 = (start[0] + 1, start[1])
			if (start1[0] >= 0 and start1[0] <= rowlim) and (start1[1] >= 0 and start1[1] <= collim):
				start = start1
			else:
				return start


class Solution:

	def endPoints(self, mat, m, n):
		i = 0
		j = 0
		rf = 1
		df = 0
		lf = 0
		uf = 0
		while (i < m and j < n) and (i >= 0 and j >= 0):
			if mat[i][j] == 1:
				if rf == 1:
					mat[i][j] = 0
					df = 1
					rf = 0
					i += 1
				elif df == 1:
					mat[i][j] = 0
					lf = 1
					df = 0
					j -= 1
				elif uf == 1:
					mat[i][j] = 0
					uf = 0
					rf = 1
					j += 1
				elif lf == 1:
					mat[i][j] = 0
					lf = 0
					uf = 1
					i -= 1
			elif rf == 1:
				j += 1
			elif df == 1:
				i += 1
			elif lf == 1:
				j -= 1
			elif uf == 1:
				i -= 1
		if rf == 1:
			return (i, j - 1)
		elif lf == 1:
			return (i, j + 1)
		elif uf == 1:
			return (i + 1, j)
		elif df == 1:
			return (i - 1, j)


class Solution:

	def check(x, y, m, n):
		return x >= 0 and y >= 0 and (x < m) and (y < n)

	def endPoints(self, matrix, m, n):
		l = [[0, 1], [1, 0], [0, -1], [-1, 0]]
		val = 1
		(row, col) = (0, 0)
		incRow = 0
		incCol = 1
		while True:
			if matrix[row][col] == 1:
				matrix[row][col] = 0
				incRow = l[val][0]
				incCol = l[val][1]
				val = (val + 1) % 4
			else:
				row += incRow
				col += incCol
				if not Solution.check(row, col, m, n):
					return (row - incRow, col - incCol)
					exit()


next_dir = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}

class Solution:

	def endPoints(self, matrix, m, n):
		(cur_pt, direction) = ((0, 0), 'right')
		prev = cur_pt
		while self.is_inside(cur_pt, m, n):
			prev = cur_pt
			(i, j) = cur_pt
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				direction = next_dir[direction]
			cur_pt = self.get_next_pt(cur_pt, direction)
		return prev

	def get_next_pt(self, cur_pt, direction):
		(i, j) = cur_pt
		if direction == 'up':
			return (i - 1, j)
		elif direction == 'down':
			return (i + 1, j)
		elif direction == 'left':
			return (i, j - 1)
		else:
			return (i, j + 1)

	def is_inside(self, cur_pt, m, n):
		(i, j) = cur_pt
		return 0 <= i < m and 0 <= j < n


class Solution:

	def endPoints(self, matrix, m, n):
		i = 0
		di = 'r'
		while i < m:
			j = 0
			while j < n:
				if matrix[i][j] == 0:
					if di == 'r':
						j += 1
						if j >= n:
							return (i, j - 1)
					elif di == 'l':
						j -= 1
						if j < 0:
							return (i, j + 1)
					elif di == 't':
						i -= 1
						if i < 0:
							return (i + 1, j)
					else:
						i += 1
						if i >= m:
							return (i - 1, j)
				elif matrix[i][j] == 1:
					matrix[i][j] = 0
					if di == 'r':
						di = 'd'
					elif di == 'l':
						di = 't'
					elif di == 't':
						di = 'r'
					else:
						di = 'l'


class Solution:

	def isSafe(self, m, n, i, j):
		if i < 0:
			return False
		if i >= m:
			return False
		if j >= n:
			return False
		if j < 0:
			return False
		return True

	def endPoints(self, matrix, m, n):
		i = 0
		j = 0
		curr_dir = 'r'
		directions = {'l': 'u', 'r': 'd', 'u': 'r', 'd': 'l'}
		while self.isSafe(m, n, i, j):
			curr_i = i
			curr_j = j
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				move_dir = directions[curr_dir]
				if move_dir == 'r':
					j += 1
				elif move_dir == 'l':
					j -= 1
				elif move_dir == 'u':
					i -= 1
				elif move_dir == 'd':
					i += 1
				curr_dir = move_dir
			else:
				if curr_dir == 'l':
					j -= 1
				if curr_dir == 'r':
					j += 1
				if curr_dir == 'u':
					i -= 1
				if curr_dir == 'd':
					i += 1
		return (curr_i, curr_j)


class Solution:

	def safe(self, m, n, i, j):
		flag = True
		if i < 0:
			flag = False
		if i >= m:
			flag = False
		if j < 0:
			flag = False
		if j >= n:
			flag = False
		return flag

	def endPoints(self, matrix, m, n):
		direction = {'r': 'd', 'u': 'r', 'd': 'l', 'l': 'u'}
		curr_dir = 'r'
		i = 0
		j = 0
		while ob.safe(m, n, i, j):
			cur_i = i
			cur_j = j
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				mov_dir = direction[curr_dir]
				if mov_dir == 'u':
					i = i - 1
				elif mov_dir == 'l':
					j = j - 1
				elif mov_dir == 'r':
					j = j + 1
				elif mov_dir == 'd':
					i = i + 1
				curr_dir = mov_dir
			elif curr_dir == 'u':
				i = i - 1
			elif curr_dir == 'l':
				j = j - 1
			elif curr_dir == 'r':
				j = j + 1
			elif curr_dir == 'd':
				i = i + 1
		return [cur_i, cur_j]


class Solution:

	def endPoints(self, matrix, m, n):
		dic1 = {'left': 'up', 'up': 'right', 'right': 'down', 'down': 'left'}
		dir_dic = {'left': (0, -1), 'up': (-1, 0), 'right': (0, 1), 'down': (1, 0)}
		direction = 'right'
		i = 0
		j = 0
		while (i >= 0 and i < m) and (j >= 0 and j < n):
			if matrix[i][j] == 0:
				i += dir_dic[direction][0]
				j += dir_dic[direction][1]
			else:
				matrix[i][j] = 0
				direction = dic1[direction]
		dir_rev = {'left': (0, 1), 'up': (1, 0), 'right': (0, -1), 'down': (-1, 0)}
		i += dir_rev[direction][0]
		j += dir_rev[direction][1]
		return (i, j)


class Solution:

	def endPoints(self, matrix, m, n):

		def dfs(i, j, dx, dy):
			if i >= m or j >= n or i < 0 or (j < 0):
				return (i - dx, j - dy)
			if matrix[i][j] == 0:
				return dfs(i + dx, j + dy, dx, dy)
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				if dx == 1:
					return dfs(i, j - 1, 0, -1)
				if dx == -1:
					return dfs(i, j + 1, 0, 1)
				if dy == 1:
					return dfs(i + 1, j, 1, 0)
				if dy == -1:
					return dfs(i - 1, j, -1, 0)
		return dfs(0, 0, 0, 1)


class Solution:

	def endPoints(self, matrix, m, n):
		i = j = 0
		x = 0
		y = 1
		mapp = {(0, 1): (1, 0), (1, 0): (0, -1), (0, -1): (-1, 0), (-1, 0): (0, 1)}
		while 0 <= i < m and 0 <= j < n:
			if matrix[i][j] == 1:
				(x, y) = mapp[x, y]
				matrix[i][j] = 0
			i += x
			j += y
		if i == -1:
			i = 0
		elif i == m:
			i = i - 1
		elif j == -1:
			j = 0
		elif j == n:
			j = j - 1
		return [i, j]


up = (0, -1)
down = (0, 1)
left = (-1, 0)
right = (1, 0)
trans = {up: right, right: down, down: left, left: up}

class Solution:

	def endPoints(self, matrix, m, n):
		start = (0, 0)
		direction = right
		while True:
			(x0, y0) = start
			if matrix[y0][x0] == 1:
				direction = trans[direction]
				matrix[y0][x0] = 0
			else:
				(dx, dy) = direction
				x = x0 + dx
				y = y0 + dy
				if x < 0 or x >= n or y < 0 or (y >= m):
					return (y0, x0)
				start = (x, y)
		return start


class Solution:

	def endPoints(self, matrix, m, n):
		hmap = {}
		hmap['up'] = 'right'
		hmap['right'] = 'down'
		hmap['down'] = 'left'
		hmap['left'] = 'up'
		pos = [0, 0]
		d = 'right'
		while True:
			if matrix[pos[0]][pos[1]] == 1:
				d = hmap[d]
			if d == 'right':
				if pos[1] + 1 >= len(matrix[0]):
					return pos
				else:
					matrix[pos[0]][pos[1]] = 0
					pos[1] += 1
			elif d == 'up':
				if pos[0] - 1 < 0:
					return pos
				else:
					matrix[pos[0]][pos[1]] = 0
					pos[0] -= 1
			elif d == 'left':
				if pos[1] - 1 < 0:
					return pos
				else:
					matrix[pos[0]][pos[1]] = 0
					pos[1] -= 1
			elif pos[0] + 1 >= len(matrix):
				return pos
			else:
				matrix[pos[0]][pos[1]] = 0
				pos[0] += 1


class Solution:

	def endPoints(self, matrix, m, n):
		direction = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}
		i = j = 0
		start = 'right'
		while i >= 0 and j >= 0 and (i < m) and (j < n):
			if matrix[i][j] == 1:
				start = direction[start]
				matrix[i][j] = 0
			if start == 'right':
				j += 1
			elif start == 'left':
				j -= 1
			elif start == 'up':
				i -= 1
			elif start == 'down':
				i += 1
		if i >= m:
			return (i - 1, j)
		elif i < 0:
			return (i + 1, j)
		elif j < 0:
			return (i, j + 1)
		return (i, j - 1)


class Solution:

	def endPoints(self, matrix, m, n):
		direction = 'r'
		(i, j) = (0, 0)
		row = m
		col = n
		while True:
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				if direction == 'u':
					direction = 'r'
				elif direction == 'r':
					direction = 'd'
				elif direction == 'd':
					direction = 'l'
				else:
					direction = 'u'
			if direction == 'r':
				j += 1
				if j >= col:
					return [i, j - 1]
			elif direction == 'l':
				j -= 1
				if j < 0:
					return [i, j + 1]
			if direction == 'u':
				i -= 1
				if i < 0:
					return [i + 1, j]
			elif direction == 'd':
				i += 1
				if i >= row:
					return [i - 1, j]