B. Counting Rectangles is Fun

problem_index: B

time_limit: 4 seconds

memory_limit: 256 megabytes

note:
For the first example, there is a 5 × 5 rectangular grid, and the first, the second, and the third queries are represented in the following image.
![image](images/cf_372_B/1.png)
For the first query, there are 10 good rectangles, five 1 × 1, two 2 × 1, two 1 × 2, and one 1 × 3.  For the second query, there is only one 1 × 1 good rectangle.  For the third query, there are 7 good rectangles, four 1 × 1, two 2 × 1, and one 3 × 1.

difficulty: HARD

source: codeforces

raw_problem:
B. Counting Rectangles is Fun

time limit per test
4 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

There is an n × m rectangular grid, each cell of the grid contains a single integer: zero or one. Let's call the cell on the i-th row and the j-th column as (i, j).

Let's define a "rectangle" as four integers a, b, c, d (1 ≤ a ≤ c ≤ n; 1 ≤ b ≤ d ≤ m). Rectangle denotes a set of cells of the grid {(x, y) :  a ≤ x ≤ c, b ≤ y ≤ d}. Let's define a "good rectangle" as a rectangle that includes only the cells with zeros.

You should answer the following q queries: calculate the number of good rectangles all of which cells are in the given rectangle.

Input

There are three integers in the first line: n, m and q (1 ≤ n, m ≤ 40, 1 ≤ q ≤ 3·105). Each of the next n lines contains m characters — the grid. Consider grid rows are numbered from top to bottom, and grid columns are numbered from left to right. Both columns and rows are numbered starting from 1.

Each of the next q lines contains a query — four integers that describe the current rectangle, a, b, c, d (1 ≤ a ≤ c ≤ n; 1 ≤ b ≤ d ≤ m).

Output

For each query output an answer — a single integer in a separate line.

Examples

Input

5 5 5
00101
00000
00001
01000
00001
1 2 2 4
4 5 4 5
1 2 5 2
2 2 4 5
4 2 5 3

Output

10
1
7
34
5

Input

4 7 5
0000100
0000010
0011000
0000000
1 7 2 7
3 1 3 1
2 3 4 5
1 2 2 7
2 2 4 7

Output

3
1
16
27
52

Note

For the first example, there is a 5 × 5 rectangular grid, and the first, the second, and the third queries are represented in the following image.

 For the first query, there are 10 good rectangles, five 1 × 1, two 2 × 1, two 1 × 2, and one 1 × 3.

 For the second query, there is only one 1 × 1 good rectangle.

 For the third query, there are 7 good rectangles, four 1 × 1, two 2 × 1, and one 3 × 1.

question:
There is an n × m rectangular grid, each cell of the grid contains a single integer: zero or one. Let's call the cell on the i-th row and the j-th column as (i, j).
Let's define a "rectangle" as four integers a, b, c, d (1 ≤ a ≤ c ≤ n; 1 ≤ b ≤ d ≤ m). Rectangle denotes a set of cells of the grid {(x, y) :  a ≤ x ≤ c, b ≤ y ≤ d}. Let's define a "good rectangle" as a rectangle that includes only the cells with zeros.
You should answer the following q queries: calculate the number of good rectangles all of which cells are in the given rectangle.

Input
There are three integers in the first line: n, m and q (1 ≤ n, m ≤ 40, 1 ≤ q ≤ 3·10^{5}). Each of the next n lines contains m characters — the grid. Consider grid rows are numbered from top to bottom, and grid columns are numbered from left to right. Both columns and rows are numbered starting from 1.
Each of the next q lines contains a query — four integers that describe the current rectangle, a, b, c, d (1 ≤ a ≤ c ≤ n; 1 ≤ b ≤ d ≤ m).

Output
For each query output an answer — a single integer in a separate line.

Examples
Input
5 5 5
00101
00000
00001
01000
00001
1 2 2 4
4 5 4 5
1 2 5 2
2 2 4 5
4 2 5 3

Output
10
1
7
34
5

Input
4 7 5
0000100
0000010
0011000
0000000
1 7 2 7
3 1 3 1
2 3 4 5
1 2 2 7
2 2 4 7

Output
3
1
16
27
52

Note
For the first example, there is a 5 × 5 rectangular grid, and the first, the second, and the third queries are represented in the following image.
 ![image](1.png)  -  For the first query, there are 10 good rectangles, five 1 × 1, two 2 × 1, two 1 × 2, and one 1 × 3. -  For the second query, there is only one 1 × 1 good rectangle. -  For the third query, there are 7 good rectangles, four 1 × 1, two 2 × 1, and one 3 × 1.

tags: ['Dynamic programming', 'Divide and conquer', 'Complete search']

skill_types: ['Dynamic programming', 'Complete search']

raw_tags: ['brute force', 'dp', 'divide and conquer']

data_split: test


CODE FESTIVAL 2016 qual A - LRU Puzzle

solutions: ["def reads(offset=0):\n\treturn [int(i) - offset for i in input().split(' ')]\n\ndef Judge(vector):\n\tlength = len(vector) - 1\n\tfor i in range(length):\n\t\tif vector[i] > vector[i + 1]:\n\t\t\treturn 0\n\treturn 1\n(N, M) = reads()\nQ = int(input())\nA = reads(1)\npos = [-1] * M\npat = []\nfreq = [0] * (M + 1)\nfreq[0] = N\nfound = set()\ncounter = 0\nfor i in A[::-1]:\n\tif i not in found:\n\t\tpat.append(i)\n\t\tfound.add(i)\n\t\tpos[i] = counter\n\t\tcounter += 1\n\t\tif counter == M:\n\t\t\tbreak\nfor i in range(M):\n\tif pos[i] == -1:\n\t\tpat.append(i)\nfor i in A[::-1]:\n\ttemp = pos[i]\n\tif freq[temp] > 0:\n\t\tfreq[temp] -= 1\n\t\tfreq[temp + 1] += 1\nstart = M\nfor i in range(M):\n\tif freq[i] != 0:\n\t\tstart = i\n\t\tbreak\nprint('Yes') if Judge(pat[start:]) else print('No')\n", "import sys\ninput = sys.stdin.readline\nsys.setrecursionlimit(10 ** 7)\n(N, M) = map(int, input().split())\nQ = int(input())\nA = [int(x) for x in input().split()]\nused = [False] * (M + 1)\narr = []\nfor x in A[::-1]:\n\tif used[x]:\n\t\tcontinue\n\tused[x] = True\n\tarr.append(x)\nfor x in range(1, M + 1):\n\tif used[x]:\n\t\tcontinue\n\tarr.append(x)\nx_to_i = {x: i for (i, x) in enumerate(arr, 1)}\nmade = [N] + [0] * M\nfor x in A[::-1]:\n\ti = x_to_i[x]\n\tif made[i - 1] > 0:\n\t\tmade[i - 1] -= 1\n\t\tmade[i] += 1\nL = 0\nprev = M + 100\nfor x in arr[::-1]:\n\tif x >= prev:\n\t\tbreak\n\tprev = x\n\tL += 1\nx = sum(made[::-1][:L + 1])\nanswer = 'Yes' if x == N else 'No'\nprint(answer)\n", "def read():\n\treturn int(input())\n\ndef reads(sep=None):\n\treturn list(map(int, input().split()))\n\ndef f(m, a):\n\tsa = set(a)\n\tseen = set()\n\tr = []\n\tfor n in a[::-1]:\n\t\tif n not in seen:\n\t\t\tr.append(n)\n\t\t\tseen.add(n)\n\tfor i in range(m):\n\t\tif i + 1 not in sa:\n\t\t\tr.append(i + 1)\n\treturn r\n\ndef isSorted(a):\n\tfor i in range(1, len(a)):\n\t\tif a[i - 1] > a[i]:\n\t\t\treturn False\n\treturn True\n(n, m) = reads()\nq = read()\na = reads()\nr = f(m, a)\ncount = [0] * (m + 1)\ncount[0] = n\ntable = [-1] * (m + 1)\nfor i in range(len(r)):\n\ttable[r[i]] = i\nfor aa in a[::-1]:\n\tindex = table[aa]\n\tif 0 < count[index]:\n\t\tcount[index] -= 1\n\t\tcount[index + 1] += 1\nto = m\nfor i in range(m):\n\tif 0 < count[i]:\n\t\tto = i\n\t\tbreak\nif isSorted(r[to:]):\n\tprint('Yes')\nelse:\n\tprint('No')\n", "import sys\n(N, M) = map(int, input().split())\nQ = int(input())\nA = list(map(int, input().split()))\ndic = {}\nlis = []\nflag = True\na = [[M - i, N] for i in range(M)]\nfor i in range(Q):\n\ta.append([A[i], 1])\na.reverse()\nfor i in range(len(a)):\n\tif a[i][0] not in dic:\n\t\tind = len(dic)\n\t\tdic[a[i][0]] = ind\n\t\tif ind != 0:\n\t\t\tlis.append(min(lis[ind - 1], a[i][1]))\n\t\telse:\n\t\t\tlis.append(a[i][1])\n\telse:\n\t\tind = dic[a[i][0]]\n\t\tif ind != 0:\n\t\t\tlis[ind] = min(N, lis[ind] + a[i][1], lis[ind - 1])\n\t\telse:\n\t\t\tlis[ind] = min(N, lis[ind] + a[i][1])\nif lis[-1] == N:\n\tprint('Yes')\nelse:\n\tprint('No')\n", "import sys\nreadline = sys.stdin.readline\nimport sys\nfrom itertools import product\nreadline = sys.stdin.readline\n\ndef check1(A):\n\tK = max(A)\n\ttable = [-1] * (K + 1)\n\tfor i in range(Q):\n\t\ttable[A[i]] = i\n\tif -1 in table:\n\t\treturn False\n\tif any((t1 - t2 < 0 for (t1, t2) in zip(table, table[1:]))):\n\t\treturn False\n\treturn True\nINF = 10 ** 9 + 7\n\ndef check2(A):\n\tstack = []\n\tused = set()\n\tfor a in A[::-1] + list(range(M)):\n\t\tif a not in used:\n\t\t\tused.add(a)\n\t\t\tstack.append(a)\n\tC = dict()\n\tfor i in range(M):\n\t\tC[stack[i]] = i\n\ttable = [0] * M + [INF]\n\tfor a in A[::-1]:\n\t\tif table[C[a]] < table[C[a] - 1]:\n\t\t\ttable[C[a]] += 1\n\tused = set()\n\tch = []\n\tfor i in range(M):\n\t\tif table[i] < N:\n\t\t\tbreak\n\t\tch.append(stack[i])\n\t\tused.add(stack[i])\n\tfor i in range(M):\n\t\tif i not in used:\n\t\t\tused.add(i)\n\t\t\tch.append(i)\n\treturn stack == ch\n(N, M) = map(int, readline().split())\nQ = int(readline())\nA = list(map(lambda x: int(x) - 1, readline().split()))\nans = 'Yes'\nif not check1(A):\n\tif not check2(A):\n\t\tans = 'No'\nprint(ans)\n"]

source: atcoder

time_limit: 2.0 seconds

memory_limit: 256.0 megabytes

raw_problem:
配点 : <var>1200</var> 点

問題文

配列が <var>N</var> 個あります。
最初、どの配列も長さ <var>M</var> で、整数が <var>(1，2，...，M)</var> の順に並んでいます。

高橋君は、これら <var>N</var> 個の配列に対して、計 <var>Q</var> 回の操作を行うことにしました。
<var>i</var> (<var>1≤i≤Q</var>) 回目の操作では、次のような操作を行います。

<var>N</var> 個の配列のうち好きなものをひとつ選ぶ。 その配列において、整数 <var>a_i</var> (<var>1≤a_i≤M</var>) を先頭へ移動する。 例えば、<var>a_i=2</var> のとき、配列 <var>(5，4，3，2，1)</var> を選んで操作を行うと、この配列は <var>(2，5，4，3，1)</var> へ変わる。

