musabgultekin/TACO huggingface dataset:
protect-the-bad-when-weak-3

Reverse_flash lost his power while moving through a number of timezones and landed in the timezone of Flash. Now we know that Flash would kill him as soon as he finds him.
Your job is to protect the bad.
The timezone of Flash is  (1,1). There is a safe timezone (n,n), the last one ,where Flash couldn't enter.
Timezone which Reverse_flash could pass through/enter is represented by 0 and which he couldn't is represented by 1.Now your task to find the possible number of ways to reach timezone (n,n) from (1,1).
Input format & constraints
1st line --> integer value 'n'  (n ≤ 100) denoting the size of the grid of timezones.
Next n lines -->each line contains n space separated integers either 1 or 0.
Output format
A line with possible number of ways you could protect bad from good i.e, all possible ways you could make him reach (n,n) from (1,1).
Note Reverse_Flash could only move either horizontally or vertically i.e, not diagonally :)

SAMPLE INPUT
7
0 0 0 0 0 0 0
0 1 0 1 0 1 0
0 0 0 0 0 0 0
0 1 0 1 0 1 0
0 0 0 0 0 0 0
0 1 0 1 0 1 0
0 0 0 0 0 0 0

SAMPLE OUTPUT
184

Difficulty: EASY

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10000)
def s(r, c):
	global ans, time_zone, vis, lens, steps
	if r == lens-1 and c == lens - 1:
		ans += 1
		return
	vis[r][c] = True
	for i in range(4):
		nr = r + steps[i][0]
		nc = c + steps[i][1]
		
		if nr < 0 or nc < 0 or nr >= lens or nc >= lens:
			continue
		if vis[nr][nc] or time_zone[nr][nc] == 1:
			continue
		s(nr, nc)
		vis[nr][nc] = False
	  
	  
n = eval(input())
time_zone = []
ans = 0
for i in range(n):
	tmp = []
	tmp = list(map(int, input().split()))
	time_zone.append(tmp)
lens = len(time_zone[0]) 
vis = [[0 for x in range(lens)] for y in range(lens)]
steps = [(1, 0), (-1, 0), (0, 1), (0, -1)]
s(0, 0)
print(ans)
Berland is very concerned with privacy, so almost all plans and blueprints are secret. However, a spy of the neighboring state managed to steal the Bertown subway scheme.

The Bertown Subway has n stations, numbered from 1 to n, and m bidirectional tunnels connecting them. All Bertown Subway consists of lines. To be more precise, there are two types of lines: circular and radial.

A radial line is a sequence of stations v1, ..., vk (k > 1), where stations vi and vi + 1 (i < k) are connected by a tunnel and no station occurs in the line more than once (vi ≠ vj for i ≠ j).

A loop line is a series of stations, v1, ..., vk (k > 2), where stations vi и vi + 1 are connected by a tunnel. In addition, stations v1 and vk are also connected by a tunnel. No station is occurs in the loop line more than once.

Note that a single station can be passed by any number of lines.

According to Berland standards, there can't be more than one tunnel between two stations and each tunnel belongs to exactly one line. Naturally, each line has at least one tunnel. Between any two stations there is the way along the subway tunnels. In addition, in terms of graph theory, a subway is a vertex cactus: if we consider the subway as a graph in which the stations are the vertexes and the edges are tunnels, then each vertex lies on no more than one simple cycle.

Unfortunately, scheme, stolen by the spy, had only the stations and the tunnels. It was impossible to determine to which line every tunnel corresponds. But to sabotage successfully, the spy needs to know what minimum and maximum number of lines may be in the Bertown subway.

Help him!

Input

The first line contains two integers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ 3·105) — the number of stations and the number of tunnels, correspondingly.

Each of the next m lines contain two integers — the numbers of stations connected by the corresponding tunnel. The stations are numbered with integers from 1 to n.

It is guaranteed that the graph that corresponds to the subway has no multiple edges or loops, it is connected and it is a vertex cactus.

Output

Print two numbers — the minimum and maximum number of lines correspondingly.

Examples

Input

3 3
1 2
2 3
3 1


Output

1 3


Input

8 8
1 2
2 3
3 4
4 5
6 4
4 7
7 2
2 8


Output

2 8


Input

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


Output

3 6

Note

The subway scheme with minimum possible number of lines for the second sample is: 

<image>

Difficulty: VERY_HARD
Tags: Graph algorithms

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
AtCoder Grand Contest 014 - Blue and Red Tree

There is a tree with N vertices numbered 1 through N. The i-th of the N-1 edges connects vertices a_i and b_i.

Initially, each edge is painted blue. Takahashi will convert this blue tree into a red tree, by performing the following operation N-1 times:

* Select a simple path that consists of only blue edges, and remove one of those edges.
* Then, span a new red edge between the two endpoints of the selected path.



His objective is to obtain a tree that has a red edge connecting vertices c_i and d_i, for each i.

Determine whether this is achievable.

Constraints

* 2 ≤ N ≤ 10^5
* 1 ≤ a_i,b_i,c_i,d_i ≤ N
* a_i ≠ b_i
* c_i ≠ d_i
* Both input graphs are trees.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 d_1
:
c_{N-1} d_{N-1}


Output

Print `YES` if the objective is achievable; print `NO` otherwise.

Examples

Input

3
1 2
2 3
1 3
3 2


Output

YES


Input

5
1 2
2 3
3 4
4 5
3 4
2 4
1 4
1 5


Output

YES


Input

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


Output

NO

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import queue
(n, q) = (int(input()), queue.Queue())
s = [set() for i in range(n + 1)]
for i in range(2 * n - 2):
	(u, v) = map(int, input().split())
	if v in s[u]:
		q.put((u, v))
	else:
		s[u].add(v)
		s[v].add(u)
f = [i for i in range(n + 1)]

def find(x):
	if f[x] == x:
		return x
	else:
		f[x] = find(f[x])
		return f[x]
while not q.empty():
	(u, v) = map(find, q.get())
	if u == v:
		continue
	if len(s[u]) < len(s[v]):
		(u, v) = (v, u)
	s[u].remove(v)
	s[v].remove(u)
	for x in s[v]:
		s[x].remove(v)
		if u in s[x]:
			q.put((u, x))
		else:
			s[u].add(x)
			s[x].add(u)
	(s[v], f[v]) = ([], u)
