vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Chef has just finished the construction of his new garden. He has sown the garden with patches of the most beautiful carpet grass he could find. He has filled it with patches of different color and now he wants to evaluate how elegant his garden is.
Chef's garden looks like a rectangular grid of cells with N rows and M columns. So there are N x M cells in total.	In each cell Chef planted grass of some color.
The elegance of the garden is defined by the number of squares, composed of at least four  garden cells, with edges parallel to the sides of the garden, that have four corner cells of the same color.
Given the description of Chef's garden, calculate how many such squares exist.
Input format
The first line contains the number T, the number of test cases. In the following lines,	T test cases follow (without any newlines between them.)
The first line of each test case contains N and M, separated by a single space.
Each of the next N lines contains M characters without any spaces between them, and without any leading or trailing spaces.
Each character describes the color of the corresponding cell in the garden and belongs to the set of lowercase and uppercase lettes of the English alphabet.
One letter in lowercase and uppercase describes different colors.
Output format
For each test case, print the number of squares that conform to the definition in the	problem statement.
Constraints
1 ≤ T ≤ 50

1 ≤ N, M ≤ 50

Sample input
3
2 2
aa
aA
3 3
aba
bab
aba
4 4
aabb
aabb
bbaa
bbaa

Sample output
0
1
4

Explanation
In the first case the only avaliable square does not conform to the definition in the problem statement because 'a' and 'A' describes different colors.
In the second case, you can select the 4 a's at the corners of the garden.
In the third case, you can only make four squares, from the four 2x2 segments	that are of the same color.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef hates unoptimized codes and people who write such codes. One fine day he decided to look through the kitchen's codebase and found a function whose pseudo-code is given here:

input: integer N, list X[1, 2, ..., N], list Y[1, 2, ..., N]

output: integer res

function:

set res = 0;
for i := 1 to N do
for j := 1 to N do
for k := 1 to N do
if (X[i] = X[j]) OR (X[j] = X[k]) OR (X[k] = X[i])
continue
else
set res = max(res, Y[i] + Y[j] + Y[k])
return res

Luckily enough this code gets triggered only if the Head Chef makes a submission. But still there is a possibility that this can crash the judge. So help Chef by writing a new function which does the same thing but is faster.

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N denoting the number of elements in the two lists.
- The i-th of the next N lines contains a pair of space-separated integers denoting the values of X[i] and Y[i] respectively.

-----Output-----
For each test case, output an integer corresponding to the return value of the function.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ X[i], Y[i] ≤ 108

-----Example-----
Input
2
3
1 3
3 1
1 2
5
1 3
2 4
1 2
3 2
3 4

Output
0
11

-----Explanation-----
Testcase 2: The maximum is attained when i = 1, j = 2 and k = 5. This leads to res being 3 + 4 + 4 = 11. This value is attained in other iterations as well, but it never exceeds this, and hence this is the answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A New Year party is not a New Year party without lemonade! As usual, you are expecting a lot of guests, and buying lemonade has already become a pleasant necessity.

Your favorite store sells lemonade in bottles of n different volumes at different costs. A single bottle of type i has volume 2^{i} - 1 liters and costs c_{i} roubles. The number of bottles of each type in the store can be considered infinite.

You want to buy at least L liters of lemonade. How many roubles do you have to spend?


-----Input-----

The first line contains two integers n and L (1 ≤ n ≤ 30; 1 ≤ L ≤ 10^9) — the number of types of bottles in the store and the required amount of lemonade in liters, respectively.

The second line contains n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ 10^9) — the costs of bottles of different types.


-----Output-----

Output a single integer — the smallest number of roubles you have to pay in order to buy at least L liters of lemonade.


-----Examples-----
Input
4 12
20 30 70 90

Output
150

Input
4 3
10000 1000 100 10

Output
10

Input
4 3
10 100 1000 10000

Output
30

Input
5 787787787
123456789 234567890 345678901 456789012 987654321

Output
44981600785557577



-----Note-----

In the first example you should buy one 8-liter bottle for 90 roubles and two 2-liter bottles for 30 roubles each. In total you'll get 12 liters of lemonade for just 150 roubles.