高橋君の目標は、計 <var>Q</var> 回の操作の後、<var>N</var> 個の配列がまったく同じになっていることです。
計 <var>Q</var> 回の操作の後、<var>N</var> 個の配列がまったく同じになるようにできるか判定してください。

制約

<var>2≤N≤10^5</var>

<var>2≤M≤10^5</var>

<var>1≤Q≤10^5</var>

<var>1≤a_i≤M</var>

入力

入力は以下の形式で標準入力から与えられる。

<var>N</var> <var>M</var>
<var>Q</var>
<var>a_1</var> <var>a_2</var> <var>...</var> <var>a_Q</var>

出力

計 <var>Q</var> 回の操作の後、<var>N</var> 個の配列がまったく同じになるようにできるならば、Yes を出力せよ。
できないならば、No を出力せよ。

入力例 1

2 2
3
2 1 2

出力例 1

Yes

例えば、図のように操作を行えばよいです。

入力例 2

3 2
3
2 1 2

出力例 2

No

入力例 3

2 3
3
3 2 1

出力例 3

Yes

例えば、図のように操作を行えばよいです。

入力例 4

3 3
6
1 2 2 3 3 3

出力例 4

No

Score : <var>1200</var> points

Problem Statement

There are <var>N</var> arrays.
The length of each array is <var>M</var> and initially each array contains integers <var>(1，2，...，M)</var> in this order.

Mr. Takahashi has decided to perform <var>Q</var> operations on those <var>N</var> arrays.
For the <var>i</var>-th (<var>1≤i≤Q</var>) time, he performs the following operation.

Choose an arbitrary array from the <var>N</var> arrays and move the integer <var>a_i</var> (<var>1≤a_i≤M</var>) to the front of that array. For example, after performing the operation on <var>a_i=2</var> and the array <var>(5，4，3，2，1)</var>, this array becomes <var>(2，5，4，3，1)</var>.

Mr. Takahashi wants to make <var>N</var> arrays exactly the same after performing the <var>Q</var> operations.
Determine if it is possible or not.

Constraints

<var>2≤N≤10^5</var>

<var>2≤M≤10^5</var>

<var>1≤Q≤10^5</var>

<var>1≤a_i≤M</var>

Input

The input is given from Standard Input in the following format:

<var>N</var> <var>M</var>
<var>Q</var>
<var>a_1</var> <var>a_2</var> <var>...</var> <var>a_Q</var>

Output

Print Yes if it is possible to make <var>N</var> arrays exactly the same after performing the <var>Q</var> operations.
Otherwise, print No.

Sample Input 1

2 2
3
2 1 2

Sample Output 1

Yes

You can perform the operations as follows.

Sample Input 2

3 2
3
2 1 2

Sample Output 2

No

Sample Input 3

2 3
3
3 2 1

Sample Output 3

Yes

You can perform the operations as follows.

Sample Input 4

3 3
6
1 2 2 3 3 3

Sample Output 4

No

question:
There are $N$ arrays.
The length of each array is $M$ and initially each array contains integers $(1，2，...，M)$ in this order.
Mr. Takahashi has decided to perform $Q$ operations on those $N$ arrays.
For the $i$-th ($1≤i≤Q$) time, he performs the following operation.

- Choose an arbitrary array from the $N$ arrays and move the integer $a_i$ ($1≤a_i≤M$) to the front of that array. For example, after performing the operation on $a_i=2$ and the array $(5，4，3，2，1)$, this array becomes $(2，5，4，3，1)$.

Mr. Takahashi wants to make $N$ arrays exactly the same after performing the $Q$ operations.
Determine if it is possible or not.

Constraints

- $2≤N≤10^5$
- $2≤M≤10^5$
- $1≤Q≤10^5$
- $1≤a_i≤M$

Input
The input is given from Standard Input in the following format:
$N$ $M$

$Q$

$a_1$ $a_2$ $...$ $a_Q$

Output
Print Yes if it is possible to make $N$ arrays exactly the same after performing the $Q$ operations.
Otherwise, print No.

Sample Input 1
2 2
3
2 1 2

Sample Output 1
Yes

You can perform the operations as follows.
![image](1.png)

Sample Input 2
3 2
3
2 1 2

Sample Output 2
No

Sample Input 3
2 3
3
3 2 1

Sample Output 3
Yes

You can perform the operations as follows.
![image](2.png)

Sample Input 4
3 3
6
1 2 2 3 3 3

Sample Output 4
No

image_tags:
Linear Data Structure
Linear Data Structure

data_split: test


E. Bash Plays with Functions

problem_index: E

time_limit: 3 seconds

memory_limit: 256 megabytes

question:
Bash got tired on his journey to become the greatest Pokemon master. So he decides to take a break and play with functions.
Bash defines a function f_{0}(n), which denotes the number of ways of factoring n into two factors p and q such that gcd(p, q) = 1. In other words, f_{0}(n) is the number of ordered pairs of positive integers (p, q) such that p·q = n and gcd(p, q) = 1.
But Bash felt that it was too easy to calculate this function. So he defined a series of functions, where f_{r + 1} is defined as:
![image](1.png)Where (u, v) is any ordered pair of positive integers, they need not to be co-prime.
Now Bash wants to know the value of f_{r}(n) for different r and n. Since the value could be huge, he would like to know the value modulo 10^{9} + 7. Help him!

Input
The first line contains an integer q (1 ≤ q ≤ 10^{6}) — the number of values Bash wants to know.
Each of the next q lines contain two integers r and n (0 ≤ r ≤ 10^{6}, 1 ≤ n ≤ 10^{6}), which denote Bash wants to know the value f_{r}(n).

Output
Print q integers. For each pair of r and n given, print f_{r}(n) modulo 10^{9} + 7 on a separate line.

Example
Input
5
0 30
1 25
3 65
2 5
4 48

Output
8
5
25
4
630

source: codeforces

raw_problem:
E. Bash Plays with Functions

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Bash got tired on his journey to become the greatest Pokemon master. So he decides to take a break and play with functions.

Bash defines a function f0(n), which denotes the number of ways of factoring n into two factors p and q such that gcd(p, q) = 1. In other words, f0(n) is the number of ordered pairs of positive integers (p, q) such that p·q = n and gcd(p, q) = 1.

But Bash felt that it was too easy to calculate this function. So he defined a series of functions, where fr + 1 is defined as:

Where (u, v) is any ordered pair of positive integers, they need not to be co-prime.

Now Bash wants to know the value of fr(n) for different r and n. Since the value could be huge, he would like to know the value modulo 109 + 7. Help him!

Input

The first line contains an integer q (1 ≤ q ≤ 106) — the number of values Bash wants to know.

Each of the next q lines contain two integers r and n (0 ≤ r ≤ 106, 1 ≤ n ≤ 106), which denote Bash wants to know the value fr(n).

Output

Print q integers. For each pair of r and n given, print fr(n) modulo 109 + 7 on a separate line.

Example

Input

5
0 30
1 25
3 65
2 5
4 48

Output

8
5
25
4
630

tags: ['Dynamic programming', 'Combinatorics', 'Number theory', 'Complete search']

skill_types: ['Dynamic programming', 'Complete search']

raw_tags: ['number theory', 'brute force', 'combinatorics', 'dp']

data_split: test


C. Sasha and a Patient Friend

problem_index: C

time_limit: 1.5 seconds

memory_limit: 256 megabytes

note:
In the first example all the queries of the $$$3$$$-rd type cover all the events, it's simulation is following:
![image](images/cf_1109_C/1.png)

source: codeforces

raw_problem:
C. Sasha and a Patient Friend

time limit per test
1.5 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Fedya and Sasha are friends, that's why Sasha knows everything about Fedya.

Fedya keeps his patience in an infinitely large bowl. But, unlike the bowl, Fedya's patience isn't infinite, that is why let $$$v$$$ be the number of liters of Fedya's patience, and, as soon as $$$v$$$ becomes equal to $$$0$$$, the bowl will burst immediately. There is one tap in the bowl which pumps $$$s$$$ liters of patience per second. Notice that $$$s$$$ can be negative, in that case, the tap pumps out the patience. Sasha can do different things, so he is able to change the tap's speed. All actions that Sasha does can be represented as $$$q$$$ queries. There are three types of queries:

 "1 t s"  — add a new event, means that starting from the $$$t$$$-th second the tap's speed will be equal to $$$s$$$.

 "2 t"  — delete the event which happens at the $$$t$$$-th second. It is guaranteed that such event exists.

 "3 l r v" — Sasha wonders: if you take all the events for which $$$l \le t \le r$$$ and simulate changes of Fedya's patience from the very beginning of the $$$l$$$-th second till the very beginning of the $$$r$$$-th second inclusive (the initial volume of patience, at the beginning of the $$$l$$$-th second, equals to $$$v$$$ liters) then when will be the moment when the bowl will burst. If that does not happen, then the answer will be $$$-1$$$.

Since Sasha does not want to check what will happen when Fedya's patience ends, and he has already come up with the queries, he is asking you to help him and find the answer for each query of the $$$3$$$-rd type.

It is guaranteed that at any moment of time, there won't be two events which happen at the same second.

Input

The first line contans one integer $$$q$$$ ($$$1 \le q \le 10^5$$$)  — the number of queries.

Each of the next $$$q$$$ lines have one of the following formats:

 1 t s ($$$1 \le t \le 10^9$$$, $$$-10^9 \le s \le 10^9$$$), means that a new event is added, which means that starting from the $$$t$$$-th second the tap's speed will be equal to $$$s$$$.

 2 t ($$$1 \le t \le 10^9$$$), means that the event which happens at the $$$t$$$-th second must be deleted. Guaranteed that such exists.

 3 l r v ($$$1 \le l \le r \le 10^9$$$, $$$0 \le v \le 10^9$$$), means that you should simulate the process from the very beginning of the $$$l$$$-th second till the very beginning of the $$$r$$$-th second inclusive, and to say when will the bowl burst.

It is guaranteed that $$$t$$$, $$$s$$$, $$$l$$$, $$$r$$$, $$$v$$$ in all the queries are integers.

Also, it is guaranteed that there is at least one query of the $$$3$$$-rd type, and there won't be a query of the $$$1$$$-st type with such $$$t$$$, that there already exists an event which happens at that second $$$t$$$.

Output

For each query of the $$$3$$$-rd type, print in a new line the moment when the bowl will burst or print $$$-1$$$ if it won't happen.

Your answer will be considered correct if it's absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Examples

Input

6
1 2 1
1 4 -3
3 1 6 1
3 1 6 3
3 1 6 4
3 1 6 5

Output

5
5.666667
6
-1

Input

10
1 2 2
1 4 4
1 7 -10
3 2 4 1
3 5 6 0
3 1 15 1
2 4
3 1 15 1
1 8 1
3 1 15 1

Output

-1
5
8.7
8.1
-1

Input

5
1 1000 9999999
1 2000 -9999
3 1000 2000 0
2 1000
3 1000 2002 1

Output

1000
2000.0001

Note

In the first example all the queries of the $$$3$$$-rd type cover all the events, it's simulation is following:

question:
Fedya and Sasha are friends, that's why Sasha knows everything about Fedya.
Fedya keeps his patience in an infinitely large bowl. But, unlike the bowl, Fedya's patience isn't infinite, that is why let $$$v$$$ be the number of liters of Fedya's patience, and, as soon as $$$v$$$ becomes equal to $$$0$$$, the bowl will burst immediately. There is one tap in the bowl which pumps $$$s$$$ liters of patience per second. Notice that $$$s$$$ can be negative, in that case, the tap pumps out the patience. Sasha can do different things, so he is able to change the tap's speed. All actions that Sasha does can be represented as $$$q$$$ queries. There are three types of queries:
 -  "1 t s"  — add a new event, means that starting from the $$$t$$$-th second the tap's speed will be equal to $$$s$$$. -  "2 t"  — delete the event which happens at the $$$t$$$-th second. It is guaranteed that such event exists. -  "3 l r v" — Sasha wonders: if you take all the events for which $$$l \le t \le r$$$ and simulate changes of Fedya's patience from the very beginning of the $$$l$$$-th second till the very beginning of the $$$r$$$-th second inclusive (the initial volume of patience, at the beginning of the $$$l$$$-th second, equals to $$$v$$$ liters) then when will be the moment when the bowl will burst. If that does not happen, then the answer will be $$$-1$$$. Since Sasha does not want to check what will happen when Fedya's patience ends, and he has already come up with the queries, he is asking you to help him and find the answer for each query of the $$$3$$$-rd type.
It is guaranteed that at any moment of time, there won't be two events which happen at the same second.

Input
The first line contans one integer $$$q$$$ ($$$1 \le q \le 10^5$$$)  — the number of queries.
Each of the next $$$q$$$ lines have one of the following formats:
 -  1 t s ($$$1 \le t \le 10^9$$$, $$$-10^9 \le s \le 10^9$$$), means that a new event is added, which means that starting from the $$$t$$$-th second the tap's speed will be equal to $$$s$$$. -  2 t ($$$1 \le t \le 10^9$$$), means that the event which happens at the $$$t$$$-th second must be deleted. Guaranteed that such exists. -  3 l r v ($$$1 \le l \le r \le 10^9$$$, $$$0 \le v \le 10^9$$$), means that you should simulate the process from the very beginning of the $$$l$$$-th second till the very beginning of the $$$r$$$-th second inclusive, and to say when will the bowl burst. It is guaranteed that $$$t$$$, $$$s$$$, $$$l$$$, $$$r$$$, $$$v$$$ in all the queries are integers.
Also, it is guaranteed that there is at least one query of the $$$3$$$-rd type, and there won't be a query of the $$$1$$$-st type with such $$$t$$$, that there already exists an event which happens at that second $$$t$$$.

Output
For each query of the $$$3$$$-rd type, print in a new line the moment when the bowl will burst or print $$$-1$$$ if it won't happen.
Your answer will be considered correct if it's absolute or relative error does not exceed $$$10^{-6}$$$.
Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

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

Output
5
5.666667
6
-1

Input
10
1 2 2
1 4 4
1 7 -10
3 2 4 1
3 5 6 0
3 1 15 1
2 4
3 1 15 1
1 8 1
3 1 15 1

Output
-1
5
8.7
8.1
-1

Input
5
1 1000 9999999
1 2000 -9999
3 1000 2000 0
2 1000
3 1000 2002 1

Output
1000
2000.0001

Note
In the first example all the queries of the $$$3$$$-rd type cover all the events, it's simulation is following:
![image](1.png)

tags: ['Sorting', 'Data structures', 'Implementation']

skill_types: ['Sorting', 'Data structures']

raw_tags: ['data structures', 'binary search', 'implementation']

data_split: test


