vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
DZY loves chemistry, and he enjoys mixing chemicals.

DZY has n chemicals, and m pairs of them will react. He wants to pour these chemicals into a test tube, and he needs to pour them in one by one, in any order. 

Let's consider the danger of a test tube. Danger of an empty test tube is 1. And every time when DZY pours a chemical, if there are already one or more chemicals in the test tube that can react with it, the danger of the test tube will be multiplied by 2. Otherwise the danger remains as it is.

Find the maximum possible danger after pouring all the chemicals one by one in optimal order.


-----Input-----

The first line contains two space-separated integers n and m $(1 \leq n \leq 50 ; 0 \leq m \leq \frac{n(n - 1)}{2})$.

Each of the next m lines contains two space-separated integers x_{i} and y_{i} (1 ≤ x_{i} < y_{i} ≤ n). These integers mean that the chemical x_{i} will react with the chemical y_{i}. Each pair of chemicals will appear at most once in the input.

Consider all the chemicals numbered from 1 to n in some order.


-----Output-----

Print a single integer — the maximum possible danger.


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

Output
1

Input
2 1
1 2

Output
2

Input
3 2
1 2
2 3

Output
4



-----Note-----

In the first sample, there's only one way to pour, and the danger won't increase.

In the second sample, no matter we pour the 1st chemical first, or pour the 2nd chemical first, the answer is always 2.

In the third sample, there are four ways to achieve the maximum possible danger: 2-1-3, 2-3-1, 1-2-3 and 3-2-1 (that is the numbers of the chemicals in order of pouring).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bharat was given a problem to solve, by his brother, Lord Ram. The problem was like, given integers, $N$ and $K$, Bharat has to find the number (possibilities) of non-increasing arrays of length $K$, where each element of the array is between $1$ and $N$ (both inclusive). He was confused, regarding this problem. So, help him solve the problem, so that, he can give the answer of the problem, to his brother, Lord Rama. Since, the number of possible sub-arrays can be large, Bharat has to answer the problem as "number of possible non-increasing arrays", modulo  $10^9$ $+$ $7$.

-----Input:-----
- Two space-seperated integers, $N$ and $K$.

-----Output:-----
- Output in a single line, the number of possible non-increasing arrays, modulo $10^9$ $+$ $7$.

-----Constraints:-----
- $1 \leq N, K \leq 2000$

-----Sample Input:-----
2 5

-----Sample Output:-----
6

-----Explanation:-----
- Possible Arrays, for the "Sample Case" are as follows: 
- {1, 1, 1, 1, 1}
- {2, 1, 1, 1, 1}
- {2, 2, 1, 1, 1} 
- {2, 2, 2, 1, 1}
- {2, 2, 2, 2, 1}
- {2, 2, 2, 2, 2}
- Hence, the answer to the "Sample Case" is $6$ ($6$ % ($10^9$ $+$ $7$)).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a permutation $p$ of integers from $1$ to $n$, where $n$ is an even number. 

Your goal is to sort the permutation. To do so, you can perform zero or more operations of the following type:   take two indices $i$ and $j$ such that $2 \cdot |i - j| \geq n$ and swap $p_i$ and $p_j$. 

There is no need to minimize the number of operations, however you should use no more than $5 \cdot n$ operations. One can show that it is always possible to do that.


-----Input-----

The first line contains a single integer $n$ ($2 \leq n \leq 3 \cdot 10^5$, $n$ is even) — the length of the permutation. 

The second line contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the given permutation.


-----Output-----

On the first line print $m$ ($0 \le m \le 5 \cdot n$) — the number of swaps to perform.

Each of the following $m$ lines should contain integers $a_i, b_i$ ($1 \le a_i, b_i \le n$, $|a_i - b_i| \ge \frac{n}{2}$) — the indices that should be swapped in the corresponding swap.

Note that there is no need to minimize the number of operations. We can show that an answer always exists.


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

Output
1
1 2
Input
4
3 4 1 2

Output
4
1 4
1 4
1 3
2 4