In the second example, even though you need only 3 liters, it's cheaper to buy a single 8-liter bottle for 10 roubles.

In the third example it's best to buy three 1-liter bottles for 10 roubles each, getting three liters for 30 roubles.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Mister B and Boring Game

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Sometimes Mister B has free evenings when he doesn't know what to do. Fortunately, Mister B found a new game, where the player can play against aliens.

All characters in this game are lowercase English letters. There are two players: Mister B and his competitor.

Initially the players have a string *s* consisting of the first *a* English letters in alphabetical order (for example, if *a*<==<=5, then *s* equals to "abcde").

The players take turns appending letters to string *s*. Mister B moves first.

Mister B must append exactly *b* letters on each his move. He can arbitrary choose these letters. His opponent adds exactly *a* letters on each move.

Mister B quickly understood that his opponent was just a computer that used a simple algorithm. The computer on each turn considers the suffix of string *s* of length *a* and generates a string *t* of length *a* such that all letters in the string *t* are distinct and don't appear in the considered suffix. From multiple variants of *t* lexicographically minimal is chosen (if *a*<==<=4 and the suffix is "bfdd", the computer chooses string *t* equal to "aceg"). After that the chosen string *t* is appended to the end of *s*.

Mister B soon found the game boring and came up with the following question: what can be the minimum possible number of different letters in string *s* on the segment between positions *l* and *r*, inclusive. Letters of string *s* are numerated starting from 1.

Input Specification:
First and only line contains four space-separated integers: *a*, *b*, *l* and *r* (1<=≤<=*a*,<=*b*<=≤<=12, 1<=≤<=*l*<=≤<=*r*<=≤<=109) — the numbers of letters each player appends and the bounds of the segment.

Output Specification:
Print one integer — the minimum possible number of different letters in the segment from position *l* to position *r*, inclusive, in string *s*.

Demo Input:
['1 1 1 8\n', '4 2 2 6\n', '3 7 4 6\n']

Demo Output:
['2', '3', '1']

Note:
In the first sample test one of optimal strategies generate string *s* = "abababab...", that's why answer is 2.

In the second sample test string *s* = "abcdbcaefg..." can be obtained, chosen segment will look like "bcdbc", that's why answer is 3.

In the third sample test string *s* = "abczzzacad..." can be obtained, chosen, segment will look like "zzz", that's why answer is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Cesar and Raul like betting and good food, in no particular order. They want to try out a new fancy restaurant and they decided to make a bet – they are going to play a game and the loser pays for dinner.

They have a box with $N$ balls. Each ball contains a distinct number between $1$ and $N$. Then, the game proceeds with these steps:
 - Initially, each person picks $C$ distinct numbers between $1$ and $N$ and writes them down on a separate card.
 - In each round, $D$ balls are drawn from the box uniformly at random. Cesar and Raul mark the ball numbers that appear on their respective card. The $D$ balls are then returned to the box.
 - The game stops when a player has marked all the numbers he chose. That player is the winner. If both players finish at the same time, it is a draw and they will split the dinner.

They are quite eager to try out this new restaurant and they’re now wondering: how many rounds will the game last until at least one of the players has marked all his numbers?

-----Task-----
Given the number $N$ of balls, the number $D$ of balls they draw from the box in each round, the amount $C$ of numbers in their cards and the numbers they wrote down, find the expected number of rounds the game will last.

-----Input-----
The first line of the input consists of three space separated integers: $N$, $D$, and $C$. $N$ is the number of balls, $D$ is the number of balls drawn in each round, and $C$ is the cards’ size. Each of the following two lines contains $C$ space separated integers: the numbers Cesar and Raul wrote down, respectively.

-----Constraints-----

$1$

$\leq $

$N$

$\leq $

$50$

Number of balls in the box

$1$

$\leq $

$D$

$\leq $

$\min (10, N)$

Number of balls drawn in each round

$1$

$\leq $

$C$

$\leq $

$\min (10, N)$

Cards’ sizeOutput

The output is the expected number of rounds of the game.

The result will be considered correct as long as the absolute error does not exceed $10^{-3}$.

