vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There is a grid with H rows and W columns, where each square is painted black or white.

You are given H strings S_1, S_2, ..., S_H, each of length W. If the square at the i-th row from the top and the j-th column from the left is painted black, the j-th character in the string S_i is `#`; if that square is painted white, the j-th character in the string S_i is `.`.

Find the number of pairs of a black square c_1 and a white square c_2 that satisfy the following condition:

* There is a path from the square c_1 to the square c_2 where we repeatedly move to a vertically or horizontally adjacent square through an alternating sequence of black and white squares: black, white, black, white...

Constraints

* 1 \leq H, W \leq 400
* |S_i| = W (1 \leq i \leq H)
* For each i (1 \leq i \leq H), the string S_i consists of characters `#` and `.`.

Input

Input is given from Standard Input in the following format:


H W
S_1
S_2
:
S_H


Output

Print the answer.

Examples

Input

3 3
.#.
..#
#..


Output

10


Input

3 3
.#.
..#
..


Output

10


Input

2 4
....
....


Output

0


Input

4 3


...


Output

6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given N points on an infinite plane with the Cartesian coordinate system on it. N-1 points lay on one line, and one point isn't on that line. You are on point K at the start, and the goal is to visit every point. You can move between any two points in a straight line, and you can revisit points. What is the minimum length of the path? 

Input

The first line contains two integers: N (3 ≤ N ≤ 2*10^5) - the number of points, and K (1 ≤ K ≤ N) - the index of the starting point.

Each of the next N lines contain two integers, A_i, B_i (-10^6 ≤ A_i, B_i ≤ 10^6) - coordinates of the i-th point.

Output

The output contains one number - the shortest path to visit all given points starting from point K. The absolute difference between your solution and the main solution shouldn't exceed 10^-6;

Example

Input


5 2
0 0
-1 1
2 -2
0 1
-2 2


Output


7.478709

Note

The shortest path consists of these moves: 

2 -> 5 

5 -> 4 

4 -> 1 

1 -> 3 

There isn't any shorter path possible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The far away land of Edinbrugh is going to war with the land of eternal darkness, Darkalvennia. King James the III, the king of Edinbrugh calls upon his war council to formulate the battle plan. The war counil comprises of, apart from the king, his 10 army chiefs numbered from chief0 to chief9. The king also has a standing army of N soldiers and each soldier has a number assigned to him/her starting from 1 to N.      

Now, the army chiefs being a bit eccentric, only like certain soldiers, for example, Chief0 only likes soldiers with 0 in their number, Chief1 likes soldiers with 1 in their number and so on.    

A few days ago, King James III received a mysterious letter saying that there might be a spy within his army chiefs, so the king decides that he'll only send some of his army chiefs to war.   

Given the size of King James the III's army, N, and the chiefs he selects to go to war, your task is to determine the size of the army that'll go to war against Darkalvennia.  

Input:
First line of input contains an integer N, number of soldiers. Next line contains an integer Q, number of queries. Each query first line contains an integer M that is number of chief selected by Kings James. Second line of query contains M space separated integers represents chief of the army.  

Constraints:
1 ≤ N ≤ 100000
1 ≤ Q ≤ 1500
1 ≤ M ≤ 10  

SAMPLE INPUT
20
3
2
1 2
2
1 9
2
2 3

SAMPLE OUTPUT
13
12
5

Explanation

Number of  Soldiers = 20
Query #1:  
Chief selected by King James are : Chief1 and Chief2  
Chief1 will select soldiers having number : 1, 10, 11 ,12, 13, 14, 15, 16, 17, 18, 19 
Chief2 will select soldiers having number : 2, 12, 20   

Total size of the army will be 13 not 14 because 12 will be count only once not twice.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ms. E.T. came from planet Hex. She has 8 fingers in each hand which makes her count in hexadecimal way. When she meets you, she tells you that she came from 7E light years from the planet Earth. You see she means that it is 126 light years far away and she is telling you the numbers in hexadecimal. Now, you are in trouble to understand what those numbers really mean. Therefore, you have to convert the hexadecimal numbers to decimals.

