vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
#### Task:

Your job here is to write a function (`keepOrder` in JS/CoffeeScript, `keep_order` in Ruby/Crystal/Python, `keeporder` in Julia), which takes a sorted array `ary` and a value `val`, and returns the lowest index where you could insert `val` to maintain the sorted-ness of the array. The input array will always be sorted in ascending order. It may contain duplicates.

_Do not modify the input._

#### Some examples:

```python
keep_order([1, 2, 3, 4, 7], 5) #=> 4
                      ^(index 4)
keep_order([1, 2, 3, 4, 7], 0) #=> 0
          ^(index 0)
keep_order([1, 1, 2, 2, 2], 2) #=> 2
                ^(index 2)
```

Also check out my other creations — [Naming Files](https://www.codewars.com/kata/naming-files), [Elections: Weighted Average](https://www.codewars.com/kata/elections-weighted-average), [Identify Case](https://www.codewars.com/kata/identify-case), [Split Without Loss](https://www.codewars.com/kata/split-without-loss), [Adding Fractions](https://www.codewars.com/kata/adding-fractions),
[Random Integers](https://www.codewars.com/kata/random-integers), [Implement String#transpose](https://www.codewars.com/kata/implement-string-number-transpose), [Implement Array#transpose!](https://www.codewars.com/kata/implement-array-number-transpose), [Arrays and Procs #1](https://www.codewars.com/kata/arrays-and-procs-number-1), and [Arrays and Procs #2](https://www.codewars.com/kata/arrays-and-procs-number-2).

If you notice any issues or have any suggestions/comments whatsoever, please don't hesitate to mark an issue or just comment. Thanks!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A land far, far away has N Members of Parliament (MP). They had a turbulent and passionate debate on the law on amendments to the law on a new referendum on referendums. From Monday to Friday, all MPs joyfully came to work and argued all day.

A diligent news reporter photographed MPs at their workplace in the heat of the argument every working day of the week. What she captured on the photos are pairs of MPs fighting and scowling at each other. The five photographs have been forwarded to you for thorough analysis.

It is a fact that each MP belongs to one of the two political parties. Let’s denote them with letters A and B. Your task is to estimate which MP belongs to which party, so that the following holds for your estimation: each MP argued with at most two distinct members of their own party.

-----Input-----
The first line of input contains an integer $N$ ($2 \leq N \leq 200000$), the number of MPs. MPs are denoted with numbers from $1$ to $N$.

The following five lines describe the photographs taken from Monday to Friday. Each of the five lines contains the list of pairs of MPs that are arguing on the photograph that day (scowling at each other). Stated first is the number of pairs $P$ ($1 \leq P \leq N/2$), followed by $P$ pairs in the form “$K$ $L$”, where $K$ and $L$ are labels of MPs scowling at each other. Before each pair there is a double space.

Of course, each MP is stated at most once per line, and no MP ever argues with herself.

-----Output-----
The first and only line of output must contain an array consisting of only characters A and B, so that the $K$-th character denotes the party of $K$-th MP in a division that satisfies the given conditions.

Since the solution isn’t going to be unique, output any.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke has decided to play a game, where the player runs a railway company.
There are M+1 stations on Snuke Line, numbered 0 through M.
A train on Snuke Line stops at station 0 and every d-th station thereafter, where d is a predetermined constant for each train.
For example, if d = 3, the train stops at station 0, 3, 6, 9, and so forth.
There are N kinds of souvenirs sold in areas around Snuke Line. The i-th kind of souvenirs can be purchased when the train stops at one of the following stations: stations l_i, l_i+1, l_i+2, ..., r_i.
There are M values of d, the interval between two stops, for trains on Snuke Line: 1, 2, 3, ..., M.
For each of these M values, find the number of the kinds of souvenirs that can be purchased if one takes a train with that value of d at station 0.
Here, assume that it is not allowed to change trains.

-----Constraints-----
 - 1 ≦ N ≦ 3 × 10^{5}
 - 1 ≦ M ≦ 10^{5}
 - 1 ≦ l_i ≦ r_i ≦ M

-----Input-----
The input is given from Standard Input in the following format:
N M
l_1 r_1
:
l_{N} r_{N}

-----Output-----
Print the answer in M lines. The i-th line should contain the maximum number of the kinds of souvenirs that can be purchased if one takes a train stopping every i-th station.

-----Sample Input-----
3 3
1 2
2 3
3 3

-----Sample Output-----
3
2
2

 - If one takes a train stopping every station, three kinds of souvenirs can be purchased: kind 1, 2 and 3.
 - If one takes a train stopping every second station, two kinds of souvenirs can be purchased: kind 1 and 2.
 - If one takes a train stopping every third station, two kinds of souvenirs can be purchased: kind 2 and 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Kanto region has $N$ junctions and $N - 1$ bidirectional roads. Junctions are numbered from $1$ to $N$, inclusive. All roads have the same length and each of them connects two different junctions.

At any moment, a Pokenom can appear in any of these junctions.

To become the best Pokenom trainer, like no one ever was, Bash is studying the behavior of the Pokenom in Kanto region. Bash has found that, when trying to capture a Pokenom at junction $u$, the Pokenom can run away to junction $v$, iff the optimal path between $u$ and $v$ has length exactly $2$.

More formally, a path of length $K$ from junction $s$ to junction $t$ is an ordered sequence of junctions $v_{0} \rightarrow v_{1} \rightarrow v_{2} \rightarrow \cdots \rightarrow v_{K}$, where $v_{0} = s, v_{K} = t$ and for each valid index $i$, $v_{i}$ and $v_{i+1}$ are connected directly by some road. A path is called optimal iff there is no shorter path with the same starting and ending junctions. Two paths $v_{0} \rightarrow v_{1} \rightarrow \cdots \rightarrow v_{k}$ and $w_{0} \rightarrow w_{1} \rightarrow \cdots w_{l}$ are different iff either $k \neq l$ or there exist some valid $i$ such that $v_{i} \neq w_{i}$.

A Pokenom can use an optimal path of length exactly $2$. Help Bash count the number of such paths.

-----Input-----
 - The first line contains one integer $N$ $(1 \leq N \leq 3 \cdot 10^{5})$ — the number of junctions.
 - Each of the rest $N - 1$ lines contains two integers $u$ and $v$ $(1 \leq u, v \leq N, u \neq v)$ — two endpoints of a single road.

-----Output-----
 - The only line contains exactly one integer — the number of optimal paths of length $2$.

-----Explanation for the first example-----
 - There are two optimal paths of length $2$: $(2 \rightarrow 1 \rightarrow 3)$ and $(3 \rightarrow 1 \rightarrow 2)$.
 - The path $(1 \rightarrow 2 \rightarrow 1)$ is a valid path of length $2$ from $1$ to $1$ but it is not optimal since there is a path of length $0$ from $1$ to $1$.

-----Examples-----
Sample Input 1:
3
1 2
1 3
Sample Output 1:
2

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

Sample Input 3:
10
1 2
2 3
2 4
1 5
3 6
2 7
7 8
5 9
5 10
Sample Output 3:
24

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ralph is going to collect mushrooms in the Mushroom Forest. 

There are m directed paths connecting n trees in the Mushroom Forest. On each path grow some mushrooms. When Ralph passes a path, he collects all the mushrooms on the path. The Mushroom Forest has a magical fertile ground where mushrooms grow at a fantastic speed. New mushrooms regrow as soon as Ralph finishes mushroom collection on a path. More specifically, after Ralph passes a path the i-th time, there regrow i mushrooms less than there was before this pass. That is, if there is initially x mushrooms on a path, then Ralph will collect x mushrooms for the first time, x - 1 mushrooms the second time, x - 1 - 2 mushrooms the third time, and so on. However, the number of mushrooms can never be less than 0.

For example, let there be 9 mushrooms on a path initially. The number of mushrooms that can be collected from the path is 9, 8, 6 and 3 when Ralph passes by from first to fourth time. From the fifth time and later Ralph can't collect any mushrooms from the path (but still can pass it).

Ralph decided to start from the tree s. How many mushrooms can he collect using only described paths?

Input

The first line contains two integers n and m (1 ≤ n ≤ 106, 0 ≤ m ≤ 106), representing the number of trees and the number of directed paths in the Mushroom Forest, respectively.

Each of the following m lines contains three integers x, y and w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 108), denoting a path that leads from tree x to tree y with w mushrooms initially. There can be paths that lead from a tree to itself, and multiple paths between the same pair of trees.

The last line contains a single integer s (1 ≤ s ≤ n) — the starting position of Ralph. 

Output

Print an integer denoting the maximum number of the mushrooms Ralph can collect during his route. 

Examples

Input

2 2
1 2 4
2 1 4
1


Output

16

Input

3 3
1 2 4
2 3 3
1 3 8
1


Output

8

Note

In the first sample Ralph can pass three times on the circle and collect 4 + 4 + 3 + 3 + 1 + 1 = 16 mushrooms. After that there will be no mushrooms for Ralph to collect.

In the second sample, Ralph can go to tree 3 and collect 8 mushrooms on the path from tree 1 to tree 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke has a grid consisting of three squares numbered 1, 2 and 3.
In each square, either 0 or 1 is written. The number written in Square i is s_i.
Snuke will place a marble on each square that says 1.
Find the number of squares on which Snuke will place a marble.

-----Constraints-----
 - Each of s_1, s_2 and s_3 is either 1 or 0.

-----Input-----
Input is given from Standard Input in the following format:
s_{1}s_{2}s_{3}

-----Output-----
Print the answer.

-----Sample Input-----
101

-----Sample Output-----
2

 - A marble will be placed on Square 1 and 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mahmoud and Ehab play a game called the even-odd game. Ehab chooses his favorite integer n and then they take turns, starting from Mahmoud. In each player's turn, he has to choose an integer a and subtract it from n such that:  1 ≤ a ≤ n.  If it's Mahmoud's turn, a has to be even, but if it's Ehab's turn, a has to be odd. 

If the current player can't choose any number satisfying the conditions, he loses. Can you determine the winner if they both play optimally?


-----Input-----

The only line contains an integer n (1 ≤ n ≤ 10^9), the number at the beginning of the game.


-----Output-----

Output "Mahmoud" (without quotes) if Mahmoud wins and "Ehab" (without quotes) otherwise.


-----Examples-----
Input
1

Output
Ehab
Input
2

Output
Mahmoud


-----Note-----

In the first sample, Mahmoud can't choose any integer a initially because there is no positive even integer less than or equal to 1 so Ehab wins.

In the second sample, Mahmoud has to choose a = 2 and subtract it from n. It's Ehab's turn and n = 0. There is no positive odd integer less than or equal to 0 so Mahmoud wins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have sticks numbered 1, \cdots, N. The length of Stick i (1 \leq i \leq N) is L_i.
In how many ways can we choose three of the sticks with different lengths that can form a triangle?
That is, find the number of triples of integers (i, j, k) (1 \leq i < j < k \leq N) that satisfy both of the following conditions:
 - L_i, L_j, and L_k are all different.
 - There exists a triangle whose sides have lengths L_i, L_j, and L_k.

-----Constraints-----
 - 1 \leq N \leq 100
 - 1 \leq L_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
L_1 L_2 \cdots L_N

-----Output-----
Print the number of ways to choose three of the sticks with different lengths that can form a triangle.

-----Sample Input-----
5
4 4 9 7 5

-----Sample Output-----
5

The following five triples (i, j, k) satisfy the conditions: (1, 3, 4), (1, 4, 5), (2, 3, 4), (2, 4, 5), and (3, 4, 5).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a board with an H \times W grid. Each square in the grid is painted in black or white. The square at the i-th row from the top and j-th column from the left is black if the j-th character in S_i is `#`, and white if that character is `.`.

Snuke can perform the following operation on the grid any number of times:

* Select a row or column in the grid, and invert the color of all the squares in that row or column (that is, black squares become white and vice versa).



Then, Snuke draws a rectangle along grid lines. Here, all the squares contained in the rectangle must be painted in black.

Find the maximum possible area of Snuke's rectangle when the operation is performed optimally.

Constraints

* 2 \leq H \leq 2000
* 2 \leq W \leq 2000
* |S_i| = W
* S_i consists of `#` and `.`.

Input

Input is given from Standard Input in the following format:


H W
S_1
S_2
:
S_H


Output

Print the maximum possible area of Snuke's rectangle.

Examples

Input

3 3
..#
##.
.#.


Output

6


Input

3 3
..#
.
.#.


Output

6


Input

4 4
....
....
....
....


Output

16


Input

10 8
...#.#
...#.#
..###.#.
.##.#.#
.#..#.#.
..##.#.#
.#.#..
...#.#..
.#.##
..###


Output

27

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Dima and Sequence

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Dima got into number sequences. Now he's got sequence *a*1,<=*a*2,<=...,<=*a**n*, consisting of *n* positive integers. Also, Dima has got a function *f*(*x*), which can be defined with the following recurrence:
 -  *f*(0)<==<=0; -  *f*(2·*x*)<==<=*f*(*x*); -  *f*(2·*x*<=+<=1)<==<=*f*(*x*)<=+<=1. 
Dima wonders, how many pairs of indexes (*i*,<=*j*) (1<=≤<=*i*<=&lt;<=*j*<=≤<=*n*) are there, such that *f*(*a**i*)<==<=*f*(*a**j*). Help him, count the number of such pairs.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105). The second line contains *n* positive integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109).

