vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Gerald got a very curious hexagon for his birthday. The boy found out that all the angles of the hexagon are equal to $120^{\circ}$. Then he measured the length of its sides, and found that each of them is equal to an integer number of centimeters. There the properties of the hexagon ended and Gerald decided to draw on it.

He painted a few lines, parallel to the sides of the hexagon. The lines split the hexagon into regular triangles with sides of 1 centimeter. Now Gerald wonders how many triangles he has got. But there were so many of them that Gerald lost the track of his counting. Help the boy count the triangles.


-----Input-----

The first and the single line of the input contains 6 space-separated integers a_1, a_2, a_3, a_4, a_5 and a_6 (1 ≤ a_{i} ≤ 1000) — the lengths of the sides of the hexagons in centimeters in the clockwise order. It is guaranteed that the hexagon with the indicated properties and the exactly such sides exists.


-----Output-----

Print a single integer — the number of triangles with the sides of one 1 centimeter, into which the hexagon is split.


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

Output
6

Input
1 2 1 2 1 2

Output
13



-----Note-----

This is what Gerald's hexagon looks like in the first sample:

$\theta$

And that's what it looks like in the second sample:

$A$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence of integers $A_1, A_2, \ldots, A_N$. This sequence is circular ― for each valid $i$, the element $A_{i+1}$ follows after $A_i$, and the element $A_1$ follows after $A_N$.
You may insert any positive integers at any positions you choose in this sequence; let's denote the resulting sequence by $B$. This sequence is also circular. For each pair of its elements $B_s$ and $B_f$, let's denote the (non-circular) sequence created by starting at $B_s$ and moving from each element to the one that follows after it, until we reach $B_f$, by $B(s, f)$. This sequence includes the elements $B_s$ and $B_f$.
For each $K$ from $2$ to $N$ inclusive, find the smallest possible number of elements that need to be inserted into $A$ to form a sequence $B$ for which there is no subsequence $B(p, q)$ such that:
- The size of $B(p, q)$ is at least $K$.
- There is no pair of consecutive elements in $B(p, q)$ such that their GCD is equal to $1$.

-----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 $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing $N-1$ space-separated integers. For each $i$ ($1 \le i \le N-1$), the $i$-th of these integers should be the smallest number of inserted elements in a valid sequence $B$ for $K = i+1$.

-----Constraints-----
- $1 \le T \le 2,000$
- $2 \le N \le 10^5$
- $1 \le A_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^6$

-----Example Input-----
1
5
3 6 4 5 9

-----Example Output-----
3 1 1 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a new version of the famous Pinball game, one of the most important parts of the game field is a sequence of n bumpers. The bumpers are numbered with integers from 1 to n from left to right. There are two types of bumpers. They are denoted by the characters '<' and '>'. When the ball hits the bumper at position i it goes one position to the right (to the position i + 1) if the type of this bumper is '>', or one position to the left (to i - 1) if the type of the bumper at position i is '<'. If there is no such position, in other words if i - 1 < 1 or i + 1 > n, the ball falls from the game field.

Depending on the ball's starting position, the ball may eventually fall from the game field or it may stay there forever. You are given a string representing the bumpers' types. Calculate the number of positions such that the ball will eventually fall from the game field if it starts at that position.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the length of the sequence of bumpers. The second line contains the string, which consists of the characters '<' and '>'. The character at the i-th position of this string corresponds to the type of the i-th bumper.


-----Output-----

Print one integer — the number of positions in the sequence such that the ball will eventually fall from the game field if it starts at that position.


-----Examples-----
Input
4
<<><

Output
2
Input
5
>>>>>

Output
5
Input
4
>><<

Output
0


-----Note-----

In the first sample, the ball will fall from the field if starts at position 1 or position 2.

In the second sample, any starting position will result in the ball falling from the field.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nick likes strings very much, he likes to rotate them, sort them, rearrange characters within a string... Once he wrote a random string of characters a, b, c on a piece of paper and began to perform the following operations: 

  * to take two adjacent characters and replace the second character with the first one, 
  * to take two adjacent characters and replace the first character with the second one 



To understand these actions better, let's take a look at a string «abc». All of the following strings can be obtained by performing one of the described operations on «abc»: «bbc», «abb», «acc». Let's denote the frequency of a character for each of the characters a, b and c as the number of occurrences of this character in the string. For example, for string «abc»: |a| = 1, |b| = 1, |c| = 1, and for string «bbc»: |a| = 0, |b| = 2, |c| = 1. 