root = find(1)
for i in range(2, n + 1):
	if find(i) != root:
		print('NO')
		break
else:
	print('YES')
The goal of this Kata is to return the greatest distance of index positions between matching number values in an array or 0 if there are no matching values.  

Example:
In an array with the values [0, 2, 1, 2, 4, 1] the greatest index distance is between the matching '1' values at index 2 and 5.  Executing greatestDistance against this array would return 3. (i.e. 5 - 2)  

Here's the previous example in test form:
```python
test.assert_equals(greatest_distance([0, 2, 1, 2, 4, 1]), 3)
```

This is based on a Kata I had completed only to realize I has misread the instructions.  I enjoyed solving the problem I thought it was asking me to complete so I thought I'd add a new Kata for others to enjoy.  There are no tricks in this one, good luck!

Difficulty: EASY

Starter code:
def greatest_distance(arr):
	

Solutions:
def greatest_distance(arr):
	return max((i - arr.index(x) for (i, x) in enumerate(arr)))


def greatest_distance(arr):
	(indexes, d) = ({}, 0)
	for (i, n) in enumerate(arr):
		if n in indexes:
			d = max(d, i - indexes[n])
		else:
			indexes[n] = i
	return d


def greatest_distance(lst):
	return max((distance(lst, n) for n in set(lst) if lst.count(n) > 1), default=0)

def distance(lst, item):
	return len(lst) - 1 - lst[::-1].index(item) - lst.index(item)


from collections import defaultdict

def greatest_distance(a):
	d = defaultdict(list)
	for (i, x) in enumerate(a):
		d[x].append(i)
	return max((x[-1] - x[0] for x in d.values()))


def greatest_distance(data):
	i = 0
	d = 0
	while i < len(data):
		j = i + 1
		while j < len(data):
			if data[j] == data[i]:
				if j - i > d:
					d = j - i
			j += 1
		i += 1
	return d


greatest_distance = lambda a: max((i - a.index(e) for (i, e) in enumerate(a)))


greatest_distance = lambda a: max((len(a) - a[::-1].index(e) - a.index(e) - 1 for e in a))


from collections import defaultdict

def greatest_distance(arr):
	indexes = defaultdict(list)
	for (i, a) in enumerate(arr):
		indexes[a].append(i)
	try:
		return max((b[-1] - b[0] for b in indexes.values() if len(b) > 1))
	except ValueError:
		return 0


def greatest_distance(arr):
	res = 0
	for (i, x) in enumerate(arr):
		for (j, y) in enumerate(arr):
			if y == x:
				res = max(res, abs(i - j))
	return res


from collections import Counter

def greatest_distance(arr):
	(r_arr, count_arr) = (arr[::-1], Counter(arr))
	return max((len(arr) - 1 - r_arr.index(k) - arr.index(k) if c > 1 else 0 for (k, c) in count_arr.items()))
Problem Statement

Let b_i(x) be the i-th least significant bit of x, i.e. the i-th least significant digit of x in base 2 (i \geq 1). For example, since 6 = (110)_2, b_1(6) = 0, b_2(6) = 1, b_3(6) = 1, b_4(6) = 0, b_5(6) = 0, and so on.

Let A and B be integers that satisfy 1 \leq A \leq B \leq 10^{18}, and k_i be the number of integers x such that A \leq x \leq B and b_i(x) = 1.

Your task is to write a program that determines A and B for a given \\{k_i\\}.



Input

The input consists of multiple datasets. The number of datasets is no more than 100,000. Each dataset has the following format:


n
k_1
k_2
...
k_n


The first line of each dataset contains an integer n (1 \leq n \leq 64). Then n lines follow, each of which contains k_i (0 \leq k_i \leq 2^{63} - 1). For all i > n, k_i = 0.

The input is terminated by n = 0. Your program must not produce output for it.

Output

For each dataset, print one line.

* If A and B can be uniquely determined, output A and B. Separate the numbers by a single space.
* If there exists more than one possible pair of A and B, output `Many` (without quotes).
* Otherwise, i.e. if there exists no possible pair, output `None` (without quotes).

Example

Input

3
2
2
1
49
95351238128934
95351238128934
95351238128932
95351238128936
95351238128936
95351238128936
95351238128960
95351238128900
95351238128896
95351238129096
95351238128772
95351238129096
95351238129096
95351238126156
95351238131712
95351238131712
95351238149576
95351238093388
95351238084040
95351237962316
95351238295552
95351237911684
95351237911684
95351235149824
95351233717380
95351249496652
95351249496652
95351226761216
95351226761216
95351082722436
95351082722436
95352054803020
95352156464260
95348273971200
95348273971200
95354202286668
95356451431556
95356451431556
95346024826312
95356451431556
95356451431556
94557999988736
94256939803780
94256939803780
102741546035788
87649443431880
87649443431880
140737488355328
32684288648324
64
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
11
0
0
1
1
1
0
1
1
1
1
1
63
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
4
1
1
1
1
0


Output

1 4
123456789101112 314159265358979
None
2012 2012
None
Many

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
Due to the rise of covid-19 cases in India, this year BCCI decided to organize knock-out matches in IPL rather than a league. 
Today is matchday 1 and it is between previous year winners Mumbai Indians and the city of Joy - Kolkata Knight Riders. Eoin Morgan the new captain of the team KKR, thinks that death overs are very important to win a match. He decided to end MI's innings with his most trusted bowler Pat Cummins to minimize the target. There must be at least 4 players inside the 30-yard circle in death overs. Positions of 3 players are already decided which are given as 2-D integer points A, B, and C,  the task is to find the missing point D such that ABCD should be a parallelogram. If there are multiple such points, find the lexicographically smallest coordinate.
 
Example 1:
Input:
A = (3, 2)
B = (3, 4)
c = (2, 2)
Output:
2.000000 0.000000
Explanation: There are two options for 
point D : (2, 4) and (2, 0) such that ABCD 
forms a parallelogram. Since (2, 0) is 
lexicographically smaller than (2, 4). Hence,
(2, 0) is the answer.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findPoint() which takes three lists of integers A[], B[] and C[] and return D[] list of two numbers with a precision of 6 decimal places where first element of D[ ] denote x coordinate and second element of D[ ] denote y coordinate.
Constraints:
1 ≤ x, y ≤ 1000, where x and y denote coordinates of points A, B, and C.
The order of points in the parallelogram doesnt matter.
The given points are not collinear.