solutions: ["class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdi = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}\n\t\td = 'right'\n\t\ti = j = 0\n\t\twhile True:\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif d == 'right':\n\t\t\t\t\td = di['right']\n\t\t\t\telif d == 'left':\n\t\t\t\t\td = di['left']\n\t\t\t\telif d == 'down':\n\t\t\t\t\td = di['down']\n\t\t\t\telse:\n\t\t\t\t\td = di['up']\n\t\t\telif d == 'right':\n\t\t\t\tj += 1\n\t\t\t\tif j >= n:\n\t\t\t\t\treturn (i, n - 1)\n\t\t\telif d == 'left':\n\t\t\t\tj -= 1\n\t\t\t\tif j < 0:\n\t\t\t\t\treturn (i, 0)\n\t\t\telif d == 'down':\n\t\t\t\ti += 1\n\t\t\t\tif i >= m:\n\t\t\t\t\treturn (m - 1, j)\n\t\t\telse:\n\t\t\t\ti -= 1\n\t\t\t\tif i < 0:\n\t\t\t\t\treturn (0, j)\n", "class Solution:\n\n\tdef endPoints(self, mat, m, n):\n\t\tR = len(mat)\n\t\tC = len(mat[0])\n\t\tdire = 'R'\n\t\ti = j = 0\n\t\t(li, lj) = (0, 0)\n\t\twhile i >= 0 and i < R and (j >= 0) and (j < C):\n\t\t\tif mat[i][j] == 1:\n\t\t\t\tmat[i][j] = 0\n\t\t\t\tif dire == 'R':\n\t\t\t\t\tdire = 'D'\n\t\t\t\telif dire == 'U':\n\t\t\t\t\tdire = 'R'\n\t\t\t\telif dire == 'D':\n\t\t\t\t\tdire = 'L'\n\t\t\t\telif dire == 'L':\n\t\t\t\t\tdire = 'U'\n\t\t\t(li, lj) = (i, j)\n\t\t\tif dire == 'R':\n\t\t\t\tj += 1\n\t\t\telif dire == 'U':\n\t\t\t\ti -= 1\n\t\t\telif dire == 'D':\n\t\t\t\ti += 1\n\t\t\telif dire == 'L':\n\t\t\t\tj -= 1\n\t\treturn (li, lj)\n", "class Solution:\n\n\tdef endPoints(self, matrix, n, m):\n\t\tdirection = {0: (0, 1), 1: (1, 0), 2: (0, -1), 3: (-1, 0)}\n\t\ti = 0\n\t\tj = 0\n\t\tgo = 0\n\t\twhile 0 <= i < n and 0 <= j < m:\n\t\t\tif matrix[i][j]:\n\t\t\t\tgo += 1\n\t\t\t\tgo %= 4\n\t\t\tmatrix[i][j] = 0\n\t\t\ti += direction[go][0]\n\t\t\tj += direction[go][1]\n\t\ti -= direction[go][0]\n\t\tj -= direction[go][1]\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\ti = 0\n\t\tj = 0\n\t\tcurser = 'right'\n\t\twhile j < n and j >= 0 and (i < m) and (i >= 0):\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif curser == 'right':\n\t\t\t\t\tj += 1\n\t\t\t\telif curser == 'left':\n\t\t\t\t\tj -= 1\n\t\t\t\telif curser == 'up':\n\t\t\t\t\ti -= 1\n\t\t\t\telif curser == 'down':\n\t\t\t\t\ti += 1\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif curser == 'up':\n\t\t\t\t\tcurser = 'right'\n\t\t\t\t\tj += 1\n\t\t\t\telif curser == 'down':\n\t\t\t\t\tcurser = 'left'\n\t\t\t\t\tj -= 1\n\t\t\t\telif curser == 'left':\n\t\t\t\t\tcurser = 'up'\n\t\t\t\t\ti -= 1\n\t\t\t\telif curser == 'right':\n\t\t\t\t\tcurser = 'down'\n\t\t\t\t\ti += 1\n\t\tif i >= m:\n\t\t\ti = m - 1\n\t\telif i < 0:\n\t\t\ti = 0\n\t\telif j >= n:\n\t\t\tj = n - 1\n\t\telif j < 0:\n\t\t\tj = 0\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\n\t\tdef get(x, y, d):\n\t\t\tif d == 'R':\n\t\t\t\treturn (x, y + 1)\n\t\t\telif d == 'L':\n\t\t\t\treturn (x, y - 1)\n\t\t\telif d == 'U':\n\t\t\t\treturn (x - 1, y)\n\t\t\telse:\n\t\t\t\treturn (x + 1, y)\n\n\t\tdef solve(x, y, d):\n\t\t\tif matrix[x][y] == 0:\n\t\t\t\t(nx, ny) = get(x, y, d)\n\t\t\t\tnd = d\n\t\t\telse:\n\t\t\t\tmatrix[x][y] = 0\n\t\t\t\tif d == 'U':\n\t\t\t\t\t(nx, ny) = get(x, y, 'R')\n\t\t\t\t\tnd = 'R'\n\t\t\t\telif d == 'R':\n\t\t\t\t\t(nx, ny) = get(x, y, 'D')\n\t\t\t\t\tnd = 'D'\n\t\t\t\telif d == 'D':\n\t\t\t\t\t(nx, ny) = get(x, y, 'L')\n\t\t\t\t\tnd = 'L'\n\t\t\t\telif d == 'L':\n\t\t\t\t\t(nx, ny) = get(x, y, 'U')\n\t\t\t\t\tnd = 'U'\n\t\t\tif 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]):\n\t\t\t\treturn solve(nx, ny, nd)\n\t\t\telse:\n\t\t\t\treturn (x, y)\n\t\treturn solve(0, 0, 'R')\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdirection = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}\n\t\t(i, j) = (0, 0)\n\t\tcurr = 'right'\n\t\twhile True:\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif curr == 'left':\n\t\t\t\t\tj -= 1\n\t\t\t\t\tif j < 0:\n\t\t\t\t\t\treturn [i, j + 1]\n\t\t\t\telif curr == 'right':\n\t\t\t\t\tj += 1\n\t\t\t\t\tif j > n - 1:\n\t\t\t\t\t\treturn [i, j - 1]\n\t\t\t\telif curr == 'down':\n\t\t\t\t\ti += 1\n\t\t\t\t\tif i > m - 1:\n\t\t\t\t\t\treturn [i - 1, j]\n\t\t\t\telif curr == 'up':\n\t\t\t\t\ti -= 1\n\t\t\t\t\tif i < 0:\n\t\t\t\t\t\treturn [i + 1, j]\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tcurr = direction[curr]\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdire = 'r'\n\t\t(i, j) = (0, 0)\n\t\t(x, y) = (0, 0)\n\t\twhile True:\n\t\t\tif i >= m or i < 0 or j >= n or (j < 0):\n\t\t\t\treturn [x, y]\n\t\t\telse:\n\t\t\t\t(x, y) = (i, j)\n\t\t\t\tif matrix[i][j] == 0:\n\t\t\t\t\tif dire == 'd':\n\t\t\t\t\t\ti += 1\n\t\t\t\t\telif dire == 'u':\n\t\t\t\t\t\ti -= 1\n\t\t\t\t\telif dire == 'l':\n\t\t\t\t\t\tj -= 1\n\t\t\t\t\telif dire == 'r':\n\t\t\t\t\t\tj += 1\n\t\t\t\telse:\n\t\t\t\t\tif dire == 'r':\n\t\t\t\t\t\tdire = 'd'\n\t\t\t\t\t\ti += 1\n\t\t\t\t\telif dire == 'u':\n\t\t\t\t\t\tdire = 'r'\n\t\t\t\t\t\tj += 1\n\t\t\t\t\telif dire == 'd':\n\t\t\t\t\t\tdire = 'l'\n\t\t\t\t\t\tj -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tdire = 'u'\n\t\t\t\t\t\ti -= 1\n\t\t\t\t\tmatrix[x][y] = 0\n", "class Solution:\n\n\tdef isSafe(self, m, n, i, j):\n\t\tif i < 0 or j < 0 or i >= m or (j >= n):\n\t\t\treturn False\n\t\treturn True\n\n\tdef endPoints(self, matrix, m, n):\n\t\ti = 0\n\t\tj = 0\n\t\tcurr_d = 'r'\n\t\tnew_d = {'r': 'd', 'l': 'u', 'u': 'r', 'd': 'l'}\n\t\twhile self.isSafe(m, n, i, j):\n\t\t\tcurr_i = i\n\t\t\tcurr_j = j\n\t\t\tif matrix[curr_i][curr_j] == 1:\n\t\t\t\tturn = new_d[curr_d]\n\t\t\t\tmatrix[curr_i][curr_j] = 0\n\t\t\t\tif turn == 'd':\n\t\t\t\t\ti += 1\n\t\t\t\telif turn == 'u':\n\t\t\t\t\ti -= 1\n\t\t\t\telif turn == 'r':\n\t\t\t\t\tj += 1\n\t\t\t\telif turn == 'l':\n\t\t\t\t\tj -= 1\n\t\t\t\tcurr_d = turn\n\t\t\telif curr_d == 'd':\n\t\t\t\ti += 1\n\t\t\telif curr_d == 'u':\n\t\t\t\ti -= 1\n\t\t\telif curr_d == 'r':\n\t\t\t\tj += 1\n\t\t\telif curr_d == 'l':\n\t\t\t\tj -= 1\n\t\treturn (curr_i, curr_j)\n", "class Solution:\n\n\tdef endPoints(self, mat, m, n):\n\n\t\tdef dfs(i, j, state):\n\t\t\tif i < 0:\n\t\t\t\treturn (i + 1, j)\n\t\t\telif i >= m:\n\t\t\t\treturn (i - 1, j)\n\t\t\telif j < 0:\n\t\t\t\treturn (i, j + 1)\n\t\t\telif j >= n:\n\t\t\t\treturn (i, j - 1)\n\t\t\tif state == 'R':\n\t\t\t\tif mat[i][j] == 0:\n\t\t\t\t\treturn dfs(i, j + 1, 'R')\n\t\t\t\telse:\n\t\t\t\t\tmat[i][j] = 0\n\t\t\t\t\treturn dfs(i + 1, j, 'D')\n\t\t\tif state == 'D':\n\t\t\t\tif mat[i][j] == 0:\n\t\t\t\t\treturn dfs(i + 1, j, 'D')\n\t\t\t\telse:\n\t\t\t\t\tmat[i][j] = 0\n\t\t\t\t\treturn dfs(i, j - 1, 'L')\n\t\t\tif state == 'L':\n\t\t\t\tif mat[i][j] == 0:\n\t\t\t\t\treturn dfs(i, j - 1, 'L')\n\t\t\t\telse:\n\t\t\t\t\tmat[i][j] = 0\n\t\t\t\t\treturn dfs(i - 1, j, 'U')\n\t\t\tif state == 'U':\n\t\t\t\tif mat[i][j] == 0:\n\t\t\t\t\treturn dfs(i - 1, j, 'U')\n\t\t\t\telse:\n\t\t\t\t\tmat[i][j] = 0\n\t\t\t\t\treturn dfs(i, j + 1, 'R')\n\t\treturn dfs(0, 0, 'R')\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\t(i, j) = (0, 0)\n\t\tdir = 0\n\t\twhile True:\n\t\t\tdir = (dir + matrix[i][j]) % 4\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\tif dir == 0:\n\t\t\t\tj += 1\n\t\t\telif dir == 1:\n\t\t\t\ti += 1\n\t\t\telif dir == 2:\n\t\t\t\tj -= 1\n\t\t\telif dir == 3:\n\t\t\t\ti -= 1\n\t\t\tif i < 0:\n\t\t\t\ti += 1\n\t\t\t\tbreak\n\t\t\telif j < 0:\n\t\t\t\tj += 1\n\t\t\t\tbreak\n\t\t\telif j >= len(matrix[0]):\n\t\t\t\tj -= 1\n\t\t\t\tbreak\n\t\t\telif i >= len(matrix):\n\t\t\t\ti -= 1\n\t\t\t\tbreak\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdirection = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}\n\t\t(i, j) = (0, 0)\n\t\tcurr = 'right'\n\t\twhile True:\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif curr == 'left':\n\t\t\t\t\tj -= 1\n\t\t\t\t\tif j < 0:\n\t\t\t\t\t\treturn [i, j + 1]\n\t\t\t\telif curr == 'right':\n\t\t\t\t\tj += 1\n\t\t\t\t\tif j > n - 1:\n\t\t\t\t\t\treturn [i, j - 1]\n\t\t\t\telif curr == 'down':\n\t\t\t\t\ti += 1\n\t\t\t\t\tif i > m - 1:\n\t\t\t\t\t\treturn [i - 1, j]\n\t\t\t\telif curr == 'up':\n\t\t\t\t\ti -= 1\n\t\t\t\t\tif i < 0:\n\t\t\t\t\t\treturn [i + 1, j]\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tcurr = direction[curr]\nif __name__ == '__main__':\n\tt = int(input())\n\tfor _ in range(t):\n\t\t(r, c) = map(int, input().strip().split())\n\t\tmatrix = []\n\t\tfor i in range(r):\n\t\t\tline = [int(x) for x in input().strip().split()]\n\t\t\tmatrix.append(line)\n\t\tob = Solution()\n\t\tans = ob.endPoints(matrix, r, c)\n\t\tprint('(', ans[0], ', ', ans[1], ')', sep='')\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\ti = 0\n\t\tj = 0\n\t\tcurr_dir = 'R'\n\t\twhile i < m and j < n and (j >= 0) and (i >= 0):\n\t\t\tif matrix[i][j] == 0 and curr_dir == 'R':\n\t\t\t\tj += 1\n\t\t\telif matrix[i][j] == 0 and curr_dir == 'L':\n\t\t\t\tj -= 1\n\t\t\telif matrix[i][j] == 0 and curr_dir == 'U':\n\t\t\t\ti -= 1\n\t\t\telif matrix[i][j] == 0 and curr_dir == 'D':\n\t\t\t\ti += 1\n\t\t\telif matrix[i][j] == 1 and curr_dir == 'R':\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tcurr_dir = 'D'\n\t\t\t\ti += 1\n\t\t\telif matrix[i][j] == 1 and curr_dir == 'L':\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tcurr_dir = 'U'\n\t\t\t\ti -= 1\n\t\t\telif matrix[i][j] == 1 and curr_dir == 'D':\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tcurr_dir = 'L'\n\t\t\t\tj -= 1\n\t\t\telif matrix[i][j] == 1 and curr_dir == 'U':\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tcurr_dir = 'R'\n\t\t\t\tj += 1\n\t\tif i < 0:\n\t\t\ti += 1\n\t\tif j < 0:\n\t\t\tj += 1\n\t\tif i >= m:\n\t\t\ti -= 1\n\t\tif j >= n:\n\t\t\tj -= 1\n\t\treturn [i, j]\n", "class Solution:\n\n\tdef endPoints(self, mat, m, n):\n\t\tguide = {'top': 'right', 'right': 'bottom', 'bottom': 'left', 'left': 'top'}\n\t\tcurrdir = 'right'\n\t\trow = 0\n\t\tcol = 0\n\t\ttop = 0\n\t\tleft = 0\n\t\tright = len(mat[0])\n\t\tbottom = len(mat)\n\t\twhile left <= col < right and top <= row < bottom:\n\t\t\tif mat[row][col] == 0:\n\t\t\t\tif currdir == 'right':\n\t\t\t\t\tif col != right - 1:\n\t\t\t\t\t\tcol += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn (row, col)\n\t\t\t\telif currdir == 'left':\n\t\t\t\t\tif col != left:\n\t\t\t\t\t\tcol -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn (row, col)\n\t\t\t\telif currdir == 'top':\n\t\t\t\t\tif row != top:\n\t\t\t\t\t\trow -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn (row, col)\n\t\t\t\telif currdir == 'bottom':\n\t\t\t\t\tif row != bottom - 1:\n\t\t\t\t\t\trow += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn (row, col)\n\t\t\telif mat[row][col] == 1:\n\t\t\t\tmat[row][col] = 0\n\t\t\t\tcurrdir = guide[currdir]\n\t\t\t\tif currdir == 'right':\n\t\t\t\t\tif col != right - 1:\n\t\t\t\t\t\tcol += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn (row, col)\n\t\t\t\telif currdir == 'left':\n\t\t\t\t\tif col != left:\n\t\t\t\t\t\tcol -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn (row, col)\n\t\t\t\telif currdir == 'top':\n\t\t\t\t\tif row != top:\n\t\t\t\t\t\trow -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn (row, col)\n\t\t\t\telif currdir == 'bottom':\n\t\t\t\t\tif row != bottom - 1:\n\t\t\t\t\t\trow += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\treturn (row, col)\n\t\treturn (row, col)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tchange = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n\t\tind = 0\n\t\ti = j = 0\n\t\twhile i > -1 and i < m and (j > -1) and (j < n):\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tind = (ind + 1) % 4\n\t\t\t\tmatrix[i][j] = 0\n\t\t\tcell = [i, j]\n\t\t\ti += change[ind][0]\n\t\t\tj += change[ind][1]\n\t\treturn cell\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\n\t\tdef is_safe(m, n, i, j):\n\t\t\tif i < 0:\n\t\t\t\treturn False\n\t\t\telif j < 0:\n\t\t\t\treturn False\n\t\t\telif i >= m:\n\t\t\t\treturn False\n\t\t\telif j >= n:\n\t\t\t\treturn False\n\t\t\treturn True\n\n\t\tdef checking_the_exit():\n\t\t\ti = 0\n\t\t\tj = 0\n\t\t\tcurrent_direction = 'r'\n\t\t\tchanged_direction = {'l': 'u', 'u': 'r', 'r': 'd', 'd': 'l'}\n\t\t\twhile is_safe(m, n, i, j):\n\t\t\t\tcurrent_i = i\n\t\t\t\tcurrent_j = j\n\t\t\t\tif matrix[i][j] == 1:\n\t\t\t\t\tmove_in = changed_direction[current_direction]\n\t\t\t\t\tmatrix[i][j] = 0\n\t\t\t\t\tif move_in == 'u':\n\t\t\t\t\t\ti -= 1\n\t\t\t\t\telif move_in == 'd':\n\t\t\t\t\t\ti += 1\n\t\t\t\t\telif move_in == 'l':\n\t\t\t\t\t\tj -= 1\n\t\t\t\t\telif move_in == 'r':\n\t\t\t\t\t\tj += 1\n\t\t\t\t\tcurrent_direction = move_in\n\t\t\t\telif current_direction == 'u':\n\t\t\t\t\ti -= 1\n\t\t\t\telif current_direction == 'd':\n\t\t\t\t\ti += 1\n\t\t\t\telif current_direction == 'l':\n\t\t\t\t\tj -= 1\n\t\t\t\telif current_direction == 'r':\n\t\t\t\t\tj += 1\n\t\t\treturn (current_i, current_j)\n\t\treturn checking_the_exit()\n", "def issafe(m, n, i, j):\n\tif i < 0:\n\t\treturn False\n\tif j < 0:\n\t\treturn False\n\tif i >= m:\n\t\treturn False\n\tif j >= n:\n\t\treturn False\n\treturn True\n\nclass Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\ti = 0\n\t\tj = 0\n\t\tcur_pos = 'r'\n\t\tdi = {'l': 'u', 'u': 'r', 'r': 'd', 'd': 'l'}\n\t\twhile issafe(m, n, i, j):\n\t\t\tcur_i = i\n\t\t\tcur_j = j\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tmove = di[cur_pos]\n\t\t\t\tif move == 'u':\n\t\t\t\t\ti -= 1\n\t\t\t\telif move == 'l':\n\t\t\t\t\tj -= 1\n\t\t\t\telif move == 'r':\n\t\t\t\t\tj += 1\n\t\t\t\telif move == 'd':\n\t\t\t\t\ti += 1\n\t\t\t\tcur_pos = move\n\t\t\telif cur_pos == 'u':\n\t\t\t\ti -= 1\n\t\t\telif cur_pos == 'l':\n\t\t\t\tj -= 1\n\t\t\telif cur_pos == 'r':\n\t\t\t\tj += 1\n\t\t\telif cur_pos == 'd':\n\t\t\t\ti += 1\n\t\treturn (cur_i, cur_j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tpx = py = x = y = 0\n\t\tds = [(0, -1), (1, 0), (0, 1), (-1, 0)]\n\t\tdi = 1\n\t\twhile 0 <= x and x < n and (0 <= y) and (y < m):\n\t\t\tif matrix[y][x] == 0:\n\t\t\t\t(px, py) = (x, y)\n\t\t\t\tx += ds[di][0]\n\t\t\t\ty += ds[di][1]\n\t\t\telse:\n\t\t\t\tmatrix[y][x] = 0\n\t\t\t\tdi = (di + 1) % 4\n\t\treturn (py, px)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tup = False\n\t\tdown = False\n\t\tright = True\n\t\tleft = False\n\t\tstart_row = start_col = 0\n\t\twhile 0 <= start_row < m and 0 <= start_col < n:\n\t\t\tif matrix[start_row][start_col] == 0:\n\t\t\t\tif right:\n\t\t\t\t\tstart_col += 1\n\t\t\t\telif left:\n\t\t\t\t\tstart_col -= 1\n\t\t\t\telif up:\n\t\t\t\t\tstart_row -= 1\n\t\t\t\telif down:\n\t\t\t\t\tstart_row += 1\n\t\t\telse:\n\t\t\t\tmatrix[start_row][start_col] = 0\n\t\t\t\tif right:\n\t\t\t\t\tright = False\n\t\t\t\t\tdown = True\n\t\t\t\telif left:\n\t\t\t\t\tleft = False\n\t\t\t\t\tup = True\n\t\t\t\telif up:\n\t\t\t\t\tup = False\n\t\t\t\t\tright = True\n\t\t\t\telif down:\n\t\t\t\t\tdown = False\n\t\t\t\t\tleft = True\n\t\tif start_row < 0:\n\t\t\tstart_row += 1\n\t\tif start_row >= m:\n\t\t\tstart_row -= 1\n\t\tif start_col < 0:\n\t\t\tstart_col += 1\n\t\tif start_col >= n:\n\t\t\tstart_col -= 1\n\t\treturn (start_row, start_col)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tk = 'r'\n\t\ti = 0\n\t\tj = 0\n\t\twhile i >= 0 and j >= 0 and (i < m) and (j < n):\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tans1 = i\n\t\t\t\tans2 = j\n\t\t\t\tif k == 'r':\n\t\t\t\t\tj += 1\n\t\t\t\telif k == 'd':\n\t\t\t\t\ti += 1\n\t\t\t\telif k == 'l':\n\t\t\t\t\tj -= 1\n\t\t\t\telif k == 'u':\n\t\t\t\t\ti -= 1\n\t\t\telse:\n\t\t\t\tans1 = i\n\t\t\t\tans2 = j\n\t\t\t\tif k == 'r':\n\t\t\t\t\tmatrix[i][j] = 0\n\t\t\t\t\tk = 'd'\n\t\t\t\t\ti += 1\n\t\t\t\telif k == 'd':\n\t\t\t\t\tmatrix[i][j] = 0\n\t\t\t\t\tk = 'l'\n\t\t\t\t\tj -= 1\n\t\t\t\telif k == 'l':\n\t\t\t\t\tmatrix[i][j] = 0\n\t\t\t\t\tk = 'u'\n\t\t\t\t\ti -= 1\n\t\t\t\telif k == 'u':\n\t\t\t\t\tmatrix[i][j] = 0\n\t\t\t\t\tk = 'r'\n\t\t\t\t\tj += 1\n\t\treturn (ans1, ans2)\n", "U = (-1, 0)\nD = (1, 0)\nL = (0, -1)\nR = (0, 1)\nchanges = {U: R, R: D, D: L, L: U}\n\nclass Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdir = R\n\t\t(ui, uj) = (0, 0)\n\t\tprev = (0, 0)\n\t\twhile ui in range(m) and uj in range(n):\n\t\t\tif matrix[ui][uj] == 1:\n\t\t\t\tdir = changes[dir]\n\t\t\t\tmatrix[ui][uj] = 0\n\t\t\telse:\n\t\t\t\tprev = (ui, uj)\n\t\t\t\t(di, dj) = dir\n\t\t\t\tui += di\n\t\t\t\tuj += dj\n\t\treturn prev\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdirection = {1: 2, 2: 3, 3: 4, 4: 1}\n\t\tcurr_direction = 2\n\t\t(x, y) = (0, 0)\n\t\twhile True:\n\t\t\t(prev_x, prev_y) = (x, y)\n\t\t\tif matrix[x][y] == 0:\n\t\t\t\tif curr_direction == 1:\n\t\t\t\t\tx -= 1\n\t\t\t\telif curr_direction == 2:\n\t\t\t\t\ty += 1\n\t\t\t\telif curr_direction == 3:\n\t\t\t\t\tx += 1\n\t\t\t\telse:\n\t\t\t\t\ty -= 1\n\t\t\telse:\n\t\t\t\tmatrix[x][y] = 0\n\t\t\t\tcurr_direction = direction[curr_direction]\n\t\t\t\tif curr_direction == 1:\n\t\t\t\t\tx -= 1\n\t\t\t\telif curr_direction == 2:\n\t\t\t\t\ty += 1\n\t\t\t\telif curr_direction == 3:\n\t\t\t\t\tx += 1\n\t\t\t\telse:\n\t\t\t\t\ty -= 1\n\t\t\tif x < 0 or y < 0 or x >= m or (y >= n):\n\t\t\t\treturn (prev_x, prev_y)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tverticalShift = 0\n\t\thorizontalShift = 1\n\t\ti = 0\n\t\tj = 0\n\t\twhile True:\n\t\t\tif i < 0 or i >= m:\n\t\t\t\tbreak\n\t\t\tif j < 0 or j >= n:\n\t\t\t\tbreak\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif verticalShift == 0 and horizontalShift == 1:\n\t\t\t\t\tverticalShift = 1\n\t\t\t\t\thorizontalShift = 0\n\t\t\t\telif verticalShift == 1 and horizontalShift == 0:\n\t\t\t\t\tverticalShift = 0\n\t\t\t\t\thorizontalShift = -1\n\t\t\t\telif verticalShift == 0 and horizontalShift == -1:\n\t\t\t\t\tverticalShift = -1\n\t\t\t\t\thorizontalShift = 0\n\t\t\t\telif verticalShift == -1 and horizontalShift == 0:\n\t\t\t\t\tverticalShift = 0\n\t\t\t\t\thorizontalShift = 1\n\t\t\ti += verticalShift\n\t\t\tj += horizontalShift\n\t\treturn (i - verticalShift, j - horizontalShift)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdirection = [0, 1, 0, -1]\n\t\tdr = row = col = 0\n\t\tdc = 1\n\t\twhile 0 <= row < m and 0 <= col < n:\n\t\t\tif matrix[row][col] == 1:\n\t\t\t\tmatrix[row][col] = 0\n\t\t\t\tdr = (dr + 1) % 4\n\t\t\t\tdc = (dc + 1) % 4\n\t\t\trow += direction[dr]\n\t\t\tcol += direction[dc]\n\t\treturn (row - direction[dr], col - direction[dc])\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\td = 0\n\t\ta = 0\n\t\tb = 0\n\t\twhile 0 <= a < m and 0 <= b < n:\n\t\t\tv = matrix[a][b]\n\t\t\tif v == 0:\n\t\t\t\tif d == 0:\n\t\t\t\t\tb += 1\n\t\t\t\telif d == 1:\n\t\t\t\t\ta += 1\n\t\t\t\telif d == 2:\n\t\t\t\t\tb -= 1\n\t\t\t\telse:\n\t\t\t\t\ta -= 1\n\t\t\telse:\n\t\t\t\td = (d + 1) % 4\n\t\t\t\tmatrix[a][b] = 0\n\t\tif a == -1:\n\t\t\ta = 0\n\t\telif a == m:\n\t\t\ta -= 1\n\t\telif b == -1:\n\t\t\tb = 0\n\t\telif b == n:\n\t\t\tb -= 1\n\t\treturn [a, b]\n", "change_dir = {'u': 'r', 'r': 'd', 'd': 'l', 'l': 'u'}\n\nclass Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\treturn self.operation(matrix, 0, 0, 'r', m, n)\n\n\tdef operation(self, matrix, r, c, d, m, n):\n\t\tif matrix[r][c]:\n\t\t\tmatrix[r][c] = 0\n\t\t\td = change_dir[d]\n\t\tnew_r = r\n\t\tnew_c = c\n\t\tif d == 'r':\n\t\t\tnew_c = new_c + 1\n\t\telif d == 'd':\n\t\t\tnew_r = new_r + 1\n\t\telif d == 'l':\n\t\t\tnew_c = new_c - 1\n\t\telif d == 'u':\n\t\t\tnew_r = new_r - 1\n\t\tif new_r < 0 or new_r == m or new_c < 0 or (new_c == n):\n\t\t\treturn [r, c]\n\t\treturn self.operation(matrix, new_r, new_c, d, m, n)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdir = 'right'\n\t\ti = 0\n\t\tj = 0\n\t\twhile i < m and j < n and (i >= 0) and (j >= 0):\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif dir == 'right':\n\t\t\t\t\tj += 1\n\t\t\t\telif dir == 'left':\n\t\t\t\t\tj -= 1\n\t\t\t\telif dir == 'down':\n\t\t\t\t\ti += 1\n\t\t\t\telif dir == 'up':\n\t\t\t\t\ti -= 1\n\t\t\telif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif dir == 'right':\n\t\t\t\t\tdir = 'down'\n\t\t\t\t\ti += 1\n\t\t\t\telif dir == 'left':\n\t\t\t\t\tdir = 'up'\n\t\t\t\t\ti -= 1\n\t\t\t\telif dir == 'down':\n\t\t\t\t\tdir = 'left'\n\t\t\t\t\tj -= 1\n\t\t\t\telif dir == 'up':\n\t\t\t\t\tdir = 'right'\n\t\t\t\t\tj += 1\n\t\tif i == -1:\n\t\t\treturn list([i + 1, j])\n\t\telif j == -1:\n\t\t\treturn list([i, j + 1])\n\t\telif j == n:\n\t\t\treturn list([i, j - 1])\n\t\telif i == m:\n\t\t\treturn list([i - 1, j])\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdirection = 2\n\t\t(i, j) = (0, 0)\n\t\twhile True:\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif direction == 2:\n\t\t\t\t\tif j + 1 < n:\n\t\t\t\t\t\tj += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\telif direction == -2:\n\t\t\t\t\tif j - 1 >= 0:\n\t\t\t\t\t\tj -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\telif direction == 1:\n\t\t\t\t\tif i - 1 >= 0:\n\t\t\t\t\t\ti -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\telif direction == -1:\n\t\t\t\t\tif i + 1 < m:\n\t\t\t\t\t\ti += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\telif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif direction == 2:\n\t\t\t\t\tdirection = -1\n\t\t\t\t\tif i + 1 < m:\n\t\t\t\t\t\ti += 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\telif direction == -2:\n\t\t\t\t\tdirection = 1\n\t\t\t\t\tif i - 1 >= 0:\n\t\t\t\t\t\ti -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\telif direction == 1:\n\t\t\t\t\tdirection = 2\n\t\t\t\t\tif j + 1 < n:\n\t\t\t\t\t\tj = j + 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\telif direction == -1:\n\t\t\t\t\tdirection = -2\n\t\t\t\t\tif j - 1 >= 0:\n\t\t\t\t\t\tj -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\treturn tuple([i, j])\n", "class Solution:\n\n\tdef endPoints(self, matrix, n, m):\n\t\tdirection = 'r'\n\t\ti = 0\n\t\tj = 0\n\t\twhile i <= n and j <= m:\n\t\t\tif i >= n or j >= m or i < 0 or (j < 0):\n\t\t\t\tif i >= n and j >= m:\n\t\t\t\t\ti -= 1\n\t\t\t\t\tj -= 1\n\t\t\t\telif i >= n:\n\t\t\t\t\ti -= 1\n\t\t\t\telif j >= m:\n\t\t\t\t\tj -= 1\n\t\t\t\telif i < 0 and j < 0:\n\t\t\t\t\ti += 1\n\t\t\t\t\tj += 1\n\t\t\t\telif i < 0:\n\t\t\t\t\ti += 1\n\t\t\t\telse:\n\t\t\t\t\tj += 1\n\t\t\t\ttup = (i, j)\n\t\t\t\treturn tup\n\t\t\t\tbreak\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif direction == 'r':\n\t\t\t\t\tj += 1\n\t\t\t\telif direction == 'd':\n\t\t\t\t\ti += 1\n\t\t\t\telif direction == 'l':\n\t\t\t\t\tj -= 1\n\t\t\t\telse:\n\t\t\t\t\ti -= 1\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif direction == 'r':\n\t\t\t\t\tdirection = 'd'\n\t\t\t\t\ti += 1\n\t\t\t\telif direction == 'd':\n\t\t\t\t\tdirection = 'l'\n\t\t\t\t\tj -= 1\n\t\t\t\telif direction == 'l':\n\t\t\t\t\tdirection = 'u'\n\t\t\t\t\ti -= 1\n\t\t\t\telse:\n\t\t\t\t\tdirection = 'r'\n\t\t\t\t\tj += 1\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\n\t\tdef check(i, j, m, n):\n\t\t\tif i < 0 and j >= 0:\n\t\t\t\ti1 = i + 1\n\t\t\t\treturn (i1, j)\n\t\t\telif j < 0 and i >= 0:\n\t\t\t\tj1 = j + 1\n\t\t\t\treturn (i, j1)\n\t\t\telif i > m - 1 and j >= 0:\n\t\t\t\treturn (m - 1, j)\n\t\t\telif i >= 0 and j > n - 1:\n\t\t\t\treturn (i, n - 1)\n\t\t\telse:\n\t\t\t\treturn (-1, -1)\n\t\ti = 0\n\t\tj = 0\n\t\tdirection = 'r'\n\t\twhile True:\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif direction == 'r':\n\t\t\t\t\tj += 1\n\t\t\t\telif direction == 'u':\n\t\t\t\t\ti -= 1\n\t\t\t\telif direction == 'l':\n\t\t\t\t\tj -= 1\n\t\t\t\telif direction == 'd':\n\t\t\t\t\ti += 1\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif direction == 'u':\n\t\t\t\t\tdirection = 'r'\n\t\t\t\telif direction == 'r':\n\t\t\t\t\tdirection = 'd'\n\t\t\t\telif direction == 'd':\n\t\t\t\t\tdirection = 'l'\n\t\t\t\telif direction == 'l':\n\t\t\t\t\tdirection = 'u'\n\t\t\t(k, l) = check(i, j, m, n)\n\t\t\tif k != -1 and l != -1:\n\t\t\t\treturn (k, l)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\t(i, j, d) = (0, 0, 'R')\n\t\tdir = {'R': [+0, +1], 'D': [+1, +0], 'L': [+0, -1], 'U': [-1, +0]}\n\t\twhile (i < m) & (j < n) & (i >= 0) & (j >= 0):\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tif d == 'R':\n\t\t\t\t\td = 'D'\n\t\t\t\telif d == 'D':\n\t\t\t\t\td = 'L'\n\t\t\t\telif d == 'L':\n\t\t\t\t\td = 'U'\n\t\t\t\telse:\n\t\t\t\t\td = 'R'\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t(i, j) = (i + dir[d][0], j + dir[d][1])\n\t\tif i == m:\n\t\t\ti -= 1\n\t\telif j == n:\n\t\t\tj -= 1\n\t\telif i == -1:\n\t\t\ti = 0\n\t\telif j == -1:\n\t\t\tj = 0\n\t\treturn [i, j]\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdir = 0\n\t\ti = 0\n\t\tj = 0\n\t\twhile 0 <= i < m and 0 <= j < n:\n\t\t\tv = matrix[i][j]\n\t\t\tif v == 0:\n\t\t\t\tif dir == 0:\n\t\t\t\t\tj = j + 1\n\t\t\t\telif dir == 1:\n\t\t\t\t\ti = i + 1\n\t\t\t\telif dir == 2:\n\t\t\t\t\tj = j - 1\n\t\t\t\telse:\n\t\t\t\t\ti = i - 1\n\t\t\telse:\n\t\t\t\tdir = (dir + 1) % 4\n\t\t\t\tmatrix[i][j] = 0\n\t\tif i == -1:\n\t\t\ti = 0\n\t\telif i == m:\n\t\t\ti = i - 1\n\t\telif j == -1:\n\t\t\tj = 0\n\t\telif j == n:\n\t\t\tj = j - 1\n\t\treturn [i, j]\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\t(i, j) = (0, 0)\n\t\tdir = 'r'\n\t\twhile i >= 0 and j >= 0 and (i < m) and (j < n):\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif dir == 'r':\n\t\t\t\t\tj += 1\n\t\t\t\telif dir == 'l':\n\t\t\t\t\tj -= 1\n\t\t\t\telif dir == 'u':\n\t\t\t\t\ti -= 1\n\t\t\t\telse:\n\t\t\t\t\ti += 1\n\t\t\telif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif dir == 'r':\n\t\t\t\t\tdir = 'd'\n\t\t\t\t\ti += 1\n\t\t\t\telif dir == 'l':\n\t\t\t\t\tdir = 'u'\n\t\t\t\t\ti -= 1\n\t\t\t\telif dir == 'u':\n\t\t\t\t\tdir = 'r'\n\t\t\t\t\tj += 1\n\t\t\t\telse:\n\t\t\t\t\tdir = 'l'\n\t\t\t\t\tj -= 1\n\t\tif dir == 'l':\n\t\t\treturn [i, j + 1]\n\t\telif dir == 'r':\n\t\t\treturn [i, j - 1]\n\t\telif dir == 'u':\n\t\t\treturn [i + 1, j]\n\t\telse:\n\t\t\treturn [i - 1, j]\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\td = 1\n\t\ti = 0\n\t\tj = 0\n\t\twhile i < m and j < n and (i >= 0) and (j >= 0):\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\td = (d + 1) % 4\n\t\t\telif d == 0:\n\t\t\t\ti -= 1\n\t\t\telif d == 1:\n\t\t\t\tj += 1\n\t\t\telif d == 2:\n\t\t\t\ti += 1\n\t\t\telif d == 3:\n\t\t\t\tj -= 1\n\t\tif i == m:\n\t\t\treturn [i - 1, j]\n\t\telif i < 0:\n\t\t\treturn [i + 1, j]\n\t\telif j < 0:\n\t\t\treturn [i, j + 1]\n\t\telse:\n\t\t\treturn [i, j - 1]\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\t(i, j) = (0, 0)\n\t\td = 'r'\n\t\twhile True:\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif d == 'r':\n\t\t\t\t\td = 'd'\n\t\t\t\telif d == 'd':\n\t\t\t\t\td = 'l'\n\t\t\t\telif d == 'l':\n\t\t\t\t\td = 'u'\n\t\t\t\telif d == 'u':\n\t\t\t\t\td = 'r'\n\t\t\tif d == 'r':\n\t\t\t\tj += 1\n\t\t\telif d == 'u':\n\t\t\t\ti -= 1\n\t\t\telif d == 'd':\n\t\t\t\ti += 1\n\t\t\telif d == 'l':\n\t\t\t\tj -= 1\n\t\t\tif i > m - 1 or j < 0 or j > n - 1 or (i < 0):\n\t\t\t\tbreak\n\t\tif d == 'r':\n\t\t\tj -= 1\n\t\telif d == 'u':\n\t\t\ti += 1\n\t\telif d == 'l':\n\t\t\tj += 1\n\t\telif d == 'd':\n\t\t\ti -= 1\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tans1 = [[0, 0]]\n\t\tans = []\n\t\td = 1\n\t\ti = 0\n\t\tj = 0\n\t\twhile True and i >= 0 and (i < m) and (j < n) and (j >= 0):\n\t\t\ttry:\n\t\t\t\tif matrix[i][j] == 0:\n\t\t\t\t\ta = d % 4\n\t\t\t\t\tif a == 1:\n\t\t\t\t\t\tj += 1\n\t\t\t\t\telif a == 2:\n\t\t\t\t\t\ti += 1\n\t\t\t\t\telif a == 3:\n\t\t\t\t\t\tj -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\ti -= 1\n\t\t\t\tif i >= 0 and i < m and (j < n) and (j >= 0):\n\t\t\t\t\tans = [i, j]\n\t\t\t\t\tans1.append(ans)\n\t\t\t\tif matrix[i][j] == 1:\n\t\t\t\t\tmatrix[i][j] = 0\n\t\t\t\t\td += 1\n\t\t\t\t\ta = d % 4\n\t\t\t\t\tif a == 1:\n\t\t\t\t\t\tj += 1\n\t\t\t\t\telif a == 2:\n\t\t\t\t\t\ti += 1\n\t\t\t\t\telif a == 3:\n\t\t\t\t\t\tj -= 1\n\t\t\t\t\telse:\n\t\t\t\t\t\ti -= 1\n\t\t\t\tif i >= 0 and i < m and (j < n) and (j >= 0):\n\t\t\t\t\tans = [i, j]\n\t\t\t\t\tans1.append(ans)\n\t\t\texcept:\n\t\t\t\tbreak\n\t\treturn ans1[len(ans1) - 1]\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdirection = 'right'\n\t\t(i, j) = (0, 0)\n\t\twhile i < m and j < n:\n\t\t\tif i < 0 or j < 0:\n\t\t\t\tbreak\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\tif direction == 'up':\n\t\t\t\t\ti -= 1\n\t\t\t\telif direction == 'down':\n\t\t\t\t\ti += 1\n\t\t\t\telif direction == 'right':\n\t\t\t\t\tj += 1\n\t\t\t\telif direction == 'left':\n\t\t\t\t\tj -= 1\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif direction == 'right':\n\t\t\t\t\tdirection = 'down'\n\t\t\t\telif direction == 'down':\n\t\t\t\t\tdirection = 'left'\n\t\t\t\telif direction == 'left':\n\t\t\t\t\tdirection = 'up'\n\t\t\t\telif direction == 'up':\n\t\t\t\t\tdirection = 'right'\n\t\tif i == m:\n\t\t\treturn (i - 1, j)\n\t\telif j == n:\n\t\t\treturn (i, j - 1)\n\t\telif j < 0:\n\t\t\treturn (i, j + 1)\n\t\telse:\n\t\t\treturn (i + 1, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\td1 = {'l': 'u', 'u': 'r', 'r': 'd', 'd': 'l'}\n\t\trowlim = m - 1\n\t\tcollim = n - 1\n\t\tstart = (0, 0)\n\t\td = 'r'\n\t\twhile True:\n\t\t\tval = matrix[start[0]][start[1]]\n\t\t\tif val == 1:\n\t\t\t\tmatrix[start[0]][start[1]] = 0\n\t\t\t\td = d1[d]\n\t\t\telse:\n\t\t\t\tpass\n\t\t\tif d == 'l':\n\t\t\t\tstart1 = (start[0], start[1] - 1)\n\t\t\telif d == 'r':\n\t\t\t\tstart1 = (start[0], start[1] + 1)\n\t\t\telif d == 'u':\n\t\t\t\tstart1 = (start[0] - 1, start[1])\n\t\t\telse:\n\t\t\t\tstart1 = (start[0] + 1, start[1])\n\t\t\tif (start1[0] >= 0 and start1[0] <= rowlim) and (start1[1] >= 0 and start1[1] <= collim):\n\t\t\t\tstart = start1\n\t\t\telse:\n\t\t\t\treturn start\n", "class Solution:\n\n\tdef endPoints(self, mat, m, n):\n\t\ti = 0\n\t\tj = 0\n\t\trf = 1\n\t\tdf = 0\n\t\tlf = 0\n\t\tuf = 0\n\t\twhile (i < m and j < n) and (i >= 0 and j >= 0):\n\t\t\tif mat[i][j] == 1:\n\t\t\t\tif rf == 1:\n\t\t\t\t\tmat[i][j] = 0\n\t\t\t\t\tdf = 1\n\t\t\t\t\trf = 0\n\t\t\t\t\ti += 1\n\t\t\t\telif df == 1:\n\t\t\t\t\tmat[i][j] = 0\n\t\t\t\t\tlf = 1\n\t\t\t\t\tdf = 0\n\t\t\t\t\tj -= 1\n\t\t\t\telif uf == 1:\n\t\t\t\t\tmat[i][j] = 0\n\t\t\t\t\tuf = 0\n\t\t\t\t\trf = 1\n\t\t\t\t\tj += 1\n\t\t\t\telif lf == 1:\n\t\t\t\t\tmat[i][j] = 0\n\t\t\t\t\tlf = 0\n\t\t\t\t\tuf = 1\n\t\t\t\t\ti -= 1\n\t\t\telif rf == 1:\n\t\t\t\tj += 1\n\t\t\telif df == 1:\n\t\t\t\ti += 1\n\t\t\telif lf == 1:\n\t\t\t\tj -= 1\n\t\t\telif uf == 1:\n\t\t\t\ti -= 1\n\t\tif rf == 1:\n\t\t\treturn (i, j - 1)\n\t\telif lf == 1:\n\t\t\treturn (i, j + 1)\n\t\telif uf == 1:\n\t\t\treturn (i + 1, j)\n\t\telif df == 1:\n\t\t\treturn (i - 1, j)\n", "class Solution:\n\n\tdef check(x, y, m, n):\n\t\treturn x >= 0 and y >= 0 and (x < m) and (y < n)\n\n\tdef endPoints(self, matrix, m, n):\n\t\tl = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n\t\tval = 1\n\t\t(row, col) = (0, 0)\n\t\tincRow = 0\n\t\tincCol = 1\n\t\twhile True:\n\t\t\tif matrix[row][col] == 1:\n\t\t\t\tmatrix[row][col] = 0\n\t\t\t\tincRow = l[val][0]\n\t\t\t\tincCol = l[val][1]\n\t\t\t\tval = (val + 1) % 4\n\t\t\telse:\n\t\t\t\trow += incRow\n\t\t\t\tcol += incCol\n\t\t\t\tif not Solution.check(row, col, m, n):\n\t\t\t\t\treturn (row - incRow, col - incCol)\n\t\t\t\t\texit()\n", "next_dir = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}\n\nclass Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\t(cur_pt, direction) = ((0, 0), 'right')\n\t\tprev = cur_pt\n\t\twhile self.is_inside(cur_pt, m, n):\n\t\t\tprev = cur_pt\n\t\t\t(i, j) = cur_pt\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tdirection = next_dir[direction]\n\t\t\tcur_pt = self.get_next_pt(cur_pt, direction)\n\t\treturn prev\n\n\tdef get_next_pt(self, cur_pt, direction):\n\t\t(i, j) = cur_pt\n\t\tif direction == 'up':\n\t\t\treturn (i - 1, j)\n\t\telif direction == 'down':\n\t\t\treturn (i + 1, j)\n\t\telif direction == 'left':\n\t\t\treturn (i, j - 1)\n\t\telse:\n\t\t\treturn (i, j + 1)\n\n\tdef is_inside(self, cur_pt, m, n):\n\t\t(i, j) = cur_pt\n\t\treturn 0 <= i < m and 0 <= j < n\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\ti = 0\n\t\tdi = 'r'\n\t\twhile i < m:\n\t\t\tj = 0\n\t\t\twhile j < n:\n\t\t\t\tif matrix[i][j] == 0:\n\t\t\t\t\tif di == 'r':\n\t\t\t\t\t\tj += 1\n\t\t\t\t\t\tif j >= n:\n\t\t\t\t\t\t\treturn (i, j - 1)\n\t\t\t\t\telif di == 'l':\n\t\t\t\t\t\tj -= 1\n\t\t\t\t\t\tif j < 0:\n\t\t\t\t\t\t\treturn (i, j + 1)\n\t\t\t\t\telif di == 't':\n\t\t\t\t\t\ti -= 1\n\t\t\t\t\t\tif i < 0:\n\t\t\t\t\t\t\treturn (i + 1, j)\n\t\t\t\t\telse:\n\t\t\t\t\t\ti += 1\n\t\t\t\t\t\tif i >= m:\n\t\t\t\t\t\t\treturn (i - 1, j)\n\t\t\t\telif matrix[i][j] == 1:\n\t\t\t\t\tmatrix[i][j] = 0\n\t\t\t\t\tif di == 'r':\n\t\t\t\t\t\tdi = 'd'\n\t\t\t\t\telif di == 'l':\n\t\t\t\t\t\tdi = 't'\n\t\t\t\t\telif di == 't':\n\t\t\t\t\t\tdi = 'r'\n\t\t\t\t\telse:\n\t\t\t\t\t\tdi = 'l'\n", "class Solution:\n\n\tdef isSafe(self, m, n, i, j):\n\t\tif i < 0:\n\t\t\treturn False\n\t\tif i >= m:\n\t\t\treturn False\n\t\tif j >= n:\n\t\t\treturn False\n\t\tif j < 0:\n\t\t\treturn False\n\t\treturn True\n\n\tdef endPoints(self, matrix, m, n):\n\t\ti = 0\n\t\tj = 0\n\t\tcurr_dir = 'r'\n\t\tdirections = {'l': 'u', 'r': 'd', 'u': 'r', 'd': 'l'}\n\t\twhile self.isSafe(m, n, i, j):\n\t\t\tcurr_i = i\n\t\t\tcurr_j = j\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tmove_dir = directions[curr_dir]\n\t\t\t\tif move_dir == 'r':\n\t\t\t\t\tj += 1\n\t\t\t\telif move_dir == 'l':\n\t\t\t\t\tj -= 1\n\t\t\t\telif move_dir == 'u':\n\t\t\t\t\ti -= 1\n\t\t\t\telif move_dir == 'd':\n\t\t\t\t\ti += 1\n\t\t\t\tcurr_dir = move_dir\n\t\t\telse:\n\t\t\t\tif curr_dir == 'l':\n\t\t\t\t\tj -= 1\n\t\t\t\tif curr_dir == 'r':\n\t\t\t\t\tj += 1\n\t\t\t\tif curr_dir == 'u':\n\t\t\t\t\ti -= 1\n\t\t\t\tif curr_dir == 'd':\n\t\t\t\t\ti += 1\n\t\treturn (curr_i, curr_j)\n", "class Solution:\n\n\tdef safe(self, m, n, i, j):\n\t\tflag = True\n\t\tif i < 0:\n\t\t\tflag = False\n\t\tif i >= m:\n\t\t\tflag = False\n\t\tif j < 0:\n\t\t\tflag = False\n\t\tif j >= n:\n\t\t\tflag = False\n\t\treturn flag\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdirection = {'r': 'd', 'u': 'r', 'd': 'l', 'l': 'u'}\n\t\tcurr_dir = 'r'\n\t\ti = 0\n\t\tj = 0\n\t\twhile ob.safe(m, n, i, j):\n\t\t\tcur_i = i\n\t\t\tcur_j = j\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tmov_dir = direction[curr_dir]\n\t\t\t\tif mov_dir == 'u':\n\t\t\t\t\ti = i - 1\n\t\t\t\telif mov_dir == 'l':\n\t\t\t\t\tj = j - 1\n\t\t\t\telif mov_dir == 'r':\n\t\t\t\t\tj = j + 1\n\t\t\t\telif mov_dir == 'd':\n\t\t\t\t\ti = i + 1\n\t\t\t\tcurr_dir = mov_dir\n\t\t\telif curr_dir == 'u':\n\t\t\t\ti = i - 1\n\t\t\telif curr_dir == 'l':\n\t\t\t\tj = j - 1\n\t\t\telif curr_dir == 'r':\n\t\t\t\tj = j + 1\n\t\t\telif curr_dir == 'd':\n\t\t\t\ti = i + 1\n\t\treturn [cur_i, cur_j]\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdic1 = {'left': 'up', 'up': 'right', 'right': 'down', 'down': 'left'}\n\t\tdir_dic = {'left': (0, -1), 'up': (-1, 0), 'right': (0, 1), 'down': (1, 0)}\n\t\tdirection = 'right'\n\t\ti = 0\n\t\tj = 0\n\t\twhile (i >= 0 and i < m) and (j >= 0 and j < n):\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\ti += dir_dic[direction][0]\n\t\t\t\tj += dir_dic[direction][1]\n\t\t\telse:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tdirection = dic1[direction]\n\t\tdir_rev = {'left': (0, 1), 'up': (1, 0), 'right': (0, -1), 'down': (-1, 0)}\n\t\ti += dir_rev[direction][0]\n\t\tj += dir_rev[direction][1]\n\t\treturn (i, j)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\n\t\tdef dfs(i, j, dx, dy):\n\t\t\tif i >= m or j >= n or i < 0 or (j < 0):\n\t\t\t\treturn (i - dx, j - dy)\n\t\t\tif matrix[i][j] == 0:\n\t\t\t\treturn dfs(i + dx, j + dy, dx, dy)\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif dx == 1:\n\t\t\t\t\treturn dfs(i, j - 1, 0, -1)\n\t\t\t\tif dx == -1:\n\t\t\t\t\treturn dfs(i, j + 1, 0, 1)\n\t\t\t\tif dy == 1:\n\t\t\t\t\treturn dfs(i + 1, j, 1, 0)\n\t\t\t\tif dy == -1:\n\t\t\t\t\treturn dfs(i - 1, j, -1, 0)\n\t\treturn dfs(0, 0, 0, 1)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\ti = j = 0\n\t\tx = 0\n\t\ty = 1\n\t\tmapp = {(0, 1): (1, 0), (1, 0): (0, -1), (0, -1): (-1, 0), (-1, 0): (0, 1)}\n\t\twhile 0 <= i < m and 0 <= j < n:\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\t(x, y) = mapp[x, y]\n\t\t\t\tmatrix[i][j] = 0\n\t\t\ti += x\n\t\t\tj += y\n\t\tif i == -1:\n\t\t\ti = 0\n\t\telif i == m:\n\t\t\ti = i - 1\n\t\telif j == -1:\n\t\t\tj = 0\n\t\telif j == n:\n\t\t\tj = j - 1\n\t\treturn [i, j]\n", "up = (0, -1)\ndown = (0, 1)\nleft = (-1, 0)\nright = (1, 0)\ntrans = {up: right, right: down, down: left, left: up}\n\nclass Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tstart = (0, 0)\n\t\tdirection = right\n\t\twhile True:\n\t\t\t(x0, y0) = start\n\t\t\tif matrix[y0][x0] == 1:\n\t\t\t\tdirection = trans[direction]\n\t\t\t\tmatrix[y0][x0] = 0\n\t\t\telse:\n\t\t\t\t(dx, dy) = direction\n\t\t\t\tx = x0 + dx\n\t\t\t\ty = y0 + dy\n\t\t\t\tif x < 0 or x >= n or y < 0 or (y >= m):\n\t\t\t\t\treturn (y0, x0)\n\t\t\t\tstart = (x, y)\n\t\treturn start\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\thmap = {}\n\t\thmap['up'] = 'right'\n\t\thmap['right'] = 'down'\n\t\thmap['down'] = 'left'\n\t\thmap['left'] = 'up'\n\t\tpos = [0, 0]\n\t\td = 'right'\n\t\twhile True:\n\t\t\tif matrix[pos[0]][pos[1]] == 1:\n\t\t\t\td = hmap[d]\n\t\t\tif d == 'right':\n\t\t\t\tif pos[1] + 1 >= len(matrix[0]):\n\t\t\t\t\treturn pos\n\t\t\t\telse:\n\t\t\t\t\tmatrix[pos[0]][pos[1]] = 0\n\t\t\t\t\tpos[1] += 1\n\t\t\telif d == 'up':\n\t\t\t\tif pos[0] - 1 < 0:\n\t\t\t\t\treturn pos\n\t\t\t\telse:\n\t\t\t\t\tmatrix[pos[0]][pos[1]] = 0\n\t\t\t\t\tpos[0] -= 1\n\t\t\telif d == 'left':\n\t\t\t\tif pos[1] - 1 < 0:\n\t\t\t\t\treturn pos\n\t\t\t\telse:\n\t\t\t\t\tmatrix[pos[0]][pos[1]] = 0\n\t\t\t\t\tpos[1] -= 1\n\t\t\telif pos[0] + 1 >= len(matrix):\n\t\t\t\treturn pos\n\t\t\telse:\n\t\t\t\tmatrix[pos[0]][pos[1]] = 0\n\t\t\t\tpos[0] += 1\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdirection = {'up': 'right', 'right': 'down', 'down': 'left', 'left': 'up'}\n\t\ti = j = 0\n\t\tstart = 'right'\n\t\twhile i >= 0 and j >= 0 and (i < m) and (j < n):\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tstart = direction[start]\n\t\t\t\tmatrix[i][j] = 0\n\t\t\tif start == 'right':\n\t\t\t\tj += 1\n\t\t\telif start == 'left':\n\t\t\t\tj -= 1\n\t\t\telif start == 'up':\n\t\t\t\ti -= 1\n\t\t\telif start == 'down':\n\t\t\t\ti += 1\n\t\tif i >= m:\n\t\t\treturn (i - 1, j)\n\t\telif i < 0:\n\t\t\treturn (i + 1, j)\n\t\telif j < 0:\n\t\t\treturn (i, j + 1)\n\t\treturn (i, j - 1)\n", "class Solution:\n\n\tdef endPoints(self, matrix, m, n):\n\t\tdirection = 'r'\n\t\t(i, j) = (0, 0)\n\t\trow = m\n\t\tcol = n\n\t\twhile True:\n\t\t\tif matrix[i][j] == 1:\n\t\t\t\tmatrix[i][j] = 0\n\t\t\t\tif direction == 'u':\n\t\t\t\t\tdirection = 'r'\n\t\t\t\telif direction == 'r':\n\t\t\t\t\tdirection = 'd'\n\t\t\t\telif direction == 'd':\n\t\t\t\t\tdirection = 'l'\n\t\t\t\telse:\n\t\t\t\t\tdirection = 'u'\n\t\t\tif direction == 'r':\n\t\t\t\tj += 1\n\t\t\t\tif j >= col:\n\t\t\t\t\treturn [i, j - 1]\n\t\t\telif direction == 'l':\n\t\t\t\tj -= 1\n\t\t\t\tif j < 0:\n\t\t\t\t\treturn [i, j + 1]\n\t\t\tif direction == 'u':\n\t\t\t\ti -= 1\n\t\t\t\tif i < 0:\n\t\t\t\t\treturn [i + 1, j]\n\t\t\telif direction == 'd':\n\t\t\t\ti += 1\n\t\t\t\tif i >= row:\n\t\t\t\t\treturn [i - 1, j]\n"]