While performing the described operations, Nick sometimes got balanced strings. Let's say that a string is balanced, if the frequencies of each character differ by at most 1. That is  - 1 ≤ |a| - |b| ≤ 1,  - 1 ≤ |a| - |c| ≤ 1 и  - 1 ≤ |b| - |c| ≤ 1. 

Would you help Nick find the number of different balanced strings that can be obtained by performing the operations described above, perhaps multiple times, on the given string s. This number should be calculated modulo 51123987.

Input

The first line contains integer n (1 ≤ n ≤ 150) — the length of the given string s. Next line contains the given string s. The initial string can be balanced as well, in this case it should be counted too. The given string s consists only of characters a, b and c.

Output

Output the only number — the number of different balanced strings that can be obtained by performing the described operations, perhaps multiple times, on the given string s, modulo 51123987.

Examples

Input

4
abca


Output

7


Input

4
abbc


Output

3


Input

2
ab


Output

1

Note

In the first sample it is possible to get 51 different strings through the described operations, but only 7 of them are balanced: «abca», «bbca», «bcca», «bcaa», «abcc», «abbc», «aabc». In the second sample: «abbc», «aabc», «abcc». In the third sample there is only one balanced string — «ab» itself.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
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 Specification:
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 Specification:
Print an integer denoting the maximum number of the mushrooms Ralph can collect during his route.

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

Demo Output:
['16', '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.
Given a string s. You should re-order the string using the following algorithm:

Pick the smallest character from s and append it to the result.
Pick the smallest character from s which is greater than the last appended character to the result and append it.
Repeat step 2 until you cannot pick more characters.
Pick the largest character from s and append it to the result.
Pick the largest character from s which is smaller than the last appended character to the result and append it.
Repeat step 5 until you cannot pick more characters.
Repeat the steps from 1 to 6 until you pick all characters from s.

In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.
Return the result string after sorting s with this algorithm.
 
Example 1:
Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"
Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"
After steps 4, 5 and 6 of the first iteration, result = "abccba"
First iteration is done. Now s = "aabbcc" and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"
After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"

Example 2:
Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

Example 3:
Input: s = "leetcode"
Output: "cdelotee"

Example 4:
Input: s = "ggggggg"
Output: "ggggggg"

Example 5:
Input: s = "spo"
Output: "ops"

 
Constraints:

1 <= s.length <= 500
s contains only lower-case English letters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today everyone is talking about big data. As a renowned data provider in the area, you now have $N$ precious pieces of data. You want to sell all $N$ pieces of data to $N$ customers. You can sell multiple pieces of data (including all and none) to a single customer. However, each piece of data must be sold to exactly one customer (you cannot split a single piece of data and sell it to multiple customers).

In your previous transactions you simply sold bigger data for higher prices. Unfortunately, that did not work quite well and your customers were a bit unsatisfied about the value of the data they got. Obviously, the value of data is not necessarily positively correlated with its volume.

This time you decide to do something different. After many meetings you finally sign a new contract with your customers. You number the $N$ pieces of data from $1$ to $N$ and figure out that the $i^\textrm {th}$ piece of data has a special property $S_ i$. The new contract specifies that each customer shall pay you an amount of money that is equal to the number of distinct prime factors in the sum of $S_ i$’s of the data pieces sold to him/her.

Based on the new contract, what is the maximum revenue you can achieve by selling all $N$ pieces of data?

-----Input-----
The first line has a single integer $N$ ($1 \leq N \leq 14$). The second line has $N$ positive integers, $S_1, S_2, \ldots , S_ N$. These integers are no larger than $1000$.

-----Output-----
Output the maximum revenue you can achieve by selling all $N$ pieces of data.

-----Examples-----
Sample Input 1:
1
1
Sample Output 1:
0

Sample Input 2:
3
4 7 8
Sample Output 2:
3

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in [Hindi], [Mandarin Chinese],  [Vietnamese], and [Bengali] as well.

A semester in Chef's University has $120$ working days. The University's requirement is that a student should be present for at least $75\%$ of the working days in the semester. If not, the student is failed.

Chef has been taking a lot of holidays, and is now concerned whether he can pass the attendance requirement or not. $N$ working days have already passed, and you are given $N$ bits - $B_{1}$, $B_{2}$, ..., $B_{N}$. $B_{i}$ = $0$ denotes that Chef was absent on the $i^{th}$ day, and $B_{i}$ = $1$ denotes that Chef was present on that day.

Can Chef hope to pass the requirement by the end of the semester?

------ Input: ------

First line will contain $T$, the number of testcases. Then the testcases follow. 
Each testcase contains two lines of input.
The first line of each testcase contains a single integer, $N$, the number of days till now.
The second line of each testcase contains a string $B$ of length $N$ where $B_{i}$ represents the status of the $i^{th}$ day.

------ Output: ------
For each testcase, output the answer in a single line - "YES" if Chef can pass the attendance requirement and "NO" if not.

------ Constraints  ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 120$
$0 ≤ B_{i} ≤ 1$

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

50

00000000000000000000000000000000000000000000000000

50

01010101010101010101010101010101010101010101010101

2

01
----- Sample Output 1 ------ 
NO

YES

YES
----- explanation 1 ------ 
For Case 1, even if Chef attends all the remaining 70 days, he'll only have an attendance percentage of $70/120$ = $58.33\%$ which is less than $75\%$.

For Case 2, maximum attendance possible is $79.167\%$ which is more than $75\%$.

For Case 3, maximum attendance possible is $99.167\%$ which is more than $75\%$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that returns the number of '2's in the factorization of a number.  
For example,
```python
two_count(24)
```
should return 3, since the factorization of 24 is 2^3 x 3
```python
two_count(17280)
```
should return 7, since the factorization of 17280 is 2^7 x 5 x 3^3  
The number passed to two_count (twoCount)  will always be a positive integer greater than or equal to 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.


Example:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"



Restrictions: 

 The string consists of lower English letters only.
 Length of the given string and k will in the range [1, 10000]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Number of Ways

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got array *a*[1],<=*a*[2],<=...,<=*a*[*n*], consisting of *n* integers. Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same. 

More formally, you need to find the number of such pairs of indices *i*,<=*j* (2<=≤<=*i*<=≤<=*j*<=≤<=*n*<=-<=1), that .

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=5·105), showing how many numbers are in the array. The second line contains *n* integers *a*[1], *a*[2], ..., *a*[*n*] (|*a*[*i*]|<=≤<=<=109) — the elements of array *a*.