Difficulty: MEDIUM
Tags: Geometry

Mathematics

Starter code:
#User function Template for python3





class Solution:

    def findPoint(self, A, B, C):

        # code here

Solutions:
class Solution:

	def findPoint(self, a, b, c):
		dx = b[0] - c[0]
		dy = b[1] - c[1]
		ans = [(a[0] + dx, a[1] + dy), (a[0] - dx, a[1] - dy)]
		dx = a[0] - b[0]
		dy = a[1] - b[1]
		ans += [(c[0] + dx, c[1] + dy), (c[0] - dx, c[1] - dy)]
		return min(ans)


class Solution:

	def orderLex(self, a, b, c):
		winners = [a]
		if b[0] < winners[0][0]:
			winners = [b]
		elif b[0] == winners[0][0]:
			winners.append(b)
		if c[0] == winners[0][0]:
			winners.append(c)
		elif c[0] < winners[0][0]:
			winners[0] = c
		return min(winners, key=lambda t: t[1])

	def newPoint(self, A, B, C):
		return (C[0] - B[0] + A[0], C[1] - B[1] + A[1])

	def findPoint(self, A, B, C):
		(a, b, c) = (self.newPoint(A, B, C), self.newPoint(B, C, A), self.newPoint(C, A, B))
		return self.orderLex(a, b, c)


class Solution:

	def findPoint(self, A, B, C):
		P = [A[0] + C[0] - B[0], A[1] + C[1] - B[1]]
		Q = [B[0] + C[0] - A[0], B[1] + C[1] - A[1]]
		R = [A[0] + B[0] - C[0], A[1] + B[1] - C[1]]
		X = min(P[0], Q[0], R[0])
		if P[0] == X:
			if Q[0] == X:
				if P[1] > Q[1]:
					return Q
			elif R[0] == X:
				if P[1] > R[1]:
					return R
			return P
		elif Q[0] == X:
			if R[0] == X and Q[1] > R[1]:
				return R
			return Q
		return R
While reviewing code recently being checked into the repository, Jim discovered that some employees now and then seemed to copy code right from the Internet into the company code base. This would be a potential disaster as the company then risks getting sued by copyright holders of the original code. The obvious solution, talking to the employees and kindly ask them not to submit any stolen code, seemed to solve the problem. Still, it was decided that a screening process should be introduced to detect newly stolen code. 

The screening would work as follows: Every time new code was checked in, the full contents of the changed files where matched against a repository of known open source code. For each file the longest match, in number of consecutive lines, should be reported.

Comparison is done line by line. Empty lines, and lines only containing space, are ignored during comparison and not counted. Leading and trailing spaces should be ignored completely and consecutive space characters inside the lines are treated as one single space. The comparison is case-sensitive.

-----Input-----
Test data starts with the number $0 \le N \le 100$ of code fragments in the repository. Then follows, for each code fragment, one line containing the file name that the fragment was fetched from and the contents of the fragment on subsequent lines. File names will neither contain whitespace nor be guaranteed to be unique. The name is at most 254 characters long. Each fragment is terminated by ***END*** on a line by its own. This line is not considered being part of the fragment.

After the fragments in the repository have all been listed, comes the actual code snippet to find matches for. This snippet is also terminated by ***END*** on a line by its own.

Lines are guaranteed to be no longer than $254$ characters. No code fragment will be longer than $10000$ lines. Any code and file name lines will only contain the ASCII characters 32-126. The total size of the input file will not exceed $10^6$ characters.

-----Output-----
Output the number of matching consecutive lines (empty lines not counted) in a longest match from the repository, followed by a space-separated list of the file names of each fragments containing a match of this length, given in the order that the matching fragments were presented in the repository description. If no fragments match, write the number 0 on a line of its own.

-----Examples-----
Sample Input:
2
HelloWorld.c
int Main() {
    printf("Hello %d\n",i);
}
***END***
Add.c
int Main() {
  for (int i=0; i<10; i++)
    sum += i;
  printf("SUM %d", sum);
}
***END***
int Main() {
  printf("Hello %d\n",i);
  printf("THE END\n");
}
***END***
Sample Output:
2 HelloWorld.c

Difficulty: HARD

Starter code:

Solutions:
Given an array (ints) of n integers, find three integers in arr such that the sum is closest to a given number (num), target.

Return the sum of the three integers. 
You may assume that each input would have exactly one solution.

Example:

Note: your solution should not modify the input array.

Difficulty: EASY
Tags: Fundamentals

Starter code:
def closest_sum(ints, num):
	

Solutions:
from itertools import combinations

def closest_sum(ints, num):
	return sum(min(combinations(ints, 3), key=lambda a: abs(num - sum(a))))


from itertools import combinations

def closest_sum(ints, num):
	ss = map(sum, combinations(ints, 3))
	return min(ss, key=lambda x: abs(x - num))


from itertools import combinations

def closest_sum(arr, target):
	return min(map(sum, combinations(arr, 3)), key=lambda s: abs(target - s))


def closest_sum(i, ii):
	print(i)
	print(ii)
	iii = len(i)
	iiiiiii = 2.6406429642573826e+32
	for iiii in range(iii):
		for iiiii in range(iii):
			for iiiiii in range(iii):
				if iiii != iiiii and iiiii != iiiiii and (iiiiii != iiii):
					if abs(i[iiii] + i[iiiii] + i[iiiiii] - ii) < abs(iiiiiii - ii):
						iiiiiii = i[iiii] + i[iiiii] + i[iiiiii]
	return iiiiiii


closest_sum = lambda a, n: min(map(sum, __import__('itertools').combinations(a, 3)), key=lambda c: abs(c - n))


from itertools import permutations
closest_sum = lambda s, n: min([sum(i) for i in permutations(s, 3)], key=lambda x: abs(x - n))