The numbers in the lines are separated by single spaces.

Output Specification:
In a single line print the answer to the problem.

Please, don't use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Demo Input:
['3\n1 2 4\n', '3\n5 3 1\n']

Demo Output:
['3\n', '1\n']

Note:
In the first sample any pair (*i*, *j*) will do, so the answer is 3.

In the second sample only pair (1, 2) will do.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Significant Cups

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Stepan is a very experienced olympiad participant. He has *n* cups for Physics olympiads and *m* cups for Informatics olympiads. Each cup is characterized by two parameters — its significance *c**i* and width *w**i*.

Stepan decided to expose some of his cups on a shelf with width *d* in such a way, that:
 -  there is at least one Physics cup and at least one Informatics cup on the shelf, -  the total width of the exposed cups does not exceed *d*, -  from each subjects (Physics and Informatics) some of the most significant cups are exposed (i. e. if a cup for some subject with significance *x* is exposed, then all the cups for this subject with significance greater than *x* must be exposed too). 
Your task is to determine the maximum possible total significance, which Stepan can get when he exposes cups on the shelf with width *d*, considering all the rules described above. The total significance is the sum of significances of all the exposed cups.

Input Specification:
The first line contains three integers *n*, *m* and *d* (1<=≤<=*n*,<=*m*<=≤<=100<=000, 1<=≤<=*d*<=≤<=109) — the number of cups for Physics olympiads, the number of cups for Informatics olympiads and the width of the shelf.