starter_code:
#User function Template for python3

class Solution:

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

        ##code here

difficulty: EASY

source: geekforgeeks

skill_types: ['Data structures']

raw_problem:
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

question:
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:
![image](1.png)
![image](2.png)
![image](3.png)

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

image_tags: Others Others Others

data_split: test


C. Cupboard and Balloons

problem_index: C

time_limit: 2 seconds

memory_limit: 256 megabytes

solutions: ["(r, h) = list(map(int, input().split()))\na = 2 * (h // r)\nh = h % r\nprint(a + 1 + (2 * h >= r) + (4 * h * h >= 3 * r * r))\n", "import math\n(r, h) = map(int, input().split())\na = h // r * 2\nif 2 * (h % r) >= math.sqrt(3) * r:\n\ta += 3\nelif 2 * (h % r) >= r:\n\ta += 2\nelse:\n\ta += 1\nprint(a)\n", "from math import sqrt\n(r, h) = list(map(int, input().split()))\nnum = h // r\nrem = h % r\nans = num * 2\nif rem * 2 < r:\n\tans += 1\nelif rem * 2 >= sqrt(3) * r:\n\tans += 3\nelse:\n\tans += 2\nprint(ans)\n", "from math import sqrt\n(r, h) = (int(x) for x in input().split(' '))\nin_box = 2 * h // r + 1\nremainder = h % r + r\nheight = r * sqrt(3) / 2 + r\nif remainder < height:\n\tprint(in_box)\nelse:\n\tprint(in_box + 1)\n", "(r, h) = map(int, input().split())\nres = h // r * 2\nif 2 * (h % r) >= 3 ** 0.5 * r:\n\tres += 3\nelif 2 * (h % r) >= r:\n\tres += 2\nelse:\n\tres += 1\nprint(res)\n", "3\n(r, h) = tuple(map(int, input().split()))\nans = (2 * h + r) // (2 * r)\nprint(2 * ans + (3 * r ** 2 <= 4 * (h + r - ans * r) ** 2))\n", "(r, h) = map(int, input().split())\nhalf_count = (2 * h + r) // (2 * r)\nres = 2 * half_count\nx1 = 0\ny1 = h + r / 2\nx2 = r / 2\ny2 = r * (2 * half_count - 1) / 2\nif (x1 - x2) ** 2 + (y1 - y2) ** 2 >= r * r:\n\tres += 1\nprint(res)\n", "import math\n(r, h) = [int(r) for r in input().split(' ')]\nprint(math.floor(h / r * 2 + 1 + math.floor(h % r / r + 0.15)))\n", "from math import *\n(r, h) = map(int, input().split())\nd = h % r\nif d * 2 < r:\n\tprint(h // r * 2 + 1)\nelif sqrt(3) * (r / 2) + r - 1e-06 <= d + r:\n\tprint(h // r * 2 + 3)\nelse:\n\tprint(h // r * 2 + 2)\n", "(r, h) = list(map(int, input().split()))\na = 1 + 2 * h // r\nif h % r >= 3 ** 0.5 * r / 2:\n\ta += 1\nprint(a)\n", "(r, h) = list(map(int, input().split()))\nans = h // r * 2\nh %= r\nif 2 * h < r:\n\tans += 1\nelif 2 * h < 1.732 * r:\n\tans += 2\nelse:\n\tans += 3\nprint(ans)\n", "(r, h) = map(int, input().split())\nh *= 2\nif h < r:\n\tprint(1)\n\treturn\nr *= 2\nans = (h + r // 2) // r * 2\nh -= r * (ans // 2 - 1)\nif h ** 2 * 4 >= r ** 2 * 3:\n\tans += 1\nprint(ans)\n", "from math import sqrt\n(r, h) = map(int, input().split())\ncount = h // r * 2\nh -= h // r * r\nif h >= sqrt(3) / 2 * r:\n\tcount += 3\nelif h >= r / 2:\n\tcount += 2\nelse:\n\tcount += 1\nprint(count)\n", "(r, h) = map(int, input().split())\nans = int(h // (r / 2))\nballoons = ans + ans % 2\nif balloons == 0:\n\tdist = r + 1\nelse:\n\tdist = ((r / 2) ** 2 + (h - (balloons // 2 - 1) * r) ** 2) ** 0.5\nif dist >= r:\n\tballoons += 1\nprint(balloons)\n", "(r, h) = map(int, input().split())\nk = h // r * 2\nd = h % r\nif d >= 2 * r / 3 + 1:\n\tk += 3\nelif d >= r / 2:\n\tk += 2\nelse:\n\tk += 1\nprint(k)\n", "from math import sqrt\n(r, h) = tuple(map(int, input().split()))\nans = (2 * h + r) // (2 * r)\nprint(2 * ans + (ans * r + sqrt(3.0) * r / 2 <= h + r))\n", "(r, h) = map(int, input().split())\n(d, p) = (3 ** 0.5 / 2 - 1, h / r)\nprint(max(1 + 2 * int(p - d), 2 * int(p + 0.5)))\n", "from math import sqrt\n(r, h) = [int(x) for x in input().split()]\nr <<= 1\nh <<= 1\nans = h // r * 2\nh %= r\nif h >= r // 2:\n\tans += 2\n\tif 3 * r * r <= 4 * h * h:\n\t\tans += 1\nelse:\n\tans += 1\nprint(ans)\n", "def __starting_point():\n\tinp = input()\n\tarr = inp.split(' ')\n\tr = int(arr[0])\n\th = int(arr[1])\n\tans = 2 * (h // r)\n\td = h % r\n\tif d * 2 >= r:\n\t\tans += 2\n\t\tif 4 * d * d >= 3 * r * r:\n\t\t\tans += 1\n\telse:\n\t\tans += 1\n\tprint(ans)\n__starting_point()\n", "(r, h) = map(int, input().split())\ns = h % r\na = h // r * 2\nif s * s >= 3 * r * r / 4:\n\ta += 3\nelif 2 * s >= r:\n\ta += 2\nelse:\n\ta += 1\nprint(a)\n", "(r, h) = map(int, input().split())\nh *= 2\nif h < r:\n\tprint(1)\n\texit(0)\nr *= 2\nans = (h + r // 2) // r * 2\nh -= r * (ans // 2 - 1)\nif h ** 2 * 4 >= r ** 2 * 3:\n\tans += 1\nprint(ans)\n"]