def A(arr, a, b, c, L, T):
	if c < L:
		T.append(arr[a] + arr[b] + arr[c])
	if a == L - 2:
		return 0
	elif b == L - 2:
		return A(arr, a + 1, a + 2, a + 3, L, T)
	elif c == L - 1:
		return A(arr, a, b + 1, b + 2, L, T)
	return A(arr, a, b, c + 1, L, T)

def closest_sum(ints, num):
	print((num, ints))
	T = []
	A(ints, 0, 1, 2, len(ints), T)
	print(T)
	if num in T:
		return num
	else:
		(l, h) = (num, num)
		while True:
			l -= 1
			h += 1
			if l in T and h in T:
				return l if T.index(l) < T.index(h) else h
			if l in T:
				return l
			if h in T:
				return h


import itertools

def closest_sum(ints, num):
	res = ints[:3]
	comb = list(itertools.combinations(ints, 3))
	for i in comb:
		if abs(num - sum(i)) < abs(num - sum(res)):
			res = [_ for _ in i]
	return sum(res)
Write a simple function that takes polar coordinates (an angle in degrees and a radius) and returns the equivalent cartesian coordinates (rouded to 10 places).

```
For example:

coordinates(90,1)
=> (0.0, 1.0)

coordinates(45, 1)
=> (0.7071067812, 0.7071067812)
```

Difficulty: EASY
Tags: Geometry

Mathematics

Starter code:
def coordinates(degrees, radius):
	

Solutions:
from math import cos, sin, radians

def coordinates(deg, r, precision=10):
	(x, y) = (r * cos(radians(deg)), r * sin(radians(deg)))
	return (round(x, precision), round(y, precision))


from math import cos, sin, radians

def coordinates(d, r):
	convert = lambda x: round(r * x(radians(d)), 10)
	return (convert(cos), convert(sin))


from math import cos, radians, sin

def coordinates(th, r):
	return tuple((round(r * f(radians(th)), 10) for f in (cos, sin)))


from math import cos, sin, radians

def coordinates(d, r):
	return (round(r * cos(radians(d)), 10), round(r * sin(radians(d)), 10))


import math

def coordinates(degrees, radius):
	theta = math.radians(degrees)
	x = math.cos(theta) * radius
	y = math.sin(theta) * radius
	return (round(x, 10), round(y, 10))


from math import sin, cos, radians

def coordinates(deg, r):
	theta = radians(deg)
	return tuple((round(r * f(theta), 10) for f in (cos, sin)))


def coordinates(d, r):
	c = r * 1j ** (d / 90)
	return (round(c.real, 10), round(c.imag, 10))


from math import radians, sin, cos

def coordinates(degrees, radius):
	angle = radians(degrees)
	return tuple((round(f(angle) * radius, 10) for f in (cos, sin)))


import math

def coordinates(degrees, radius):
	if degrees != 0:
		degrees = math.pi / (180 / degrees)
	else:
		degrees = 0
	return (round(radius * math.cos(degrees), 10), round(radius * math.sin(degrees), 10))


from math import radians, sin, cos

def coordinates(degrees, radius):
	return (round(radius * cos(radians(degrees)), 10), round(radius * sin(radians(degrees)), 10))
Tim buy a string of  length N from his friend which consist of  ‘d’ and ‘u’ letters only
,but now Tim wants to sell the string at maximum cost.  
The maximum cost of string is defined as the maximum length of a Substring (consecutive subsequence) consisting of equal letters.
Tim can change at most P characters of string (‘d’ to ‘u’   and   ‘u’ to ‘d’) you have to find out the maximum cost of string?

-----Input:-----
- First line will contain $N$ and $P$ .
- Second line will contain the String $S$.

-----Output:-----
Maximum cost of string S.

-----Constraints-----
- $1 \leq N\leq 10^5$
- $0 \leq P \leq N$

-----Sample Input 1:-----
4  2
$duud$

-----Sample Output 1:-----
4

-----Sample Input 2 :-----
10 1
$dduddudddu$

-----Sample Output 2:-----
6

-----EXPLANATION:-----
In the first sample input , We can obtain both strings $dddd$ and $uuuu$ .
In the second sample, the optimal answer is obtained with the string $dddddudd$ or with the string $dduddddd$

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(n, p) = map(int, input().split())
s = input()
d = s.count('d')
u = s.count('u')
if d <= p or u <= p:
	print(n)
elif d >= u:
	c = 0
	l = 0
	i = 0
	ii = -1
	pp = p
	while i < n:
		if s[i] == 'u' and ii == -1:
			ii = i
		if pp == 0 and s[i] == 'u':
			c = max(c, l)
			i = ii
			ii = -1
			l = -1
			pp = p
		elif s[i] == 'u':
			pp -= 1
		i += 1
		l += 1
	print(max(c, l))
else:
	c = 0
	l = 0
	i = 0
	ii = -1
	pp = p
	while i < n:
		if s[i] == 'd' and ii == -1:
			ii = i
		if pp == 0 and s[i] == 'd':
			c = max(c, l)
			i = ii
			ii = -1
			l = -1
			pp = p
		elif s[i] == 'd':
			pp -= 1
		i += 1
		l += 1
	print(max(c, l))


(N, P) = map(int, input().split())
S = [i == 'd' for i in input().strip()]

def calcMax(ar):
	j = c = ans = 0
	for i in range(len(ar)):
		while j < len(ar) and c + ar[j] <= P:
			c += ar[j]
			j += 1
		ans = max(ans, j - i)
		c -= ar[i]
	return ans
print(max(calcMax(S), calcMax([not _ for _ in S])))


def findLen(A, n, k, ch):
	maxlen = 1
	cnt = 0
	l = 0
	r = 0
	while r < n:
		if A[r] != ch:
			cnt += 1
		while cnt > k:
			if A[l] != ch:
				cnt -= 1
			l += 1
		maxlen = max(maxlen, r - l + 1)
		r += 1
	return maxlen

def answer(A, n, k):
	maxlen = 1
	for i in range(26):
		maxlen = max(maxlen, findLen(A, n, k, chr(i + ord('A'))))
		maxlen = max(maxlen, findLen(A, n, k, chr(i + ord('a'))))
	return maxlen