Each of the following *n* lines contains two integers *c**i* and *w**i* (1<=≤<=*c**i*,<=*w**i*<=≤<=109) — significance and width of the *i*-th cup for Physics olympiads.

Each of the following *m* lines contains two integers *c**j* and *w**j* (1<=≤<=*c**j*,<=*w**j*<=≤<=109) — significance and width of the *j*-th cup for Informatics olympiads.

Output Specification:
Print the maximum possible total significance, which Stepan can get exposing cups on the shelf with width *d*, considering all the rules described in the statement.

If there is no way to expose cups on the shelf, then print 0.

Demo Input:
['3 1 8\n4 2\n5 5\n4 2\n3 2\n', '4 3 12\n3 4\n2 4\n3 5\n3 4\n3 5\n5 2\n3 4\n', '2 2 2\n5 3\n6 3\n4 2\n8 1\n']

Demo Output:
['8\n', '11\n', '0\n']

Note:
In the first example Stepan has only one Informatics cup which must be exposed on the shelf. Its significance equals 3 and width equals 2, so after Stepan exposes it, the width of free space on the shelf becomes equal to 6. Also, Stepan must expose the second Physics cup (which has width 5), because it is the most significant cup for Physics (its significance equals 5). After that Stepan can not expose more cups on the shelf, because there is no enough free space. Thus, the maximum total significance of exposed cups equals to 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S containing only digits, Your task is to complete the function genIp() which returns a vector containing all possible combinations of valid IPv4 IP addresses and takes only a string S as its only argument.
Note: Order doesn't matter. A valid IP address must be in the form of A.B.C.D, where A, B, C, and D are numbers from 0-255. The numbers cannot be 0 prefixed unless they are 0.
For string 11211 the IP address possible are 
1.1.2.11
1.1.21.1
1.12.1.1
11.2.1.1
Example 1:
Input:
S = 1111
Output: 1.1.1.1
Example 2:
Input:
S = 55
Output: -1
Your Task:
Your task is to complete the function genIp() which returns a vector containing all possible combinations of valid IPv4 IP addresses or -1 if no such IP address could be generated through the input string S, the only argument to the function.
Expected Time Complexity: O(N * N * N)
Expected Auxiliary Space: O(N * N * N * N)
Constraints:
1<=N<=16
here, N = length of S.
S only contains digits(i.e. 0-9)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
View Russian Translation