Input:

First line of code contain T test cases.

every line of text case contain a Hex-value 

Output:

Every line of output contain a decimal conversion of given nunmber

Sample Input:

3

A

1A23

2C2A

Sample Output:

10

6691

11306

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Watching a movie

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have decided to watch the best moments of some movie. There are two buttons on your player: 
 1.  Watch the current minute of the movie. By pressing this button, you watch the current minute of the movie and the player automatically proceeds to the next minute of the movie. 1.  Skip exactly *x* minutes of the movie (*x* is some fixed positive integer). If the player is now at the *t*-th minute of the movie, then as a result of pressing this button, it proceeds to the minute (*t*<=+<=*x*). 
Initially the movie is turned on in the player on the first minute, and you want to watch exactly *n* best moments of the movie, the *i*-th best moment starts at the *l**i*-th minute and ends at the *r**i*-th minute (more formally, the *i*-th best moment consists of minutes: *l**i*,<=*l**i*<=+<=1,<=...,<=*r**i*). 

Determine, what is the minimum number of minutes of the movie you have to watch if you want to watch all the best moments?

Input Specification:
The first line contains two space-separated integers *n*, *x* (1<=≤<=*n*<=≤<=50, 1<=≤<=*x*<=≤<=105) — the number of the best moments of the movie and the value of *x* for the second button.

The following *n* lines contain the descriptions of the best moments of the movie, the *i*-th line of the description contains two integers separated by a space *l**i*, *r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=105).

It is guaranteed that for all integers *i* from 2 to *n* the following condition holds: *r**i*<=-<=1<=&lt;<=*l**i*.

Output Specification:
Output a single number — the answer to the problem.

Demo Input:
['2 3\n5 6\n10 12\n', '1 1\n1 100000\n']

Demo Output:
['6\n', '100000\n']

Note:
In the first sample, the player was initially standing on the first minute. As the minutes from the 1-st to the 4-th one don't contain interesting moments, we press the second button. Now we can not press the second button and skip 3 more minutes, because some of them contain interesting moments. Therefore, we watch the movie from the 4-th to the 6-th minute, after that the current time is 7. Similarly, we again skip 3 minutes and then watch from the 10-th to the 12-th minute of the movie. In total, we watch 6 minutes of the movie.

In the second sample, the movie is very interesting, so you'll have to watch all 100000 minutes of the movie.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
**Steps**
1. Square the numbers that are greater than zero.
2. Multiply by 3 every third number.
3. Multiply by -1 every fifth number.
4. Return the sum of the sequence.

**Example**   
`{ -2, -1, 0, 1, 2 }` returns `-6`
```
1. { -2, -1, 0, 1 * 1, 2 * 2 }
2. { -2, -1, 0 * 3, 1, 4 }
3. { -2, -1, 0, 1, -1 * 4 }
4. -6
```

P.S.: The sequence consists only of integers. And try not to use "for", "while" or "loop" statements.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Is there anything better than going to the zoo after a tiresome week at work? No wonder Grisha feels the same while spending the entire weekend accompanied by pretty striped zebras. 

Inspired by this adventure and an accidentally found plasticine pack (represented as a sequence of black and white stripes), Grisha now wants to select several consequent (contiguous) pieces of alternating colors to create a zebra. Let's call the number of selected pieces the length of the zebra.

Before assembling the zebra Grisha can make the following operation $0$ or more times. He splits the sequence in some place into two parts, then reverses each of them and sticks them together again. For example, if Grisha has pieces in the order "bwbbw" (here 'b' denotes a black strip, and 'w' denotes a white strip), then he can split the sequence as bw|bbw (here the vertical bar represents the cut), reverse both parts and obtain "wbwbb".

Determine the maximum possible length of the zebra that Grisha can produce.