(n, k) = map(int, input().split())
s = str(input())
print(answer(s, n, k))
The chef has a recipe he wishes to use for his guests,
but the recipe will make far more food than he can serve to the guests.
The chef therefore would like to make a reduced version of the recipe which has the same ratios of ingredients, but makes less food.
The chef, however, does not like fractions.
The original recipe contains only whole numbers of ingredients,
and the chef wants the reduced recipe to only contain whole numbers of ingredients as well.
Help the chef determine how much of each ingredient to use in order to make as little food as possible.

-----Input-----
Input will begin with an integer T, the number of test cases.
Each test case consists of a single line.
The line begins with a positive integer N, the number of ingredients.
N integers follow, each indicating the quantity of a particular ingredient that is used.

-----Output-----
For each test case, output exactly N space-separated integers on a line,
giving the quantity of each ingredient that the chef should use in order to make as little food as possible.

-----Sample Input-----
3
2 4 4
3 2 3 4
4 3 15 9 6

-----Sample Output-----
1 1
2 3 4
1 5 3 2

-----Constraints-----
T≤100

2≤N≤50

All ingredient quantities are between 1 and 1000, inclusive.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from sys import stdin
from functools import reduce

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a

def gcdl(l):
	return reduce(gcd, l[1:], l[0])

def __starting_point():
	T = int(stdin.readline())
	for case in range(T):
		numbers = list(map(int, stdin.readline().split()[1:]))
		g = gcdl(numbers)
		numbers = [n / g for n in numbers]
		print(' '.join([str(x) for x in numbers]))
__starting_point()
Maj loves pickled cucumber (also known as pickles). However, her partner is not as keen on filling a sandwich with pickles. Maj would like to maximize the amount of pickles on a sandwich, while still avoiding being judged by her partner. 

Both Maj’s sandwich and the pickles have a circular shape. The sandwich has radius $s$ cm and the pickles have radius $r$ cm.

Maj has exactly $n$ pickles. She wants to place as many of them as possible on her sandwich, as long as:
 - at most $z \% $ of the area of the sandwich is covered by pickles.
 - no two pickles overlap (but they are allowed to touch).

How many pickles can Maj place on her sandwich?

-----Input-----
The input consists of:
 - one line with the decimal numbers $s$ and $r$ ($1 \le s \le 10$, $0.5 \le r \le s$, at most $6$ digits after the decimal point), the radius of the sandwich and the radius of a pickle, in centimetres.
 - one line with the integers $n$ and $z$ ($1 \le n \le 7$, $0 \le z \le 100$), the number of pickles Maj have, and the maximum area she may cover with them, in percent.

-----Output-----
Output the maximum number of pickles Maj can place on her sandwich. The input will always be constructed such that this number does not change if the radius of the sandwich increases or decreases by $10^{-6}$.

-----Examples-----
Sample Input:
3 1 4 40
Sample Output:
3

Difficulty: HARD

Starter code:

Solutions:
refreshed-mind-1

The average miner Sehdev took refresher courses. As soon as a miner completes the courses, he should take exams. The hardest one is a computer test called "Refreshed Mind".

The test consists of n questions; the questions are to be answered strictly in the order in which they are given, from question 1 to question n. Question i contains ai answer variants, exactly one of them is correct.

A click is regarded as selecting any answer in any question. The goal is to select the correct answer for each of the n questions. If Sehdev selects a wrong answer for some question, then all selected answers become unselected and the test starts from the very beginning, from question 1 again. But Sehdev remembers everything. The order of answers for each question and the order of questions remain unchanged, as well as the question and answers themselves.

Sehdev is very smart and his memory is superb, yet he is unbelievably unlucky and knows nothing whatsoever about the test's theme. How many clicks will he have to perform in the worst case?

Input
The first line contains a positive integer n (1 ≤ n ≤ 100). It is the number of questions in the test. The second line contains space-separated n positive integers ai (1 ≤ ai ≤ 109), the number of answer variants to question i.

Output
Print a single number — the minimal number of clicks needed to pass the test it the worst-case scenario. 

SAMPLE INPUT
2
1 1

SAMPLE OUTPUT
2

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
t=int(eval(input()))
x=list(map(int,input().split()))
j=0
n=sum(x)
for i in x:
	n+=j*(i-1)
	j+=1
print(n)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
n = int(input())
a = []
while len(a) != n:
	a += list(map(int,input().split()))
	
a = a[::-1]
i = 0
ctr2 = 0
while i < len(a):
	if i == 0:
		ctr = a[i]
	else:
		ctr = ctr + a[i] - 1
	ctr2+=ctr
	#print "ctr", ctr, "a[i]", a[i]
	i+=1
	
#print a
print(ctr2)
Filip came across an interesting math problem: He was supposed to find a five-digit number with the following property. If you cross out its first two digits, then place the digit $8$ after the remaining three digits to form a four-digit number and multiply the resulting four-digit number by $4$, you will get the original five-digit number.

After thinking for a while, he found his answer. But now he is wondering, what if he had to find an $m$-digit number, where you have to cross out the first $n$ digits, place a (possibly multi-digit) number $p$ after the remaining $(m-n)$-digit number, then multiply this new number by a number $q$ to get the original number? Please help him!

(Note: Every $m$, $p$ and $q$ needs to start with a non-zero digit.)

-----Input-----
The input consists of a single line containing four numbers: $m$, $n$, $p$, and $q$. You may assume that each number is positive and not larger than $1000000$. You may also assume that $m\geq n$.

-----Output-----
The output consists of a single line. If such an $m$-digit number exists, the line contains the smallest such number. If no such number exists, the line contains the string IMPOSSIBLE.

-----Examples-----
Sample Input:
5 2 8 4
Sample Output:
20512

Difficulty: HARD

Starter code:

Solutions:
Yuezheng Ling gives Luo Tianyi a tree which has n nodes, rooted at 1. 

Luo Tianyi will tell you that the parent of the i-th node is a_i (1 ≤ a_i<i for 2 ≤ i ≤ n), and she will ask you to perform q queries of 2 types:

  1. She'll give you three integers l, r and x (2 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^5). You need to replace a_i with max(a_i-x,1) for all i with l ≤ i ≤ r.
  2. She'll give you two integers u, v (1 ≤ u, v ≤ n). You need to find the [LCA](https://en.wikipedia.org/wiki/Lowest_common_ancestor) of nodes u and v (their lowest common ancestor).

Input