Little pig Benny has just taken a shower. Now she is going to buy some gifts for her relatives. But the problem is that Benny doesn't know how to reach to the gift shop. Her friend Mike has created a special set of instructions for her. 
A set of instructions is a string which consists of letters {'L', 'R', 'U', 'D'}. 

For simplicity, let's assume that Benny is staying at point (0, 0) on the infinite plane. She consistently fulfills all the instructions written by Mike. Let's assume that now she is staying at point (X, Y).  Then depending on what is the current instruction she moves in some direction: 
'L' -- from  (X, Y) moves to point (X, Y - 1)
'R' -- from  (X, Y) moves to point (X, Y + 1)
'U' -- from  (X, Y) moves to point (X - 1, Y)
'D' -- from (X, Y) moves to point (X + 1, Y)

The weather is cold because it's winter now. Initially, all points are snowy. But if Benny have already visited some point at any time this point becomes icy (because Benny has just taken a shower). Every time, when Benny makes a step into icy points she slips and falls down.

You are given a string S which denotes a set of instructions for Benny. Your task is to calculate how may times she will fall down.

Input format

Single line contains string S.

Output format

Output how many times Benny will fall down.

Constraints

- 1 ≤
S
≤ 10^5
SAMPLE INPUT
RRULDL

SAMPLE OUTPUT
2