-----Explanation for Sample Input 1-----
There are $2$ balls. Cesar picked number $1$ and Raul picked number $2$. In the first round, either number $1$ or $2$ will be drawn and so one of them wins right away.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An AI has infected a text with a character!! 

This text is now **fully mutated** to this character.

If the text or the character are empty, return an empty string.  
There will never be a case when both are empty as nothing is going on!!

**Note:** The character is a string of length 1 or an empty string.

# Example
```python
text before = "abc"
character   = "z"
text after  = "zzz"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bessie has way too many friends because she is everyone's favorite cow! Her new friend Rabbit is trying to hop over so they can play! 

More specifically, he wants to get from $(0,0)$ to $(x,0)$ by making multiple hops. He is only willing to hop from one point to another point on the 2D plane if the Euclidean distance between the endpoints of a hop is one of its $n$ favorite numbers: $a_1, a_2, \ldots, a_n$. What is the minimum number of hops Rabbit needs to get from $(0,0)$ to $(x,0)$? Rabbit may land on points with non-integer coordinates. It can be proved that Rabbit can always reach his destination.

Recall that the Euclidean distance between points $(x_i, y_i)$ and $(x_j, y_j)$ is $\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$.

For example, if Rabbit has favorite numbers $1$ and $3$ he could hop from $(0,0)$ to $(4,0)$ in two hops as shown below. Note that there also exists other valid ways to hop to $(4,0)$ in $2$ hops (e.g. $(0,0)$ $\rightarrow$ $(2,-\sqrt{5})$ $\rightarrow$ $(4,0)$).

 $1$ Here is a graphic for the first example. Both hops have distance $3$, one of Rabbit's favorite numbers. 

In other words, each time Rabbit chooses some number $a_i$ and hops with distance equal to $a_i$ in any direction he wants. The same number can be used multiple times.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 1000$)  — the number of test cases. Next $2t$ lines contain test cases — two lines per test case.

The first line of each test case contains two integers $n$ and $x$ ($1 \le n \le 10^5$, $1 \le x \le 10^9$)  — the number of favorite numbers and the distance Rabbit wants to travel, respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$)  — Rabbit's favorite numbers. It is guaranteed that the favorite numbers are distinct.

It is guaranteed that the sum of $n$ over all the test cases will not exceed $10^5$.


-----Output-----

For each test case, print a single integer — the minimum number of hops needed.


-----Example-----
Input
4
2 4
1 3
3 12
3 4 5
1 5
5
2 10
15 4

Output
2
3
1
2



-----Note-----

The first test case of the sample is shown in the picture above. Rabbit can hop to $(2,\sqrt{5})$, then to $(4,0)$ for a total of two hops. Each hop has a distance of $3$, which is one of his favorite numbers.

In the second test case of the sample, one way for Rabbit to hop $3$ times is: $(0,0)$ $\rightarrow$ $(4,0)$ $\rightarrow$ $(8,0)$ $\rightarrow$ $(12,0)$.

In the third test case of the sample, Rabbit can hop from $(0,0)$ to $(5,0)$.

In the fourth test case of the sample, Rabbit can hop: $(0,0)$ $\rightarrow$ $(5,10\sqrt{2})$ $\rightarrow$ $(10,0)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a pole vaulter, it is very important to begin the approach run at the best possible starting mark. This is affected by numerous factors and requires fine-tuning in practice. But there is a guideline that will help a beginning vaulter start at approximately the right location for the so-called "three-step approach," based on the vaulter's body height.

This guideline was taught to me in feet and inches, but due to the international nature of Codewars, I am creating this kata to use metric units instead.

You are given the following two guidelines to begin with:
(1) A vaulter with a height of 1.52 meters should start at 9.45 meters on the runway.
(2) A vaulter with a height of 1.83 meters should start at 10.67 meters on the runway.

You will receive a vaulter's height in meters (which will always lie in a range between a minimum of 1.22 meters and a maximum of 2.13 meters). Your job is to return the best starting mark in meters, rounded to two decimal places.

Hint: Based on the two guidelines given above, you will want to account for the change in starting mark per change in body height. This involves a linear relationship. But there is also a constant offset involved. If you can determine the rate of change described above, you should be able to determine that constant offset.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Regional College is having N branches, where each branches have positive integral student. A minimize operation is performed on the branch such that all of them are reduced by the minimum number student in a branch.

Suppose we have 5 branches and all of them have below students in a branch.

5 2 4 2 6

Then in one minimize operation we reduce all the branch by 2 students. For next minimize operation 3 branch are left (have non-zero student), whose value are

3 2 4

Above step is repeated till no students are left in all branches.

Given students of N branches, print the number of student that are reduce in subsequent minimize operation.

Input Format

The first line contains a single integer N.

The next line contains N integers : X(0), X(1), X(2),..... X(N-1) separated by space, where X(i) represents the student of ith branch.

Output Format

For each minimize operation, print the number of students that are reduced in branches in separate line.

Constraints

1 ≤ N ≤ 1000

1 ≤ X(i) ≤ 1000

SAMPLE INPUT
6
5 4 4 2 2 8

SAMPLE OUTPUT
6
4
2
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given $n$ words, each of which consists of lowercase alphabet letters. Each word contains at least one vowel. You are going to choose some of the given words and make as many beautiful lyrics as possible.

Each lyric consists of two lines. Each line consists of two words separated by whitespace. 

A lyric is beautiful if and only if it satisfies all conditions below.   The number of vowels in the first word of the first line is the same as the number of vowels in the first word of the second line.  The number of vowels in the second word of the first line is the same as the number of vowels in the second word of the second line.  The last vowel of the first line is the same as the last vowel of the second line. Note that there may be consonants after the vowel. 

Also, letters "a", "e", "o", "i", and "u" are vowels. Note that "y" is never vowel.

For example of a beautiful lyric,  "hello hellooowww" 

"whatsup yowowowow"  is a beautiful lyric because there are two vowels each in "hello" and "whatsup", four vowels each in "hellooowww" and "yowowowow" (keep in mind that "y" is not a vowel), and the last vowel of each line is "o".

For example of a not beautiful lyric,  "hey man"

"iam mcdic"  is not a beautiful lyric because "hey" and "iam" don't have same number of vowels and the last vowels of two lines are different ("a" in the first and "i" in the second).

How many beautiful lyrics can you write from given words? Note that you cannot use a word more times than it is given to you. For example, if a word is given three times, you can use it at most three times.


-----Input-----

The first line contains single integer $n$ ($1 \le n \le 10^{5}$) — the number of words.

The $i$-th of the next $n$ lines contains string $s_{i}$ consisting lowercase alphabet letters — the $i$-th word. It is guaranteed that the sum of the total word length is equal or less than $10^{6}$. Each word contains at least one vowel.


-----Output-----

In the first line, print $m$ — the number of maximum possible beautiful lyrics.

In next $2m$ lines, print $m$ beautiful lyrics (two lines per lyric).

If there are multiple answers, print any.


-----Examples-----
Input
14
wow
this
is
the
first
mcdics
codeforces
round
hooray
i
am
proud
about
that

Output
3
about proud
hooray round
wow first
this is
i that
mcdics am

Input
7
arsijo
suggested
the
idea
for
this
problem

Output
0

Input
4
same
same
same
differ

Output
1
same differ
same same



-----Note-----

In the first example, those beautiful lyrics are one of the possible answers. Let's look at the first lyric on the sample output of the first example. "about proud hooray round" forms a beautiful lyric because "about" and "hooray" have same number of vowels, "proud" and "round" have same number of vowels, and both lines have same last vowel. On the other hand, you cannot form any beautiful lyric with the word "codeforces".

In the second example, you cannot form any beautiful lyric from given words.

In the third example, you can use the word "same" up to three times.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is the first subtask of problem F. The only differences between this and the second subtask are the constraints on the value of $m$ and the time limit. You need to solve both subtasks in order to hack this one.

There are $n+1$ distinct colours in the universe, numbered $0$ through $n$. There is a strip of paper $m$ centimetres long initially painted with colour $0$. 

Alice took a brush and painted the strip using the following process. For each $i$ from $1$ to $n$, in this order, she picks two integers $0 \leq a_i < b_i \leq m$, such that the segment $[a_i, b_i]$ is currently painted with a single colour, and repaints it with colour $i$. 

Alice chose the segments in such a way that each centimetre is now painted in some colour other than $0$. Formally, the segment $[i-1, i]$ is painted with colour $c_i$ ($c_i \neq 0$). Every colour other than $0$ is visible on the strip.

Count the number of different pairs of sequences $\{a_i\}_{i=1}^n$, $\{b_i\}_{i=1}^n$ that result in this configuration. 

Since this number may be large, output it modulo $998244353$.


-----Input-----

The first line contains a two integers $n$, $m$ ($1 \leq n \leq 500$, $n = m$) — the number of colours excluding the colour $0$ and the length of the paper, respectively.

The second line contains $m$ space separated integers $c_1, c_2, \ldots, c_m$ ($1 \leq c_i \leq n$) — the colour visible on the segment $[i-1, i]$ after the process ends. It is guaranteed that for all $j$ between $1$ and $n$ there is an index $k$ such that $c_k = j$.

Note that since in this subtask $n = m$, this means that $c$ is a permutation of integers $1$ through $n$.


-----Output-----

Output a single integer — the number of ways Alice can perform the painting, modulo $998244353$.


-----Examples-----
Input
3 3
1 2 3

Output
5

Input
7 7
4 5 1 6 2 3 7

Output
165



-----Note-----

In the first example, there are $5$ ways, all depicted in the figure below. Here, $0$ is white, $1$ is red, $2$ is green and $3$ is blue.

[Image]

Below is an example of a painting process that is not valid, as in the second step the segment 1 3 is not single colour, and thus may not be repainted with colour $2$.

[Image]

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

Given a multiset of nonnegative integers a_1, a_2, .., a_N.

How many non-empty subsets of this set have a value bitwiseAND of 0?

Find the remainder of the answer divided by 10 ^ 9 + 7.

input


N
a_1 a_2 ... a_N


output

Divide the answer by 10 ^ 9 + 7 and output the remainder.

Constraint

* 1 \ leq N \ leq 10 ^ 5
* 0 \ leq a_i \ leq 2 ^ {20} -1



Input example


6
8 6 9 1 2 1


Output example


51






Example

Input

6
8 6 9 1 2 1


Output

51

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In an NxM grid with each cell's dimension being 1x1, there will be (N+1) x (M+1) cross points. 
You task is to count the number of ways (S) of choosing K different points from these cross points such that all of them lie on a straight line and at least one of the cross points lies on the border.

Input Format  

A single line containing 3 integers N, M & K separated by a single space. 

Output Format  

A single integer denoting the number of ways (S) modulo 1000000007

Constraints

0 < N, M <= 3000 

2 <= K <= max(N, M) + 1

Sample Input  

2 2 3

Sample Output  

8

Explanation  

If you imagine a grid of the first quadrant of the co-ordinate system. Then, we have, 8 such 3 points of which at least 1 point on the borders. 

(0,0), (0,1), (0,2) 

(1,0), (1,1), (1,2) 

(2,0), (2,1), (2,2) 

(0,0), (1,0), (2,0) 

(0,1), (1,1), (2,1) 

(0,2), (1,2), (2,2) 

(0,0), (1,1), (2,2) and 

(0,2), (1,1), (2,0)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an empty graph of N vertices and M queries of two types:
Given a number X answer what is the shortest distance from the vertex 1 to the vertex X.
Given two integers X, Y add the new oriented edge from X to Y.

Input
The first line contains two integers N and M.
The following M lines describe queries in the format mentioned above

Output
For each query of the first type output one integer on a separate line - answer for the corresponding query. Output -1 if it's impossible to get to the vertex in this query from the vertex 1.

Constraints
1 ≤ N ≤ 1000
1 ≤ M ≤ 500 000
1 ≤ X, Y ≤ N

SAMPLE INPUT
4 7
1 4
2 1 2
2 2 3
2 3 4
1 4
2 2 4
1 4


SAMPLE OUTPUT
-1
3
2

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