-----Input-----

The only line contains a string $s$ ($1 \le |s| \le 10^5$, where $|s|$ denotes the length of the string $s$) comprised of lowercase English letters 'b' and 'w' only, where 'w' denotes a white piece and 'b' denotes a black piece.


-----Output-----

Print a single integer — the maximum possible zebra length.


-----Examples-----
Input
bwwwbwwbw

Output
5

Input
bwwbwwb

Output
3



-----Note-----

In the first example one of the possible sequence of operations is bwwwbww|bw $\to$ w|wbwwwbwb $\to$ wbwbwwwbw, that gives the answer equal to $5$.

In the second example no operation can increase the answer.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Today Vasya visited a widely known site and learned that the continuation of his favourite game Codecraft II will appear after exactly *k* months. He looked at the calendar and learned that at the moment is the month number *s*. Vasya immediately got interested in what month Codecraft III will appear. Help him understand that.

All the twelve months in Vasya's calendar are named using their usual English names: January, February, March, April, May, June, July, August, September, October, November, December.

Input Specification:
The first input line contains the name of the current month. It is guaranteed that it is a proper English name of one of twelve months. The first letter is uppercase, the rest are lowercase. The second line contains integer *k* (0<=≤<=*k*<=≤<=100) — the number of months left till the appearance of Codecraft III.

Output Specification:
Print starting from an uppercase letter the name of the month in which the continuation of Codeforces II will appear. The printed name must be contained in the list January, February, March, April, May, June, July, August, September, October, November, December.

Demo Input:
['November\n3\n', 'May\n24\n']

Demo Output:
['February\n', 'May\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Pair Of Lines

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given *n* points on Cartesian plane. Every point is a lattice point (i.<=e. both of its coordinates are integers), and all points are distinct.

You may draw two straight lines (not necessarily distinct). Is it possible to do this in such a way that every point lies on at least one of these lines?

Input Specification:
The first line contains one integer *n* (1<=≤<=*n*<=≤<=105) — the number of points you are given.

Then *n* lines follow, each line containing two integers *x**i* and *y**i* (|*x**i*|,<=|*y**i*|<=≤<=109)— coordinates of *i*-th point. All *n* points are distinct.

Output Specification:
If it is possible to draw two straight lines in such a way that each of given points belongs to at least one of these lines, print YES. Otherwise, print NO.

Demo Input:
['5\n0 0\n0 1\n1 1\n1 -1\n2 2\n', '5\n0 0\n1 0\n2 1\n1 1\n2 3\n']

Demo Output:
['YES\n', 'NO\n']

Note:
In the first example it is possible to draw two lines, the one containing the points 1, 3 and 5, and another one containing two remaining points.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vivek was quite bored with the lockdown, so he came up with an interesting task. He successfully completed this task and now, he would like you to solve it.
You are given two strings $A$ and $B$, each with length $N$. Let's index the characters in each string from $0$ ― for each $i$ ($0 \le i < N$), the $i+1$-th characters of $A$ and $B$ are denoted by $A_i$ and $B_i$ respectively. You should convert $A$ to $B$ by performing operations of the following type:
- Choose a subset $S$ of the set $\{0, 1, \ldots, N-1\}$.
- Let $c$ be the alphabetically smallest character among $A_x$ for all $x \in S$.
- For each $x \in S$, replace $A_x$ by $c$.
You should find the smallest necessary number of operations or report that it is impossible to convert $A$ to $B$. If it is possible, you also need to find one way to convert $A$ to $B$ using this smallest number of operations. If there are multiple solutions, you may find any one.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains a single string $A$.
- The third line contains a single string $B$.

-----Output-----
For each test case:
- If it is impossible to convert $A$ to $B$, print a single line containing the integer $-1$.
- Otherwise, first, print a line containing a single integer $K$ ― the minimum number of operations.
- Then, print $K$ lines describing the operations. Each of these lines should contain a positive integer $Z$, followed by a space and $Z$ pairwise distinct space-separated integers from the set $\{0, 1, \ldots, N-1\}$ ― the elements of $S$.

-----Constraints-----
- $1 \le T \le 20$
- $1 \le N \le 10^3$
- $|A| = |B| = N$
- $A$ and $B$ contain only lowercase English letters

-----Subtasks-----
Subtask #1 (30 points): $B$ contains only characters 'a' and 'b'
Subtask #2 (70 points): original constraints

-----Example Input-----
3
5
abcab
aabab
3
aaa
aab
2
de
cd

-----Example Output-----
2
3 1 2 4
3 0 1 3
-1
-1

-----Explanation-----
Example case 1:
- First, we can choose $S = (1, 2, 4)$, so the character $c$ is 'b' and the string $A$ after this operation is "abbab".
- Then, we choose $S = (0, 1, 3)$, so $c$ is 'a', and $A$ becomes "aabab".
- There is no way to convert $A$ to $B$ in only one operation.
Example case 2: We can see that it is impossible to convert $A$ to $B$ since $c$ is always 'a'.
Example case 3: We can see again that it is impossible to convert $A$ to $B$ since $c$ cannot be 'c'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monocarp has decided to buy a new TV set and hang it on the wall in his flat. The wall has enough free space so Monocarp can buy a TV set with screen width not greater than $a$ and screen height not greater than $b$. Monocarp is also used to TV sets with a certain aspect ratio: formally, if the width of the screen is $w$, and the height of the screen is $h$, then the following condition should be met: $\frac{w}{h} = \frac{x}{y}$.

There are many different TV sets in the shop. Monocarp is sure that for any pair of positive integers $w$ and $h$ there is a TV set with screen width $w$ and height $h$ in the shop.

Monocarp isn't ready to choose the exact TV set he is going to buy. Firstly he wants to determine the optimal screen resolution. He has decided to try all possible variants of screen size. But he must count the number of pairs of positive integers $w$ and $h$, beforehand, such that $(w \le a)$, $(h \le b)$ and $(\frac{w}{h} = \frac{x}{y})$.

In other words, Monocarp wants to determine the number of TV sets having aspect ratio $\frac{x}{y}$, screen width not exceeding $a$, and screen height not exceeding $b$. Two TV sets are considered different if they have different screen width or different screen height.


-----Input-----

The first line contains four integers $a$, $b$, $x$, $y$ ($1 \le a, b, x, y \le 10^{18}$) — the constraints on the screen width and height, and on the aspect ratio.


-----Output-----

Print one integer — the number of different variants to choose TV screen width and screen height so that they meet the aforementioned constraints.


-----Examples-----
Input
17 15 5 3

Output
3

Input
14 16 7 22

Output
0

Input
4 2 6 4

Output
1

Input
1000000000000000000 1000000000000000000 999999866000004473 999999822000007597

Output
1000000063



-----Note-----

In the first example, there are $3$ possible variants: $(5, 3)$, $(10, 6)$, $(15, 9)$.

In the second example, there is no TV set meeting the constraints.

In the third example, there is only one variant: $(3, 2)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a hard version of the problem. The actual problems are different, but the easy version is almost a subtask of the hard version. Note that the constraints and the output format are different.

You are given a string $s$ consisting of $n$ lowercase Latin letters.

You have to color all its characters the minimum number of colors (each character to exactly one color, the same letters can be colored the same or different colors, i.e. you can choose exactly one color for each index in $s$).

After coloring, you can swap any two neighboring characters of the string that are colored different colors. You can perform such an operation arbitrary (possibly, zero) number of times.

The goal is to make the string sorted, i.e. all characters should be in alphabetical order.

Your task is to find the minimum number of colors which you have to color the given string in so that after coloring it can become sorted by some sequence of swaps. Note that you have to restore only coloring, not the sequence of swaps.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $s$.

The second line of the input contains the string $s$ consisting of exactly $n$ lowercase Latin letters.


-----Output-----

In the first line print one integer $res$ ($1 \le res \le n$) — the minimum number of colors in which you have to color the given string so that after coloring it can become sorted by some sequence of swaps.

In the second line print any possible coloring that can be used to sort the string using some sequence of swaps described in the problem statement. The coloring is the array $c$ of length $n$, where $1 \le c_i \le res$ and $c_i$ means the color of the $i$-th character.


-----Examples-----
Input
9
abacbecfd

Output
2
1 1 2 1 2 1 2 1 2 

Input
8
aaabbcbb

Output
2
1 2 1 2 1 2 1 1

Input
7
abcdedc

Output
3
1 1 1 1 1 2 3 

Input
5
abcde

Output
1
1 1 1 1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The two renowned houses of the Seven Kingdoms - The Starks & The Lannisters have a rather dull relationship. "The Lannisters always pays their debts" - says Tywin, the Head of the Lannisters, while the Starks, under the leadership of Jon Snow, are looking for a revenge of the Red Wedding. They both hate each other a lot, and so they decided to play a game to decide who will sit on the Iron Throne.

There are N objects in the kingdom (initially all are cuboids). Each object has different dimensions (Ai, Bi, Ci) and can be realized as composed of smaller identical unit cubes. There is an Iron Throne replica on (Ai, Bi, Ci) of each object initially (See image below). The game is played in turns. The Starks, known for their nobility always play first. In each turn, the concerned House does the following:

He takes one of the objects in the game and places it in the corner of a room.

He pushes (or compresses) the object in one of the direction of the axes, X, Y or Z (see sample test case image). So if the object he selected has its current dimensions as (p, q, r), then he can select X axis if p > 0, Y axis if q > 0 and Z axis if r > 0. Once he has decided the direction , he chooses a number s > 0 and pushes that dimension s units. So for example if he had chosen the X axis, whose value is p, then he can choose any number s (0 < s ≤ p), and make p = p - s for that direction

If the object becomes a point mass, i.e. it has come to state (A, B, C) = (0, 0, 0), then it is thrown out of the game.

The House that cannot make a move loses the game( and also the Iron Throne). Given N and the dimension of each object initially, you need to predict the winner.

Input & Output:

The first line contains the number of test cases T. Description of the T test cases follow. The first line of every test case contains N, the number of objects. The next N lines contains A B C the dimensions of each object initially.

For each test case you need to print the winner of the game, "Stark" or "Lannister". (quotes for clarity)

Constraints:
1 ≤ T ≤ 125000
1 ≤ N ≤ 20
1 ≤ Ai, Bi, Ci ≤ 50  SAMPLE INPUT
2
1
2 2 2
2
2 2 2
2 2 2

SAMPLE OUTPUT
Stark
Lannister

Explanation

1) The first test case is shown in the image. Note that there could be more ways of winning.

2) In second test case, for every move of Stark, the Lannister can always repeat that same move in the other cuboid. Hence they always have a valid move

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your friend won't stop texting his girlfriend.  It's all he does. All day. Seriously.  The texts are so mushy too! The whole situation just makes you feel ill.
Being the wonderful friend that you are, you hatch an evil plot.  While he's sleeping, you take his phone and change the autocorrect options so that every time he types "you" or "u" it gets changed to "your sister."

Write a function called autocorrect that takes a string and replaces all instances of "you" or "u" (not case sensitive) with "your sister" (always lower case).

Return the resulting string.

Here's the slightly tricky part: These are text messages, so there are different forms of "you" and "u".

For the purposes of this kata, here's what you need to support:

"youuuuu" with any number of u characters tacked onto the end
"u" at the beginning, middle, or end of a string, but NOT part of a word
"you" but NOT as part of another word like youtube or bayou

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
 
Example 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:
Input: s = ""
Output: 0

 
Constraints:

0 <= s.length <= 3 * 104
s[i] is '(', or ')'.

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