Explanation

Benny's route consists of points 

0 0 (becomes icy) --> 0 1 (becomes icy) --> 0 2 (becomes icy) --> -1 2 (becomes icy) --> -1 1 (becomes icy) --> 0 1 (is icy) --> 0 0 (is icy)

So Benny made two steps into icy points.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your Goal is to create a function that takes  two strings, a guess and a phone number. 

Based on the guess, the function should display a portion of the phone number:

    guess_my_number('052', '123-451-2345')
    would return the string: '#2#-#5#-2##5'
    
    or
    
    guess_my_number('142', '123-451-2345')
    would return the string: '12#-4#1-2#4#'
    
Order of the guess string should not matter, and should not have duplicates of the ten digitis 0-9. Guess will never be an empty string or contains any other charachters. The phone number will always bea ten digit number in the format ###-###-####.

The default number of 123-451-2345 should be included, but can be overwriten by a different number if supplied at the time of execution.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Fibonacci sequence is defined as F(n) = F(n-1) + F(n-2). You have developed two sequences of numbers. The first sequence that uses the bitwise XOR operation instead of the addition method is called the Xoronacci number. It is described as follows:
X(n) = X(n-1) XOR X(n-2)
The second sequence that uses the bitwise XNOR operation instead of the addition method is called the XNoronacci number. It is described as follows:
E(n) = E(n-1) XNOR E(n-2)
The first and second numbers of the sequence are as follows:
X(1) = E(1) = a
X(2) = E(2) = b
Your task is to determine the value of max(X(n),E(n)), where n is the n th term of the Xoronacci and XNoronacci sequence.

-----Input:-----
The first line consists of a single integer T denoting the number of test cases.
The first and the only line of each test case consists of three space separated integers a, b and n.

-----Output:-----
For each test case print a single integer max(X(n),E(n)).

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq a,b,n \leq 1000000000000$

-----Sample Input:-----
1
3 4 2 

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

-----EXPLANATION:-----
Xoronacci Sequence : 3 4 7 …….
XNoronacci Sequence : 3 4 0 …….
Here n = 2. Hence max(X(2),E(2)) = 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two red beads are placed between every two blue beads. There are N blue beads. After looking at the arrangement below work out the number of red beads.

@
@@
@
@@
@
@@
@
@@
@
@@
@

Implement count_red_beads(n) (in PHP count_red_beads($n); in Java, Javascript, TypeScript, C, C++ countRedBeads(n)) so that it returns the number of red beads.
If there are less than 2 blue beads return 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.