The first line contains two integers n and q (2≤ n,q ≤ 10^5) — the number of nodes and the number of queries, respectively.

The second line contains n-1 integers a_2, a_3,..., a_n (1 ≤ a_i < i), where a_i is the parent of the node i.

Next q lines contain queries. For each query, the first integer of each line is t (t = 1 or 2) — the type of the query. 

If t = 1, this represents the query of the first type. Then, three integers will follow: l, r, x (2 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^5), meaning that you have to replace a_i with max(a_i-x,1) for all i with l ≤ i ≤ r.

If t = 2, this represents the query of the second type. Then, two integers will follow: u and v (1 ≤ u, v ≤ n), and you have to find the LCA of u and v. 

It's guaranteed that there is at least one query of the second type.

Output

For each query of the second type output answer on a new line.

Example

Input


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


Output


3
3
1

Note

The tree in example is shown below.

<image>

After the query of the first type, the tree changes and is looking as shown below.

<image>

Difficulty: VERY_HARD
Tags: Tree algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
Given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1's, return 0.
Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.
 
Example 1:
Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2:
Input: n = 5
Output: 2
Explanation: 5 in binary is "101".

Example 3:
Input: n = 6
Output: 1
Explanation: 6 in binary is "110".

Example 4:
Input: n = 8
Output: 0
Explanation: 8 in binary is "1000".
There aren't any adjacent pairs of 1's in the binary representation of 8, so we return 0.

Example 5:
Input: n = 1
Output: 0

 
Constraints:

1 <= n <= 109

Difficulty: EASY
Tags: Bit manipulation
Skill types: Bit manipulation

Starter code:
class Solution:
    def binaryGap(self, n: int) -> int:
        

Solutions:
class Solution:

	def binaryGap(self, n: int) -> int:
		maxDist = 0
		currDist = 0
		while n:
			if n & 1 and currDist != 0:
				maxDist = max(maxDist, currDist)
				currDist = 1
			elif n & 1:
				currDist = 1
			elif not n & 1 and currDist != 0:
				currDist += 1
			n >>= 1
		return maxDist


class Solution:

	def binaryGap(self, n: int) -> int:
		bins = ''
		maxv = 0
		i = 0
		pre = None
		while n > 0:
			if n % 2 == 1:
				if pre is not None:
					maxv = max(maxv, i - pre)
				pre = i
			n //= 2
			i += 1
		return maxv


class Solution:

	def binaryGap(self, n: int) -> int:
		binary_string = bin(n)[2:]
		(left, right, current_distance, global_max) = (0, 1, 1, 0)
		print(binary_string)
		while right <= len(binary_string) - 1:
			print(left, right, current_distance, global_max)
			if binary_string[right] == '0':
				right += 1
				current_distance += 1
			else:
				global_max = max(global_max, current_distance)
				left = right
				right += 1
				current_distance = 1
		return global_max


class Solution:

	def binaryGap(self, N: int) -> int:
		bit_list = bin(N)[2:]
		stack = []
		dis = 0
		for b in bit_list:
			if not stack and b == '1':
				stack.append(b)
			elif stack and b == '0':
				stack.append(b)
			elif stack and b == '1':
				dis = max(dis, len(stack))
				stack = ['1']
		return dis


class Solution:

	def binaryGap(self, n: int) -> int:
		if n == 0:
			return 0
		while n & 1 == 0:
			n = n >> 1
		global_max = local_max = 0
		while n > 0:
			if n & 1 == 1:
				global_max = max(global_max, local_max)
				local_max = 1
			else:
				local_max += 1
			n = n >> 1
		return global_max
Given an array Arr of N integers.Calculate the sum of Bitwise ANDs(&) all the pairs formed by the given array.
Example 1:
Input:
N=3
Arr={5,10,15}
Output:
15
Explanation:
The bitwise Ands of all pairs are (5&10)=0
(5&15)=5 and (10&15)=10.Therefore,
total Sum=0+5+10=15.
Example 2:
Input:
N=4
Arr={10,20,30,40}
Output:
46
Explanation:
The sum of bitwise Ands 
of all pairs=0+10+8+20+0+8=46.
Your Task:
You don't need to read input or print anything.Your Task is to complete the function pairAndSum() which takes an Integer N and an array Arr as input parameters and returns the sum of bitwise Ands of all pairs.
Expected Time Complexity:O(N)
Expected Auxillary Space:O(1)
Constraints:
1<=N<=10^{5}
1<=Arr_{i}<=10^{8}

Difficulty: EASY
Tags: Bit manipulation

Data structures

Mathematics
Skill types: Bit manipulation

Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def pairAndSum(self,N,Arr):
        #code here

Solutions:
class Solution:

	def pairAndSum(self, N, Arr):
		c = [0] * 32
		for i in range(N):
			for j in range(32):
				if Arr[i] & 1 << j:
					c[j] += 1
		ans = 0
		for i in range(32):
			ans += c[i] * (c[i] - 1) // 2 * (1 << i)
		return ans


from collections import defaultdict as dd

class Solution:

	def pairAndSum(self, N, Arr):
		store = dd(lambda : 0)
		for item in Arr:
			num = bin(item)[2:]
			num = num[::-1]
			for (i, bitti) in enumerate(num):
				if bitti == '1':
					store[i] += 1
		summa = 0
		for item in store:
			summa += 2 ** item * store[item] * (store[item] - 1) // 2
		return summa


class Solution:

	def pairAndSum(self, N, Arr):
		matrix = []
		ans = 0
		for i in range(N):
			matrix.append([0] * 32)
		for i in range(32):
			count = 0
			mask = 1 << i
			for j in range(N):
				if Arr[j] & mask != 0:
					count += 1
			pairs = count * (count - 1) // 2
			ans = ans + pairs * (1 << i)
		return ans