Input
6
2 5 3 1 4 6

Output
3
1 5
2 5
1 4



-----Note-----

In the first example, when one swap elements on positions $1$ and $2$, the array becomes sorted.

In the second example, pay attention that there is no need to minimize number of swaps.

In the third example, after swapping elements on positions $1$ and $5$ the array becomes: $[4, 5, 3, 1, 2, 6]$. After swapping elements on positions $2$ and $5$ the array becomes $[4, 2, 3, 1, 5, 6]$ and finally after swapping elements on positions $1$ and $4$ the array becomes sorted: $[1, 2, 3, 4, 5, 6]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N students in a school.
We will divide these students into some groups, and in each group they will discuss some themes.
You think that groups consisting of two or less students cannot have an effective discussion, so you want to have as many groups consisting of three or more students as possible.
Divide the students so that the number of groups consisting of three or more students is maximized.

-----Constraints-----
 - 1 \leq N \leq 1000
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N

-----Output-----
If you can form at most x groups consisting of three or more students, print x.

-----Sample Input-----
8

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

For example, you can form a group of three students and another of five students.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The bear has a string s = s1s2... s|s| (record |s| is the string's length), consisting of lowercase English letters. The bear wants to count the number of such pairs of indices i, j (1 ≤ i ≤ j ≤ |s|), that string x(i, j) = sisi + 1... sj contains at least one string "bear" as a substring.

String x(i, j) contains string "bear", if there is such index k (i ≤ k ≤ j - 3), that sk = b, sk + 1 = e, sk + 2 = a, sk + 3 = r.

Help the bear cope with the given problem.

Input

The first line contains a non-empty string s (1 ≤ |s| ≤ 5000). It is guaranteed that the string only consists of lowercase English letters.

Output

Print a single number — the answer to the problem.

Examples

Input

bearbtear


Output

6


Input

bearaabearc


Output

20

Note

In the first sample, the following pairs (i, j) match: (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9).

In the second sample, the following pairs (i, j) match: (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (2, 10), (2, 11), (3, 10), (3, 11), (4, 10), (4, 11), (5, 10), (5, 11), (6, 10), (6, 11), (7, 10), (7, 11).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Barica is an unusual frog. She lives in a pond where $N$ plants float on the surface of the water. The plants are numbered $1$ through $N$. When viewing from above, the location of each plant is given by a pair of coordinates. What makes Barica unusual is her fear of jumping diagonally and in the negative direction. More precisely, she can jump from a plant at coordinates $(x_1, y_1)$ to another at coordinates $(x_2, y_2)$ only if:
 - $x_2 > x_1$ and $y_2 = y_1$, or
 - $y_2 > y_1$ and $x_2 = x_1$

For each plant, we know the number of flies in its immediate vicinity. Barica can use her swift tongue to eat all flies near the plant she is at.

Barica absorbs one energy unit for each fly she eats, and uses $K$ energy units for each jump she makes. Barica can not make a jump if she doesn’t have enough energy units beforehand.

Barica wants to go from plant $1$ to plant $N$ and have the largest amount of energy possible after arriving. Barica initially has no energy and must gather energy for her first jump from the flies around plant 1.

Find the sequence of plants Barica should travel to achieve her goal.

-----Input-----
The first line of input contains two integers $N$ and $K$ ($2 \le N \le 300000$, $1 \le K \le 1000$) separated by a space.

Each of the following $N$ lines contains three integers $X$, $Y$ and $F$ ($0 \le X, Y \le 100000$, $0 \le F \le 1000$) separated by spaces, meaning that there is a plant at coordinates $(X, Y)$ with $F$ flies around it.

The first plant in the input is plant $1$, the second is plant $2$ etc.

No two plants will share the same pair of coordinates.

Note: The input data will guarantee that a sequence of jumps, although not necessarily unique, will always exist.

-----Output-----
Output the final energy level on the first line. Output an integer $L$, the number of plants Barica should travel, including plants $1$ and $N$. On the following $L$ lines, output the sequence of plants Barica should travel.

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

Sample Input 2:
8 10
1 1 15
2 2 30
1 2 8
2 1 7
3 2 8
2 3 7
4 2 100
3 3 15
Sample Output 2:
36
5
1 1
1 2
2 2
3 2
3 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is simplified version of the problem used on the original contest. The original problem seems to have too difiicult solution. The constraints for input data have been reduced.

Polycarp likes to play computer role-playing game «Lizards and Basements». At the moment he is playing it as a magician. At one of the last levels he has to fight the line of archers. The only spell with which he can damage them is a fire ball. If Polycarp hits the i-th archer with his fire ball (they are numbered from left to right), the archer loses a health points. At the same time the spell damages the archers adjacent to the i-th (if any) — they lose b (1 ≤ b < a ≤ 10) health points each.

As the extreme archers (i.e. archers numbered 1 and n) are very far, the fire ball cannot reach them. Polycarp can hit any other archer with his fire ball.

The amount of health points for each archer is known. An archer will be killed when this amount is less than 0. What is the minimum amount of spells Polycarp can use to kill all the enemies?

Polycarp can throw his fire ball into an archer if the latter is already killed.

Input

The first line of the input contains three integers n, a, b (3 ≤ n ≤ 10; 1 ≤ b < a ≤ 10). The second line contains a sequence of n integers — h1, h2, ..., hn (1 ≤ hi ≤ 15), where hi is the amount of health points the i-th archer has.

Output

In the first line print t — the required minimum amount of fire balls.

In the second line print t numbers — indexes of the archers that Polycarp should hit to kill all the archers in t shots. All these numbers should be between 2 and n - 1. Separate numbers with spaces. If there are several solutions, output any of them. Print numbers in any order.

Examples

Input

3 2 1
2 2 2


Output

3
2 2 2 

Input

4 3 1
1 4 1 1


Output

4
2 2 3 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an unusual problem in an unusual contest, here is the announcement: [http://codeforces.com/blog/entry/73543](//codeforces.com/blog/entry/73543)

You run a string shop. During a day your customers want to buy strings of certain lengths and sometimes satisfying other properties.

Today your first customer asked you if you have a string of length k. In fact, you have a string of length n and can cut a string of length k starting at any position out of it. You wonder how many distinct values this string can equal.

Please note that in your shop strings are over an alphabet of size 2.

Input

The first line contains two integers n and k (1≤ k≤ n≤ 200 000). The second line contains a binary string s of length n.

Output

In the only line print the number of distinct substrings of length k of the string s.

Examples

Input


5 2
01101


Output


3


Input


10 3
1110001011


Output


8

Note

The second sample test represents the de Bruijn sequence of order 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Surya loves to play with primes. One day, he asked his friend don to print any number in the form of multiple of prime factors. Help don in solving the problem. 

Input
The first line will contain an integer t (1 ≤ t ≤ 10^6) denoting number of test case. 
For each test case, you will be given an integer n (2 ≤ n ≤ 10^6).

Output
Print a string showing prime factors which should look like :
2^e1 * p2^e2 * .........* pk^ek 
where p1, p2, ...., pn are the prime factors and e1, e2, ....., en is the degree of corresponding prime factor.

Note: power of 2 should always be given.
For a prime number , only 2^0 is printed.

SAMPLE INPUT
3
32
100
9085

SAMPLE OUTPUT
2^5
2^2*5^2
2^0*5^1*23^1*79^1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Beakers of various capacities are given. First, choose one of the largest beakers and pour it through the faucet until it is full. Next, transfer the water from the beaker to another beaker according to the following rules.

* All water in the beaker must be transferred to another beaker without leaving. However, if it is not possible to transfer all the water to one beaker, it may be divided into multiple beakers.
* When you fill the beaker with water, you must pour water until it is full. Also, do not spill water.
* Do not pour water from multiple beakers into the same beaker at once.
* Only water the same beaker once.

<image>



When following this rule, create a program that inputs the number of beakers n and the capacity of each beaker, determines whether water can be poured into all beakers, and outputs it. Output YES (half-width uppercase letters) when water can be poured into all beakers, and NO (half-width uppercase letters) when water cannot be poured.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of zeros. Each dataset is given in the following format:


n
c1 c2 ... cn


The number of beakers n (1 ≤ n ≤ 50) is given on the first line. The second line is given the integer ci (1 ≤ ci ≤ 100), which represents the capacity of the i-th beaker.

The number of datasets does not exceed 105.

Output

The judgment result is output to one line for each data set.

Example

Input

10
11 2 23 4 2 12 8 5 2 10
8
2 1 3 11 2 3 1 4
9
5 9 1 2 4 8 17 1 8
8
3 38 9 4 18 14 19 5
1
1
0


Output

YES
YES
YES
NO
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N mountains in a circle, called Mountain 1, Mountain 2, ..., Mountain N in clockwise order. N is an odd number.
Between these mountains, there are N dams, called Dam 1, Dam 2, ..., Dam N. Dam i (1 \leq i \leq N) is located between Mountain i and i+1 (Mountain N+1 is Mountain 1).
When Mountain i (1 \leq i \leq N) receives 2x liters of rain, Dam i-1 and Dam i each accumulates x liters of water (Dam 0 is Dam N).
One day, each of the mountains received a non-negative even number of liters of rain.
As a result, Dam i (1 \leq i \leq N) accumulated a total of A_i liters of water.
Find the amount of rain each of the mountains received. We can prove that the solution is unique under the constraints of this problem.

-----Constraints-----
 - All values in input are integers.
 - 3 \leq N \leq 10^5-1
 - N is an odd number.
 - 0 \leq A_i \leq 10^9
 - The situation represented by input can occur when each of the mountains receives a non-negative even number of liters of rain.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Print N integers representing the number of liters of rain Mountain 1, Mountain 2, ..., Mountain N received, in this order.

-----Sample Input-----
3
2 2 4

-----Sample Output-----
4 0 4

If we assume Mountain 1, 2, and 3 received 4, 0, and 4 liters of rain, respectively, it is consistent with this input, as follows:
 - Dam 1 should have accumulated \frac{4}{2} + \frac{0}{2} = 2 liters of water.
 - Dam 2 should have accumulated \frac{0}{2} + \frac{4}{2} = 2 liters of water.
 - Dam 3 should have accumulated \frac{4}{2} + \frac{4}{2} = 4 liters of water.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nitika was once reading a history book and wanted to analyze it. So she asked her brother to create a list of names of the various famous personalities in the book. Her brother gave Nitika the list. Nitika was furious when she saw the list. The names of the people were not properly formatted. She doesn't like this and would like to properly format it.
A name can have at most three parts: first name, middle name and last name. It will have at least one part. The last name is always present. The rules of formatting a name are very simple:

- Only the first letter of each part of the name should be capital.
- All the parts of the name except the last part should be represented by only two characters. The first character should be the first letter of the part and should be capitalized. The second character should be ".".

Let us look at some examples of formatting according to these rules:
- gandhi -> Gandhi

- mahatma gandhI -> M. Gandhi 
- Mohndas KaramChand ganDhi -> M. K. Gandhi 

-----Input-----
The first line of the input contains an integer T denoting the number of test cases.
The only line of each test case contains the space separated parts of the name.

-----Output-----
For each case, output the properly formatted name.

-----Constraints-----
- 1 ≤ T ≤ 100
- 2 ≤ Length of each part of the name ≤ 10
- Each part of the name contains the letters from lower and upper case English alphabets (i.e. from 'a' to 'z', or 'A' to 'Z')

-----Subtasks-----
Subtask #1 (40 points)
- There is exactly one part in the name.

Subtask #2 (60 points)
- Original constraints.

-----Example-----
Input:
3
gandhi
mahatma gandhI
Mohndas KaramChand gandhi

Output:
Gandhi 
M. Gandhi 
M. K. Gandhi 

-----Explanation-----
The examples are already explained in the problem statement.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Iahub and Iahubina went to a picnic in a forest full of trees. Less than 5 minutes passed before Iahub remembered of trees from programming. Moreover, he invented a new problem and Iahubina has to solve it, otherwise Iahub won't give her the food. 

Iahub asks Iahubina: can you build a rooted tree, such that
 -  each internal node (a node with at least one son) has at least two sons; -  node *i* has *c**i* nodes in its subtree? 
Iahubina has to guess the tree. Being a smart girl, she realized that it's possible no tree can follow Iahub's restrictions. In this way, Iahub will eat all the food. You need to help Iahubina: determine if there's at least one tree following Iahub's restrictions. The required tree must contain *n* nodes.

Input Specification:
The first line of the input contains integer *n* (1<=≤<=*n*<=≤<=24). Next line contains *n* positive integers: the *i*-th number represents *c**i* (1<=≤<=*c**i*<=≤<=*n*).

Output Specification:
Output on the first line "YES" (without quotes) if there exist at least one tree following Iahub's restrictions, otherwise output "NO" (without quotes).

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are the proud owner of the new Multispecies Animal Protection Sanctuary (MAPS). As you arrive on the morning of the grand opening, you realize with horror that some of the animals are in the wrong enclosures. You will deal with the overnight zookeeper later, but right now you need to move all of the animals back to their proper areas before the zoo opens.

You may choose to begin at any of the enclosures, and you must move the animals, one at a time, back to their respective areas. Since time is of the essence, you cannot travel from one enclosure to another unless you are moving an animal directly back to its proper area. Note that the zoo is laid out in such a fashion that it is always possible to travel from one enclosure to another without passing through any other enclosures.

Determine if it is possible to return all of the animals back to their proper enclosures subject to these restrictions.

-----Input-----
The first line of input contains two space-separated integers, $n$ and $m$, where $1\leq n\leq 10000$ denotes the number of different enclosures and $1\leq m\leq 50000$ denotes the total number of animals in the zoo. Each of the next $n$ lines gives the starting state of a different enclosure. Each enclosure is described on a single line using a series of space-separated tokens. The first token is a string indicating which type of animal belongs in this particular enclosure. The second token is a non-negative integer $a$, identifying the number of animals currently in this enclosure. This is followed by $a$ tokens on the same line, each of which is a string indicating the type of one of the animals currently in this enclosure.

Each animal type is composed of lowercase letters (a–z) and contains between $1$ and $8$ characters, inclusive. Each animal in the zoo belongs to exactly one enclosure, and that may or may not correspond to the enclosure that the animal is currently in.

-----Output-----
If at least one animal is not in its proper enclosure, output “POSSIBLE” if it is possible to restore all of the animals back to their proper locations under the above restrictions; otherwise, output “IMPOSSIBLE”. If all the animals are already in their proper enclosures, output “FALSE ALARM” instead.

-----Examples-----
Sample Input:
3 6
monkey 2 lion penguin
lion 3 monkey penguin lion
penguin 1 monkey
Sample Output:
POSSIBLE

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The written representation of a number (with 4 or more digits) can be split into three parts in various different ways. For example, the written number 1234 can be split as [1 | 2 | 34] or [1 | 23 | 4] or [12 | 3 | 4].

Given a written number, find the highest possible product from splitting it into three parts and multiplying those parts together. For example:

- product of [1 | 2 | 34] = 1 \* 2 \* 34 = 68
- product of [1 | 23 | 4] = 1 \* 23 \* 4 = 92
- product of [12 | 3 | 4] = 12 \* 3 \* 4 = 144

So maximumProductOfParts(1234) = 144

For a longer string there will be many possible different ways to split it into parts. For example, 8675309 could be split as: 

- [8 | 6 | 75309] 
- [867 | 530 | 9] 
- [8 | 67 | 5309]
- [86 | 75 | 309]

or any other option that splits the string into three parts each containing at least one digit.

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