Output Specification:
Print a single integer — the number of ways to split the array into three parts with the same sum.

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

Demo Output:
['2\n', '1\n', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem is given in two editions, which differ exclusively in the constraints on the number $n$.

You are given an array of integers $a[1], a[2], \dots, a[n].$ A block is a sequence of contiguous (consecutive) elements $a[l], a[l+1], \dots, a[r]$ ($1 \le l \le r \le n$). Thus, a block is defined by a pair of indices $(l, r)$.

Find a set of blocks $(l_1, r_1), (l_2, r_2), \dots, (l_k, r_k)$ such that:

  They do not intersect (i.e. they are disjoint). Formally, for each pair of blocks $(l_i, r_i)$ and $(l_j, r_j$) where $i \neq j$ either $r_i < l_j$ or $r_j < l_i$.  For each block the sum of its elements is the same. Formally, $$a[l_1]+a[l_1+1]+\dots+a[r_1]=a[l_2]+a[l_2+1]+\dots+a[r_2]=$$ $$\dots =$$ $$a[l_k]+a[l_k+1]+\dots+a[r_k].$$  The number of the blocks in the set is maximum. Formally, there does not exist a set of blocks $(l_1', r_1'), (l_2', r_2'), \dots, (l_{k'}', r_{k'}')$ satisfying the above two requirements with $k' > k$. 

 $\left. \begin{array}{|l|l|l|l|l|l|} \hline 4 & {1} & {2} & {2} & {1} & {5} & {3} \\ \hline \end{array} \right.$ The picture corresponds to the first example. Blue boxes illustrate blocks. 

Write a program to find such a set of blocks.


-----Input-----

The first line contains integer $n$ ($1 \le n \le 50$) — the length of the given array. The second line contains the sequence of elements $a[1], a[2], \dots, a[n]$ ($-10^5 \le a_i \le 10^5$).


-----Output-----

In the first line print the integer $k$ ($1 \le k \le n$). The following $k$ lines should contain blocks, one per line. In each line print a pair of indices $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — the bounds of the $i$-th block. You can print blocks in any order. If there are multiple answers, print any of them.


-----Examples-----
Input
7
4 1 2 2 1 5 3

Output
3
7 7
2 3
4 5

Input
11
-5 -4 -3 -2 -1 0 1 2 3 4 5

Output
2
3 4
1 1

Input
4
1 1 1 1

Output
4
4 4
1 1
2 2
3 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Spider's Web

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Paw the Spider is making a web. Web-making is a real art, Paw has been learning to do it his whole life. Let's consider the structure of the web.

There are *n* main threads going from the center of the web. All main threads are located in one plane and divide it into *n* equal infinite sectors. The sectors are indexed from 1 to *n* in the clockwise direction. Sectors *i* and *i*<=+<=1 are adjacent for every *i*, 1<=≤<=*i*<=&lt;<=*n*. In addition, sectors 1 and *n* are also adjacent.

Some sectors have bridge threads. Each bridge connects the two main threads that make up this sector. The points at which the bridge is attached to the main threads will be called attachment points. Both attachment points of a bridge are at the same distance from the center of the web. At each attachment point exactly one bridge is attached. The bridges are adjacent if they are in the same sector, and there are no other bridges between them.

A cell of the web is a trapezoid, which is located in one of the sectors and is bounded by two main threads and two adjacent bridges. You can see that the sides of the cell may have the attachment points of bridges from adjacent sectors. If the number of attachment points on one side of the cell is not equal to the number of attachment points on the other side, it creates an imbalance of pulling forces on this cell and this may eventually destroy the entire web. We'll call such a cell unstable. The perfect web does not contain unstable cells.

Unstable cells are marked red in the figure. Stable cells are marked green.

Paw the Spider isn't a skillful webmaker yet, he is only learning to make perfect webs. Help Paw to determine the number of unstable cells in the web he has just spun.

Input Specification:
The first line contains integer *n* (3<=≤<=*n*<=≤<=1000) — the number of main threads.

The *i*-th of following *n* lines describe the bridges located in the *i*-th sector: first it contains integer *k**i* (1<=≤<=*k**i*<=≤<=105) equal to the number of bridges in the given sector. Then follow *k**i* different integers *p**ij* (1<=≤<=*p**ij*<=≤<=105; 1<=≤<=*j*<=≤<=*k**i*). Number *p**ij* equals the distance from the attachment points of the *j*-th bridge of the *i*-th sector to the center of the web.

It is guaranteed that any two bridges between adjacent sectors are attached at a different distance from the center of the web. It is guaranteed that the total number of the bridges doesn't exceed 105.

Output Specification:
Print a single integer — the number of unstable cells in Paw the Spider's web.

Demo Input:
['7\n3 1 6 7\n4 3 5 2 9\n2 8 1\n4 3 7 6 4\n3 2 5 9\n3 6 3 8\n3 4 2 9\n']

Demo Output:
['6']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every true king during his life must conquer the world, hold the Codeforces world finals, win pink panda in the shooting gallery and travel all over his kingdom.

King Copa has already done the first three things. Now he just needs to travel all over the kingdom. The kingdom is an infinite plane with Cartesian coordinate system on it. Every city is a point on this plane. There are n cities in the kingdom at points with coordinates (x1, 0), (x2, 0), ..., (xn, 0), and there is one city at point (xn + 1, yn + 1). 

King starts his journey in the city number k. Your task is to find such route for the king, which visits all cities (in any order) and has minimum possible length. It is allowed to visit a city twice. The king can end his journey in any city. Between any pair of cities there is a direct road with length equal to the distance between the corresponding points. No two cities may be located at the same point.

Input

The first line contains two integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ n + 1) — amount of cities and index of the starting city. The second line contains n + 1 numbers xi. The third line contains yn + 1. All coordinates are integers and do not exceed 106 by absolute value. No two cities coincide.

Output

Output the minimum possible length of the journey. Your answer must have relative or absolute error less than 10 - 6.

Examples

Input

3 1
0 1 2 1
1


Output

3.41421356237309490000

Input

3 1
1 0 2 1
1


Output

3.82842712474619030000

Input

4 5
0 5 -1 -5 2
3


Output

14.24264068711928400000

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