class Solution:

	def pairAndSum(self, n, arr):
		ans = 0
		for i in range(0, 32):
			k = 0
			for j in range(0, n):
				if arr[j] & 1 << i:
					k = k + 1
			ans = ans + (1 << i) * (k * (k - 1) // 2)
		return ans


class Solution:

	def pairAndSum(self, N, Arr):
		res = 0
		for i in range(32):
			temp = 0
			for j in range(N):
				if Arr[j] & 1 << i:
					temp += 1
			res += (1 << i) * (temp * (temp - 1) // 2)
		return res


class Solution:

	def pairAndSum(self, N, Arr):
		l = [0] * 32
		c = 0
		for i in Arr:
			s = bin(i)
			s = s[2:]
			s = (32 - len(s)) * '0' + s
			for j in range(31, -1, -1):
				if s[j] == '1':
					l[31 - j] += 1
		for i in range(32):
			c += l[i] * (l[i] - 1) // 2 * 2 ** i
		return c


import math

class Solution:

	def cust_fact(self, n):
		return int(n * (n - 1) / 2)

	def pairAndSum(self, N, Arr):
		total = 0
		for i in range(32):
			count = 0
			for x in range(N):
				if Arr[x] >> i & 1:
					count += 1
			if count < 2:
				continue
			combinations = self.cust_fact(count)
			total += combinations << i
		return total
A bicycle race is being organized in a land far, far away. There are $N$ towns in the land, numbered $1$ through $N$. There are also $M$ one-way roads between the towns. The race will start in town $1$ and end in town $2$.

How many different ways can the route be set? Two routes are considered different if they do not use the exact same roads.

-----Input-----
The first line of input contains two integers $N$ and $M$ ($1 \le N \le 10000$, $1 \le M \le 100000$), the number of towns and roads.

Each of the next $M$ lines contains two different integers $A$ and $B$, representing a road from town $A$ to town $B$.

Towns may be connected by more than one road.

-----Output-----
Output the number of distinct routes that can be set on a single line. If that number has more than nine digits, output only the last nine digits of the number. If there are infinitely many routes, output “inf”.

-----Examples-----
Sample Input 1:
6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4
Sample Output 1:
3

Sample Input 2:
6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3
Sample Output 2:
inf

Difficulty: HARD

Starter code:

Solutions:
Digits $4$ and $7$ are lucky, while all others are unlucky. An integer is lucky if it contains only lucky digits in decimal notation. We would like to know the $K$-th lucky positive integer.

-----Input-----
The first and only line of input contains a positive integer $K$ ($1 \le K \le 10^9$).

-----Output-----
The first and only line of output must contain the $K$-th lucky positive integer.

-----Examples-----
Sample Input 1:
1
Sample Output 1:
4

Sample Input 2:
2
Sample Output 2:
7

Difficulty: MEDIUM

Starter code:

Solutions:
Akku have solved many problems, she is genius. One day her friend gave her an Array of size n and asked her to perform
some queries of following type:
Each query consists of three integers
1 A B : Update the Array at index A by value B
2 A B : if the subarray from index A to B (both inclusive) is
        1. Both increasing(Non-decreasing) and decreasing(Non-increasing) print -1
        2. Only increasing(Non-decreasing) print 0
        3. Only decreasing(Non-increasing) print 1
        4. Neither increasing nor decreasing print -1
Akku needs your help, can you help her.
 
Example 1:
Input: nums = {1,5,7,4,3,5,9},
Queries = {{2,1,3},{1,7,4},{2,6,7}}
Output: {0,1}
Explanation: For the 1st query given :
A = 1, B = 3. From 1 to 3(1,5,7) elements 
are in increasing order. So answer is 0.
For the 2nd query we have to update the 7th
element of the array by 4. So new updated array
will be {1,5,7,4,3,5,4}
For the 3rd query A = 6, B = 7. From 6 to 7
(5, 4) elements are in descending order. So 
answer is 1.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function solveQueries() which takes nums and Queries as input parameter and returns a list containing the answer for the 2nd type of query.
 
Expected Time Comeplxity: O(n*log(n))
Expected Space Comeplxity: O(n)
 
Constraints:
1 <= n <= 10^{4}
1 <= nums[i] <= 10^{4}
1 <= No. of queries <= 10^{4}

Difficulty: MEDIUM_HARD
Tags: Data structures

Range queries

Segment trees revisited
Skill types: Data structures

Range queries
Expected Time Complexity: O(n*log(n))
Expected Auxiliary Space: O(n)

Starter code:
#User function Template for python3

class Solution:
	def solveQueries(self, nums, Queries):
		#Code here

Solutions:
class Solution:

	def algo(self, a):
		l = list(a)
		l.sort()
		l1 = l[::-1]
		if len(a) == 1:
			return -1
		if a == l:
			return 0
		if a == l1:
			return 1
		return -1

	def solveQueries(self, nums, q):
		ans = []
		for i in range(len(q)):
			l = q[i]
			if l[0] == 1:
				nums[l[1] - 1] = l[2]
			elif l[0] == 2:
				a = nums[l[1] - 1:l[2]]
				ans.append(self.algo(a))
		return ans


class Solution:

	def solveQueries(self, nums, Queries):
		ans = []
		for (q, A, B) in Queries:
			if q == 1:
				nums[A - 1] = B
			if q == 2:
				s = set()
				for (x0, x1) in zip(nums[A - 1:B - 1], nums[A:B]):
					r = '<' if x0 < x1 else '>' if x0 > x1 else '='
					s.add(r)
				r = -1 if not s else 0 if '>' not in s else 1 if '<' not in s else -1
				ans.append(r)
		return ans
On the forest-filled moon of Endor there is, if we are to believe the Guinness Book of Records, the longest stick in the whole galaxy. On that stick of $L$ meters in length there are $N$ cheerful chameleons. Each chameleon is moving along the stick with constant speed of $1\mathrm{m}/\mathrm{s}$ in one of two possible directions (left or right) and is colored in one of the possible $K$ colors.

It is known that the chameleons of Endor worship the ancient ant laws that dictate that the walk along the stick must be continued until the end of the stick is reached (which means getting off it), and when a collision with another chameleon takes place, you must turn $180$ degrees and continue the walk in the opposite direction. Additionally, after a chameleon colored in colour $a$ moving to the left collides with a chameleon colored in colour $b$ moving to the right, the chameleon moving to the left before the collision takes the color of the chameleon moving to the right before the collision (so, color $b$), while the chameleon moving to the right before the collision takes a new color $(a + b) \bmod K$.

If you are given the initial positions, colors and directions of movement of all the chameleons, for each color determine the total trip taken by the chameleons in that color before getting off the stick.

-----Input-----
The first line of input contains the integers $N$, $K$ and $L$ ($1 \leq N \leq 100000$, $1 \leq K \leq 40$, $1 \leq L \leq 1000000$) from the task. The $i$-th of the following $N$ lines contains the integer $d_ i$ ($0 \leq d_ i \leq L$) that denotes the distance between the $i$-th chameleon and the left end of the stick, then the integer $b_ i$ ($0 \leq b_ i \leq K - 1$) that denotes the color of the $i$-th chameleon and the character ‘L’ (left) or ‘D’ (right) that denote the direction of movement of the $i$-th chameleon. All integers $d_ i$ will be unique and given in strictly ascending order.

-----Output-----
The output must contain $K$ lines, the $i$-th line containing the total trip taken by the chameleons in color $i$.

-----Examples-----
Sample Input 1:
2 3 10
0 0 D
10 1 L
Sample Output 1:
10.0
10.0
0.0

Sample Input 2:
4 3 7
1 0 D
3 0 D
4 1 L
6 2 D
Sample Output 2:
10.0
4.0
1.0

Difficulty: HARD

Starter code:

Solutions:
shivam-shantam-and-their-absolute-difference-3

"Sometimes the thing that brings us together also pulls us apart."  - Jarod Kintz.
Shivam and Shantam are really good friends. What mostly brings them together is the hours of group study they have done in the two years of their engineering, and there is only more to add to this. They both start studying together for exams , and keep explaining topics and clearing each other's slightest of doubts.

But , unfortunately , marks and money can always make or break relations. Both of them have to answer N questions in tomorrow's paper. We also have two arrays , A and B. Ai denotes the marks Shivam will get if he answers the i^th question. Bi denotes the marks Shantam will get if he answers the i^th question. The person not choosing to answer the question would get no marks.

Obviously , there are many ways in which they can give their papers. Let the final score of Shivam be S and that of Shantam be K. We are interested in knowing the number of ways such that the absolute difference in S and K is less than or equal to Q.

Input Format :

The first line contains N , the number of questions. The next line contains N space separated integers denoting Ai , the marks that Shivam can score if he attempts the i^th question. The next line contains N space separated integers denoting Bi , the marks that Shantam can score if he attempts the i^th question. The next line contains Q , the maximum allowed absolute difference.

Output Format :

Since the number of ways can be huge , output the answer modulo 10^9 + 7 in a separate line.

Contraints :
1 ≤ N ≤ 200
0 ≤ Ai, Bi ≤ 2 * 10^3
0 ≤ Q ≤ 10^6

SAMPLE INPUT
2
1 2
4 5
2

SAMPLE OUTPUT
6

Explanation

There are 6 ways to get an absolute difference less than equal to 2 :
Shivam :  {1 , 0}   Shantam:  {0 , 0} i. e. Shivam answers only the first question, but Shantam answers none.    
Shivam :  {0 , 2}   Shantam:  {0 , 0} i. e. Shivam answers only the second question, but Shantam answers none.    
Shivam :  {0 , 2}   Shantam:  {4 , 0}  
Shivam :  {1 , 2}   Shantam:  {4 , 0}
Shivam :  {1, 2}   Shantam:  {0 , 5}
Shivam :  {0 , 0}   Shantam:  {0 , 0}

Difficulty: MEDIUM

Starter code:

Solutions:
Vus the Cossack has a simple graph with n vertices and m edges. Let d_i be a degree of the i-th vertex. Recall that a degree of the i-th vertex is the number of conected edges to the i-th vertex.

He needs to remain not more than ⌈ (n+m)/(2) ⌉ edges. Let f_i be the degree of the i-th vertex after removing. He needs to delete them in such way so that ⌈ (d_i)/(2) ⌉ ≤ f_i for each i. In other words, the degree of each vertex should not be reduced more than twice. 

Help Vus to remain the needed edges!

Input

The first line contains two integers n and m (1 ≤ n ≤ 10^6, 0 ≤ m ≤ 10^6) — the number of vertices and edges respectively.

Each of the next m lines contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n) — vertices between which there is an edge.

It is guaranteed that the graph does not have loops and multiple edges.

It is possible to show that the answer always exists.

Output

In the first line, print one integer k (0 ≤ k ≤ ⌈ (n+m)/(2) ⌉) — the number of edges which you need to remain.

In each of the next k lines, print two integers u_i and v_i (1 ≤ u_i, v_i ≤ n) — the vertices, the edge between which, you need to remain. You can not print the same edge more than once.

Examples

Input


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


Output


5
2 1
3 2
5 3
5 4
6 5


Input


10 20
4 3
6 5
4 5
10 8
4 8
5 8
10 4
9 5
5 1
3 8
1 2
4 7
1 4
10 7
1 7
6 1
9 6
3 9
7 9
6 2


Output


12
2 1
4 1
5 4
6 5
7 1
7 4
8 3
8 5
9 3
9 6
10 4
10 7

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
pettigrews-escape

It was revealed in Harry Potter and the Prisoner of Azkaban thatr Peter Pettigrew had faked his death at the hands of Sirius Black and escaped through a maze of sewer tunnels.

Now, you are interested in finding out which path he took to escape. First, you are trying to figure out the total number of escape routes possible for his escape. You know that he doesn't reach the same cell twice. He can move only horizontally or vertically.

Your friends in the architecture department have made a matrix to represent the maze. A '0' position represents an open cell, while a '1' represents a blocked cell. You know that he started his journey from (1,1) [1 - indexed and not 0-indexed] and had to reach (N,N).

INPUT FORMAT

First line is a single odd positive integer, T ( ≤ 85), which indicates the size of the matrix. T lines 
follow, each containing T space separated numbers which are either '0' or '1'.

OUTPUT FORMAT

Output the number of ways in which Peter Pettigrew could have escaped from (1,1) to (N,N).

SAMPLE INPUT
7
0 0 1 0 0 1 0
1 0 1 1 0 0 0
0 0 0 0 1 0 1
1 0 1 0 0 0 0
1 0 1 1 0 1 0
1 0 0 0 0 1 0
1 1 1 1 0 0 0

SAMPLE OUTPUT
4

Difficulty: UNKNOWN_DIFFICULTY
Tags: Graph traversal

Starter code:

Solutions: