vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are playing a solitaire puzzle called "Connect", which uses several letter tiles.

There are R × C empty cells. For each i (1 ≤ i ≤ R), you must put a string si (1 ≤ |si| ≤ C) in the i-th row of the table, without changing the letter order. In other words, you choose an integer sequence {aj} such that 1 ≤ a1 < a2 < ... < a|si| ≤ C , and put the j-th character of the string si in the aj-th column (1 ≤ j ≤ |si|).

For example, when C = 8 and si = "ICPC", you can put si like followings.


I_C_P_C_
ICPC____
_IC___PC


'_' represents an empty cell.

For each non-empty cell x, you get a point equal to the number of adjacent cells which have the same character as x. Two cells are adjacent if they share an edge.

Calculate the maximum total point you can get.



Input

The first line contains two integers R and C (1 ≤ R ≤ 128, 1 ≤ C ≤ 16).

Then R lines follow, each of which contains si (1 ≤ |si| ≤ C). All characters of si are uppercase letters.

Output

Output the maximum total point in a line.

Examples

Input

2 4
ACM
ICPC


Output

2


Input

2 9
PROBLEMF
CONNECT


Output

6


Input

4 16
INTERNATIONAL
COLLEGIATE
PROGRAMMING
CONTEST


Output

18

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Black Friday is the Friday following Thanksgiving Day in the United States (the fourth Thursday of November). Since the early 2000s, it has been regarded as the beginning of the Christmas shopping season in the US, and most major retailers open very early and offer promotional sales. (Source: Wikipedia)

You work in the IT support division of an electronics store. This year, in an attempt to prevent overcrowding, the management has decided to limit the number of people entering the store. They divide the people at the entrance into groups of size $n$ and process them as follows: all $n$ participants roll a die, and report the outcomes $a_1, a_2, \ldots , a_ n$. To prevent cheating, instead of selecting the one with the highest outcome, the rule is to select the participant with the highest unique outcome. Everybody not selected has to move to the back of the queue. If there is no winner, the experiment is repeated.

For example, if there are three players and the outcomes are 6, 6 and 5, then the third player wins, because the first and second player lose even though their outcomes are higher, since they both have the same outcome. If instead the third player also rolls 6, then nobody wins.

They asked you to write a program for selecting the winner.

-----Input-----
The first line of the input contains one integer $n$, $1 \leq n \leq 100$, the group size. The second line contains $n$ integers $a_1, a_2, \ldots , a_ n$ ($1 \leq a_ i \leq 6$ for all $1 \leq i \leq n$): the outcome of each participant’s die roll.

-----Output-----
Output the index of the participant that has the highest unique outcome, or “none” (without the quotes) if nobody has a unique outcome.

-----Examples-----
Sample Input:
8
1 1 1 5 3 4 6 6
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that takes an integer and returns an array `[A, B, C]`, where `A` is the number of multiples of 3 (but not 5) below the given integer, `B` is the number of multiples of 5 (but not 3) below the given integer and `C` is the number of multiples of 3 and 5 below the given integer. 

For example, `solution(20)` should return `[5, 2, 1]`

~~~if:r
```r
# in R, returns a numeric vector
solution(20)
[1] 5 2 1

class(solution(20))
[1] "numeric"
```
~~~

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"ACM48" is one of the most popular dance vocal units in Japan. In this winter, ACM48 is planning a world concert tour. You joined the tour as a camera engineer.

Your role is to develop software which controls the camera on a stage. For simplicity you can regard the stage as 2-dimensional space. You can rotate the camera to an arbitrary direction by the software but cannot change its coordinate.

During a stage performance, each member of ACM48 moves along her route and sings the part(s) assigned to her. Here, a route is given as a polygonal line.

You have to keep focusing the camera on a member during a stage performance. You can change the member focused by the camera if and only if the current and next members are in the same direction from the camera.

Your task is to write a program which reads the stage performance plan and calculates the maximum time that you can focus the camera on members that are singing.

You may assume the following are satisfied:

* You can focus the camera on an arbitrary member at the beginning time.
* Each route of the member does not touch the camera.
* Each member stays at the last coordinates after she reaches there.



Input

The input contains multiple test cases. Each test case has the following format:

N
cx cy
The information of the 1-st member
.
.
.
The information of the N-th member


N (1 ≤ N ≤ 50) is the number of the members. (cx, cy) is the coordinates of the camera. Then the information of the N members follow.

The information of the i-th member has the following format:

Mi
xi,1 yi,1 ti,1
.
.
.
xi,Mi yi,Mi ti,Mi
Li
bi,1 ei,1
.
.
.
bi,Li ei,Li


Mi (1 ≤ Mi ≤ 100) is the number of the points in the route. (xi,j, yi,j ) is the coordinates of the j-th in the route. ti,j (0 = ti,0 < ti,j < ti,j+1 ≤ 103 for 0 < j) is the time that the i-th member reaches the j-th coordinates. Li (0 ≤ Li ≤ 100) is the number of the vocal part. bi,k and ei,k (0 ≤ bi,k < ei,k < bi,k+1 < ei,k+1 ≤ 103 ) are the beginning and the ending time of the k-th vocal part, respectively.

All the input values are integers. You may assume that the absolute of all the coordinates are not more than 103 .

N = 0 denotes the end of the input. You may not process this as a test case.

Output

For each dataset, print the maximum time that you can focus the camera on singing members with an absolute error of at most 10-6. You may output any number of digits after the decimal point.

Example

Input

2
0 0
2
-5 5 0
5 5 10
1
0 6
2
5 5 0
-5 5 10
1
6 10
1
7 -65
2
-65 10 0
65 1 3
2
0 1
23 24
2
0 0
2
100 10 0
-10 10 10
5
0 1
2 3
4 5
6 7
8 9
2
10 0 0
0 10 10
5
1 2
3 4
5 6
7 8
9 10
0


Output

9.00000000
2.00000000
5.98862017

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Our football team finished the championship.
The result of each match look like "x:y". Results of all matches are recorded in the collection.

For example:
```["3:1", "2:2", "0:1", ...]```

Write a function that takes such collection and counts the points of our team in the championship.
Rules for counting points for each match:
- if x>y - 3 points
- if x<y - 0 point
- if x=y - 1 point

Notes:
- there are 10 matches in the championship
- 0 <= x <= 4
- 0 <= y <= 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tyndex is again well ahead of the rivals! The reaction to the release of Zoozle Chrome browser was the release of a new browser Tyndex.Brome!

The popularity of the new browser is growing daily. And the secret is not even the Tyndex.Bar installed (the Tyndex.Bar automatically fills the glass with the finest 1664 cognac after you buy Tyndex.Bottles and insert in into a USB port). It is highly popular due to the well-thought interaction with the user.

Let us take, for example, the system of automatic address correction. Have you entered codehorses instead of codeforces? The gloomy Zoozle Chrome will sadly say that the address does not exist. Tyndex.Brome at the same time will automatically find the closest address and sent you there. That's brilliant!

How does this splendid function work? That's simple! For each potential address a function of the F error is calculated by the following rules:

  * for every letter ci from the potential address c the closest position j of the letter ci in the address (s) entered by the user is found. The absolute difference |i - j| of these positions is added to F. So for every i (1 ≤ i ≤ |c|) the position j is chosen such, that ci = sj, and |i - j| is minimal possible. 
  * if no such letter ci exists in the address entered by the user, then the length of the potential address |c| is added to F. 



After the values of the error function have been calculated for all the potential addresses the most suitable one is found. 

To understand the special features of the above described method better, it is recommended to realize the algorithm of calculating the F function for an address given by the user and some set of potential addresses. Good luck!

Input

The first line contains two integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 105). They are the number of potential addresses and the length of the address entered by the user. The next line contains k lowercase Latin letters. They are the address entered by the user (s). Each next i-th (1 ≤ i ≤ n) line contains a non-empty sequence of lowercase Latin letters. They are the potential address. It is guaranteed that the total length of all the lines does not exceed 2·105.

Output

On each n line of the output file print a single number: the value of the error function when the current potential address is chosen.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Examples

Input

2 10
codeforces
codeforces
codehorses


Output

0
12


Input

9 9
vkontakte
vcontacte
vkontrakte
vkollapse
vkrokodile
vtopke
vkapuste
vpechke
vk
vcodeforcese


Output

18
14
36
47
14
29
30
0
84

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gray codes are a classic topic in information theory with a number of practical applications, none of which we are concerned with in this problem. An $n$-bit Gray code is an ordering $(x_1, x_2, \ldots , x_{2^n})$ of all $n$-bit binary strings, with the property that any consecutive pair of strings differ in exactly $1$ bit. More formally, for every $1 \le i < 2^n$, it holds that $d(x_{i}, x_{i+1}) = 1$, where $d(\cdot , \cdot )$ denotes the Hamming distance between two binary strings. For instance, for $n=3$, the sequence $(000, 001, 011, 010, 110, 111, 101, 100)$ is a Gray code. 

While Gray codes are great, they are also a bit, well... gray1. In this problem, we look at a much more colorful variant.

For an integer $n \ge 1$ and set of integers $P \subseteq \{ 1, \ldots , n\} $, we say that an ordering $(x_1, \ldots , x_{2^n})$ of all $n$-bit binary strings is an $n$-bit color code with palette $P$, if for all $1 \le i < 2^n$, it holds that $d(x_ i, x_{i+1}) \in P$, i.e., the number of bits by which any consecutive pair of strings differ is in $P$.

Note that for some palettes, color codes do not exist. For instance, if $n = 6$ and $P = \{ 6\} $, the second string must be the binary negation of the first one, but then the third string must be the negation of the second one, i.e., equal to the first string.

Given $n$ and $P$, can you construct an $n$-bit color code with palette $P$?

-----Input-----
The first line of input consists of two integers $n$ ($1 \le n \le 16$) and $p$ ($1 \le p \le n$). Then follow a line with $p$ distinct integers $s_1, \ldots , s_ p$ ($1 \leq s_ i \leq n$ for each $i$) – the elements of $P$.

-----Output-----
If there is an $n$-bit color code with palette $P$, output $2^n$ lines, containing the elements of such a code, in order. If there are many different codes, any one will be accepted. If no such code exists, output “impossible”.

-----Examples-----
Sample Input 1:
6 1
6
Sample Output 1:
impossible

Sample Input 2:
3 1
1
Sample Output 2:
000
001
011
010
110
111
101
100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Roma found a new character in the game "World of Darkraft - 2". In this game the character fights monsters, finds the more and more advanced stuff that lets him fight stronger monsters.

The character can equip himself with k distinct types of items. Power of each item depends on its level (positive integer number). Initially the character has one 1-level item of each of the k types.

After the victory over the monster the character finds exactly one new randomly generated item. The generation process looks as follows. Firstly the type of the item is defined; each of the k types has the same probability. Then the level of the new item is defined. Let's assume that the level of player's item of the chosen type is equal to t at the moment. Level of the new item will be chosen uniformly among integers from segment [1; t + 1].

From the new item and the current player's item of the same type Roma chooses the best one (i.e. the one with greater level) and equips it (if both of them has the same level Roma choses any). The remaining item is sold for coins. Roma sells an item of level x of any type for x coins.

Help Roma determine the expected number of earned coins after the victory over n monsters.

Input

The first line contains two integers, n and k (1 ≤ n ≤ 105; 1 ≤ k ≤ 100).

Output

Print a real number — expected number of earned coins after victory over n monsters. The answer is considered correct if its relative or absolute error doesn't exceed 10 - 9.

Examples

Input

1 3


Output

1.0000000000


Input

2 1


Output

2.3333333333


Input

10 2


Output

15.9380768924

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One foggy Stockholm morning, Karlsson decided to snack on some jam in his friend Lillebror Svantenson's house. Fortunately for Karlsson, there wasn't anybody in his friend's house. Karlsson was not going to be hungry any longer, so he decided to get some food in the house.

Karlsson's gaze immediately fell on n wooden cupboards, standing in the kitchen. He immediately realized that these cupboards have hidden jam stocks. Karlsson began to fly greedily around the kitchen, opening and closing the cupboards' doors, grab and empty all the jars of jam that he could find.

And now all jars of jam are empty, Karlsson has had enough and does not want to leave traces of his stay, so as not to let down his friend. Each of the cupboards has two doors: the left one and the right one. Karlsson remembers that when he rushed to the kitchen, all the cupboards' left doors were in the same position (open or closed), similarly, all the cupboards' right doors were in the same position (open or closed). Karlsson wants the doors to meet this condition as well by the time the family returns. Karlsson does not remember the position of all the left doors, also, he cannot remember the position of all the right doors. Therefore, it does not matter to him in what position will be all left or right doors. It is important to leave all the left doors in the same position, and all the right doors in the same position. For example, all the left doors may be closed, and all the right ones may be open.

Karlsson needs one second to open or close a door of a cupboard. He understands that he has very little time before the family returns, so he wants to know the minimum number of seconds t, in which he is able to bring all the cupboard doors in the required position.

Your task is to write a program that will determine the required number of seconds t.


-----Input-----

The first input line contains a single integer n — the number of cupboards in the kitchen (2 ≤ n ≤ 10^4). Then follow n lines, each containing two integers l_{i} and r_{i} (0 ≤ l_{i}, r_{i} ≤ 1). Number l_{i} equals one, if the left door of the i-th cupboard is opened, otherwise number l_{i} equals zero. Similarly, number r_{i} equals one, if the right door of the i-th cupboard is opened, otherwise number r_{i} equals zero.

The numbers in the lines are separated by single spaces.


-----Output-----

In the only output line print a single integer t — the minimum number of seconds Karlsson needs to change the doors of all cupboards to the position he needs.


-----Examples-----
Input
5
0 1
1 0
0 1
1 1
0 1

Output
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alex, Bob, and, Chef are standing on the coordinate plane. Chef is standing at the origin (coordinates (0, 0)) while the location of Alex and Bob are (X_{1}, Y_{1}) and (X_{2}, Y_{2}) respectively.

Amongst Alex and Bob, find out who is at a farther distance from Chef or determine if both are at the same distance from Chef.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains four space-separated integers X_{1}, Y_{1}, X_{2}, and Y_{2} — the coordinates of Alex and Bob.

------ Output Format ------ 

For each test case, output on a new line:
- ALEX, if Alex is at a farther distance from Chef.
- BOB, if Bob is at a farther distance from Chef.
- EQUAL, if both are standing at the same distance from Chef.

You may print each character in uppercase or lowercase. For example, Bob, BOB, bob, and bOB, are all considered identical.

------ Constraints ------ 

$1 ≤ T ≤ 2000$
$-1000 ≤ X_{1}, Y_{1}, X_{2}, Y_{2} ≤ 1000$

----- Sample Input 1 ------ 
3
-1 0 3 4
3 4 -4 -3
8 -6 0 5

----- Sample Output 1 ------ 
BOB
EQUAL
ALEX
----- explanation 1 ------ 
Test case $1$: Alex is at a distance $1$ from Chef while Bob is at distance $5$ from Chef. Thus, Bob is at a farther distance.

Test case $2$: Alex is at a distance $5$ from Chef and Bob is also at distance $5$ from Chef. Thus, both are at the same distance.

Test case $3$: Alex is at a distance $10$ from Chef while Bob is at distance $5$ from Chef. Thus, Alex is at a farther distance.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S consisting of only opening and closing curly brackets '{' and '}', find out the minimum number of reversals required to convert the string into a balanced expression.
A reversal means changing '{' to '}' or vice-versa.
Example 1:
Input:
S = "}{{}}{{{"
Output: 3
Explanation: One way to balance is:
"{{{}}{}}". There is no balanced sequence
that can be formed in lesser reversals.
Example 2:
Input: 
S = "{{}{{{}{{}}{{"
Output: -1
Explanation: There's no way we can balance
this sequence of braces.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countRev() which takes the string S as the input parameter and returns the minimum number of reversals required to balance the bracket sequence. If balancing is not possible, return -1. 
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ |S| ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day, little Vasya found himself in a maze consisting of (n + 1) rooms, numbered from 1 to (n + 1). Initially, Vasya is at the first room and to get out of the maze, he needs to get to the (n + 1)-th one.

The maze is organized as follows. Each room of the maze has two one-way portals. Let's consider room number i (1 ≤ i ≤ n), someone can use the first portal to move from it to room number (i + 1), also someone can use the second portal to move from it to room number p_{i}, where 1 ≤ p_{i} ≤ i.

In order not to get lost, Vasya decided to act as follows.   Each time Vasya enters some room, he paints a cross on its ceiling. Initially, Vasya paints a cross at the ceiling of room 1.  Let's assume that Vasya is in room i and has already painted a cross on its ceiling. Then, if the ceiling now contains an odd number of crosses, Vasya uses the second portal (it leads to room p_{i}), otherwise Vasya uses the first portal. 

Help Vasya determine the number of times he needs to use portals to get to room (n + 1) in the end.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^3) — the number of rooms. The second line contains n integers p_{i} (1 ≤ p_{i} ≤ i). Each p_{i} denotes the number of the room, that someone can reach, if he will use the second portal in the i-th room.


-----Output-----

Print a single number — the number of portal moves the boy needs to go out of the maze. As the number can be rather large, print it modulo 1000000007 (10^9 + 7).


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

Output
4

Input
4
1 1 2 3

Output
20

Input
5
1 1 1 1 1

Output
62

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has N friends. Chef promised that he would gift a pair of shoes (consisting of one left shoe and one right shoe) to each of his N friends. Chef was about to go to the marketplace to buy shoes, but he suddenly remembers that he already had M left shoes.

What is the minimum number of extra shoes that Chef will have to buy to ensure that he is able to gift a pair of shoes to each of his N friends?

For example, if N = 2, M = 4, then Chef already has 4 left shoes, so he must buy 2 extra right shoes to form 2 pairs of shoes.

Therefore Chef must buy at least 2 extra shoes to ensure that he is able to get N = 2 pairs of shoes.

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and M - the number of Chef's friends and the number of left shoes Chef has.

------ Output Format ------ 

For each test case, output the minimum number of extra shoes that Chef will have to buy to ensure that he is able to get N pairs of shoes.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$0 ≤ M ≤ 100$

----- Sample Input 1 ------ 
3
2 4
6 0
4 3

----- Sample Output 1 ------ 
2
12
5

----- explanation 1 ------ 
Test Case 1: Discussed in the problem statement

Test Case 2: Chef initially has no left shoes. He must buy $6$ more left shoes and $6$ more right shoes to form $6$ pairs of shoes.

Test Case 3: Chef initially has $3$ left shoes. He must buy $1$ more left shoe and $4$ more right shoes to form $4$ pairs of shoes.

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

Implement a function which finds the numbers less than `2`, and the indices of numbers greater than `1` in the given sequence, and returns them as a pair of sequences. 

Return a nested array or a tuple depending on the language:

* The first sequence being only the `1`s and `0`s from the original sequence. 
* The second sequence being the indexes of the elements greater than `1` in the original sequence.  

## Examples

```python
[ 0, 1, 2, 1, 5, 6, 2, 1, 1, 0 ] => ( [ 0, 1, 1, 1, 1, 0 ], [ 2, 4, 5, 6 ] )
```

Please upvote and enjoy!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ross, being divorced for three times(yeah, and he is just 30!) had nothing to do so Chandler told him to paint his apartment.
Consider the wall is made with labelled bricks 1, 2, 3,.... and so on. Now after choosing Red paint for Ross and Blue for Chandler, they started painting a wall, Ross said he will paint every Xth brick Red, i.e., for some X, he will paint X, 2X, 3X,... etc Red. Similarly Chandler said that he will paint every Yth brick Blue. For some Y, he will paint Y,2Y,3Y,...

After painting the wall they found that some of bricks were painted both Red and Blue. Now they are wondering How many bricks from Brick number A to Brick number B are colored with both colors.

Now it's you to help them telling the number of bricks painted with both colors.

Input

  First line T, number of test case then T lines, one test case per line.

  Each test case, Four integers space separated integers X,Y,A,B.

Output

  For each test case, print the described output in newline.

Constraints

 1 ≤ T ≤ 50

 1 ≤ X, Y ≤ 1000

 1 ≤ A ≤ B ≤ 2·(10^9)

SAMPLE INPUT
3
1 3 4 5
2 4 4 8
3 6 2 12

SAMPLE OUTPUT
0
2
2

Explanation

Case 1: for X=1, Ross will paint all bricks, Y=3, Chandler will paint 3,6,9.... hence none in range [4,5] will be painted by both.

Case 2:  X=2, Y=4, so 4th and 8th will be painted by both so output 2.

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