difficulty: HARD

source: codeforces

raw_problem:
C. Cupboard and Balloons

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

A girl named Xenia has a cupboard that looks like an arc from ahead. The arc is made of a semicircle with radius r (the cupboard's top) and two walls of height h (the cupboard's sides). The cupboard's depth is r, that is, it looks like a rectangle with base r and height h + r from the sides. The figure below shows what the cupboard looks like (the front view is on the left, the side view is on the right).

Xenia got lots of balloons for her birthday. The girl hates the mess, so she wants to store the balloons in the cupboard. Luckily, each balloon is a sphere with radius . Help Xenia calculate the maximum number of balloons she can put in her cupboard.

You can say that a balloon is in the cupboard if you can't see any part of the balloon on the left or right view. The balloons in the cupboard can touch each other. It is not allowed to squeeze the balloons or deform them in any way. You can assume that the cupboard's walls are negligibly thin.

Input

The single line contains two integers r, h (1 ≤ r, h ≤ 107).

Output

Print a single integer — the maximum number of balloons Xenia can put in the cupboard.

Examples

Input

1 1

Output

3

Input

1 2

Output

5

Input

2 1

Output

2

question:
A girl named Xenia has a cupboard that looks like an arc from ahead. The arc is made of a semicircle with radius r (the cupboard's top) and two walls of height h (the cupboard's sides). The cupboard's depth is r, that is, it looks like a rectangle with base r and height h + r from the sides. The figure below shows what the cupboard looks like (the front view is on the left, the side view is on the right).
 ![image](1.png) Xenia got lots of balloons for her birthday. The girl hates the mess, so she wants to store the balloons in the cupboard. Luckily, each balloon is a sphere with radius ![image](2.png). Help Xenia calculate the maximum number of balloons she can put in her cupboard.
You can say that a balloon is in the cupboard if you can't see any part of the balloon on the left or right view. The balloons in the cupboard can touch each other. It is not allowed to squeeze the balloons or deform them in any way. You can assume that the cupboard's walls are negligibly thin.

Input
The single line contains two integers r, h (1 ≤ r, h ≤ 10^{7}).

Output
Print a single integer — the maximum number of balloons Xenia can put in the cupboard.

Examples
Input
1 1

Output
3

Input
1 2

Output
5

Input
2 1

Output
2

image_tags:
2D Geometry
Math

data_split: test