vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
JATC and his friend Giraffe are currently in their room, solving some problems. Giraffe has written on the board an array $a_1$, $a_2$, ..., $a_n$ of integers, such that $1 \le a_1 < a_2 < \ldots < a_n \le 10^3$, and then went to the bathroom.

JATC decided to prank his friend by erasing some consecutive elements in the array. Since he doesn't want for the prank to go too far, he will only erase in a way, such that Giraffe can still restore the array using the information from the remaining elements. Because Giraffe has created the array, he's also aware that it's an increasing array and all the elements are integers in the range $[1, 10^3]$.

JATC wonders what is the greatest number of elements he can erase?


-----Input-----

The first line of the input contains a single integer $n$ ($1 \le n \le 100$) — the number of elements in the array.

The second line of the input contains $n$ integers $a_i$ ($1 \le a_1<a_2<\dots<a_n \le 10^3$) — the array written by Giraffe.


-----Output-----

Print a single integer — the maximum number of consecutive elements in the array that JATC can erase.

If it is impossible to erase even a single element, print $0$.


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

Output
2
Input
3
998 999 1000

Output
2
Input
5
1 2 3 4 5

Output
4


-----Note-----

In the first example, JATC can erase the third and fourth elements, leaving the array $[1, 3, \_, \_, 6, 9]$. As you can see, there is only one way to fill in the blanks.

In the second example, JATC can erase the second and the third elements. The array will become $[998, \_, \_]$. Because all the elements are less than or equal to $1000$, the array is still can be restored. Note, that he can't erase the first $2$ elements.

In the third example, JATC can erase the first $4$ elements. Since all the elements are greater than or equal to $1$, Giraffe can still restore the array. Note, that he can't erase the last $4$ elements.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A new innovative ticketing systems for public transport is introduced in Bytesburg. Now there is a single travel card for all transport. To make a trip a passenger scan his card and then he is charged according to the fare.

The fare is constructed in the following manner. There are three types of tickets: 
 1.  a ticket for one trip costs 20 byteland rubles, 1.  a ticket for 90 minutes costs 50 byteland rubles, 1.  a ticket for one day (1440 minutes) costs 120 byteland rubles. 
Note that a ticket for *x* minutes activated at time *t* can be used for trips started in time range from *t* to *t*<=+<=*x*<=-<=1, inclusive. Assume that all trips take exactly one minute.

To simplify the choice for the passenger, the system automatically chooses the optimal tickets. After each trip starts, the system analyses all the previous trips and the current trip and chooses a set of tickets for these trips with a minimum total cost. Let the minimum total cost of tickets to cover all trips from the first to the current is *a*, and the total sum charged before is *b*. Then the system charges the passenger the sum *a*<=-<=*b*.

You have to write a program that, for given trips made by a passenger, calculates the sum the passenger is charged after each trip.

Input Specification:
The first line of input contains integer number *n* (1<=≤<=*n*<=≤<=105) — the number of trips made by passenger.

Each of the following *n* lines contains the time of trip *t**i* (0<=≤<=*t**i*<=≤<=109), measured in minutes from the time of starting the system. All *t**i* are different, given in ascending order, i. e. *t**i*<=+<=1<=&gt;<=*t**i* holds for all 1<=≤<=*i*<=&lt;<=*n*.

Output Specification:
Output *n* integers. For each trip, print the sum the passenger is charged after it.

Demo Input:
['3\n10\n20\n30\n', '10\n13\n45\n46\n60\n103\n115\n126\n150\n256\n516\n']

Demo Output:
['20\n20\n10\n', '20\n20\n10\n0\n20\n0\n0\n20\n20\n10\n']

Note:
In the first example, the system works as follows: for the first and second trips it is cheaper to pay for two one-trip tickets, so each time 20 rubles is charged, after the third trip the system understands that it would be cheaper to buy a ticket for 90 minutes. This ticket costs 50 rubles, and the passenger had already paid 40 rubles, so it is necessary to charge 10 rubles only.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the "Hobbit" movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names.

There are *n* students in a summer school. Teachers chose exactly *n* pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym *b* to a student with name *a* as the length of the largest common prefix *a* and *b*. We will represent such value as . Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students.

Find the matching between students and pseudonyms with the maximum quality.

Input Specification:
The first line contains number *n* (1<=≤<=*n*<=≤<=100<=000) — the number of students in the summer school.

Next *n* lines contain the name of the students. Each name is a non-empty word consisting of lowercase English letters. Some names can be repeating.

The last *n* lines contain the given pseudonyms. Each pseudonym is a non-empty word consisting of small English letters. Some pseudonyms can be repeating.

The total length of all the names and pseudonyms doesn't exceed 800<=000 characters.

Output Specification:
In the first line print the maximum possible quality of matching pseudonyms to students.

In the next *n* lines describe the optimal matching. Each line must have the form *a* *b* (1<=≤<=*a*,<=*b*<=≤<=*n*), that means that the student who was number *a* in the input, must match to the pseudonym number *b* in the input.

The matching should be a one-to-one correspondence, that is, each student and each pseudonym should occur exactly once in your output. If there are several optimal answers, output any.

Demo Input:
['5\ngennady\ngalya\nboris\nbill\ntoshik\nbilbo\ntorin\ngendalf\nsmaug\ngaladriel\n']

Demo Output:
['11\n4 1\n2 5\n1 3\n5 2\n3 4\n']

Note:
The first test from the statement the match looks as follows: 
 -  bill  →  bilbo (lcp = 3) -  galya  →  galadriel (lcp = 3) -  gennady  →  gendalf (lcp = 3) -  toshik  →  torin (lcp = 2) -  boris  →  smaug (lcp = 0)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You're given a string containing a sequence of words separated with whitespaces. Let's say it is a sequence of patterns: a name and a corresponding number - like this:

```"red 1 yellow 2 black 3 white 4"```

You want to turn it into a different **string** of objects you plan to work with later on - like this:

```"[{name : 'red', id : '1'}, {name : 'yellow', id : '2'}, {name : 'black', id : '3'}, {name : 'white', id : '4'}]"```

Doing this manually is a pain. So you've decided to write a short function that would make the computer do the job for you. Keep in mind, the pattern isn't necessarily a word and a number. Consider anything separeted by a whitespace, just don't forget: an array of objects with two elements: name and id.

As a result you'll have a string you may just copy-paste whenever you feel like defining a list of objects - now without the need to put in names, IDs, curly brackets, colon signs, screw up everything, fail searching for a typo and begin anew. This might come in handy with large lists.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Last year iElectro has given a circuit deigning problem , in which participants will have to prepare a grid of bulbs such that ,if you select a particular bulb in the grid to toggle (if bulb is ON you turn it OFF and vice versa),then the bulb itself and its neighbouring (up,down,left,right) bulbs will also get toggled.

The Winners of that competition, has a challenge for all you programming geeks. Now you are given the same grid with some random bulbs on and off, and your task is to find the minimum number of choices you could make to lit all the bulbs in the grid. 

Input:
Description of each grid starts with a line of two space separated integers n and m representing number of rows and columns of the grid respectively. Next n lines each with m characters represents the grid. 

‘X’ in the grid represents the bulb which is OFF.

‘.’ In the grid represents the bulb which is ON.

Each description of the grids will be separated by a line. Test case ends with the line “0 0”.

1 ≤ n,m ≤ 15

Output:
For each grid print the minimum number of choices made to turn on all the lights in a new line, print -1 if not possible to do so.

SAMPLE INPUT
3 3
.X.
XXX
.X.

1 5
...XX

0 0

SAMPLE OUTPUT
1
1

Explanation

Case 1: By Toggling the light at position (2,2) all the lights will turn on.
Case 2: By toggling the light at position (1,5) all the lights will turn on.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Having read half of the book called "Storm and Calm" on the IT lesson, Innocentius was absolutely determined to finish the book on the maths lessons. All was fine until the math teacher Ms. Watkins saw Innocentius reading fiction books instead of solving equations of the fifth degree. As during the last maths class Innocentius suggested the algorithm of solving equations of the fifth degree in the general case, Ms. Watkins had no other choice but to give him a new task.

The teacher asked to write consecutively (without spaces) all words from the "Storm and Calm" in one long string s. She thought that a string is good if the number of vowels in the string is no more than twice more than the number of consonants. That is, the string with v vowels and c consonants is good if and only if v ≤ 2c.

The task Innocentius had to solve turned out to be rather simple: he should find the number of the longest good substrings of the string s.

Input

The only input line contains a non-empty string s consisting of no more than 2·105 uppercase and lowercase Latin letters. We shall regard letters "a", "e", "i", "o", "u" and their uppercase variants as vowels.

Output

Print on a single line two numbers without a space: the maximum length of a good substring and the number of good substrings with this length. If no good substring exists, print "No solution" without the quotes.

Two substrings are considered different if their positions of occurrence are different. So if some string occurs more than once, then it should be counted more than once.

Examples

Input

Abo


Output

3 1


Input

OEIS


Output

3 1


Input

auBAAbeelii


Output

9 3


Input

AaaBRAaaCAaaDAaaBRAaa


Output

18 4


Input

EA


Output

No solution

Note

In the first sample there is only one longest good substring: "Abo" itself. The other good substrings are "b", "Ab", "bo", but these substrings have shorter length.

In the second sample there is only one longest good substring: "EIS". The other good substrings are: "S", "IS".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every year the three friendly teachers at the kindergarten let their classes’ kids change classes to form three new ones. Some kids, of course, are old enough to leave, but those who stay for another year are rearranged among the three teachers.

The teachers even let the kids have their say in the process. As friendship both comes and goes hastily in young years, each kid $X$ ranks every other kid $Y$ according to how glad $X$ would be to have $Y$ in her new class. In fact, $X$ produces a preference list giving a total order of the other kids, i.e. there are no such things as ties – kids she would be equally glad to have as classmates.

The three teachers do not mind if the new classes formed are unbalanced in size, since they fill up their classes with new kids about to start their first year at the kindergarten. They do, however, want all the kids in their own new class to be different from last year, since even a teacher needs a break after a whole year with the same kids. They decide that a best partition into three classes under these premises is one where no kid is in the same class as a kid not listed among the top $T$ entries on their preference list, for $T$ as small as possible. Note that the kids in a new class may very well be the same as in an old one, but then with a new teacher!

-----Input-----
The first line of input contains an integer $1\leq N \leq 200$ giving the number of kids to be rearranged at the kindergarten. The kids are numbered $1$ through $N$.

Then follow $N$ lines describing the kids. The $i$-th row first contains the identifier of their current class’ teacher (an integer $0$, $1$, or $2$), and next the $N-1$ integers $\{ 1,2,3,…,i-1,i+1,…,N\} $ in some order, describing the classmate preference list of the $i$-th kid, in descending order.

-----Output-----
The smallest non-negative integer $T$, such that there is a partitioning of the kids in three new classes such that
 - no kid has the same teacher as in their current class, and
 - all kids’ classmates are among the top $T$ places of their preference lists, respectively.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer range [A,B],  

What’s the probability to get a 1-bit if we first randomly choose a number x in the range and then randomly choose a bit from x?  
What’s the expected number of bit 1s if we randomly choose a number x in the range?  

Input Format 

The first line of input is the number of test cases $\mathbf{T}$ 

Each test cases is a line contains 2 integers $\mbox{A}$ and $\mbox{B}$ separated by a space. 

Output Format 

For each test case output a line containing 2 float numbers separated by a space. The first one is the probability and the second one is the expected number. You should output the number accurate to 5 fractional digits. 

Constraints 

$1\leq T\leq200$ 

$1\leq A\leq B\leq10^{10}$  

Sample Input

1
2 4

Sample Output

0.61111 1.33333

Explanation 

(10)  (11)  (100) 

(1) So we got a one in $\frac{1}{3}\times\frac{1}{2}+\frac{1}{3}\times\frac{1}{1}+\frac{1}{3}\times\frac{1}{3}=\frac{11}{18}$ 

(2) The expected 1 we have is : $1\times\frac{1}{3}+2\times\frac{1}{3}+1\times\frac{1}{3}=\frac{4}{3}$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has a water bottle with the shape of a rectangular prism whose base is a square of side a~\mathrm{cm} and whose height is b~\mathrm{cm}. (The thickness of the bottle can be ignored.)
We will pour x~\mathrm{cm}^3 of water into the bottle, and gradually tilt the bottle around one of the sides of the base.
When will the water be spilled? More formally, find the maximum angle in which we can tilt the bottle without spilling any water.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq a \leq 100
 - 1 \leq b \leq 100
 - 1 \leq x \leq a^2b

-----Input-----
Input is given from Standard Input in the following format:
a b x

-----Output-----
Print the maximum angle in which we can tilt the bottle without spilling any water, in degrees.
Your output will be judged as correct when the absolute or relative error from the judge's output is at most 10^{-6}.

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

-----Sample Output-----
45.0000000000

This bottle has a cubic shape, and it is half-full. The water gets spilled when we tilt the bottle more than 45 degrees.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have $a$ coins of value $n$ and $b$ coins of value $1$. You always pay in exact change, so you want to know if there exist such $x$ and $y$ that if you take $x$ ($0 \le x \le a$) coins of value $n$ and $y$ ($0 \le y \le b$) coins of value $1$, then the total value of taken coins will be $S$.

You have to answer $q$ independent test cases.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 10^4$) — the number of test cases. Then $q$ test cases follow.

The only line of the test case contains four integers $a$, $b$, $n$ and $S$ ($1 \le a, b, n, S \le 10^9$) — the number of coins of value $n$, the number of coins of value $1$, the value $n$ and the required total value.


-----Output-----

For the $i$-th test case print the answer on it — YES (without quotes) if there exist such $x$ and $y$ that if you take $x$ coins of value $n$ and $y$ coins of value $1$, then the total value of taken coins will be $S$, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).


-----Example-----
Input
4
1 2 3 4
1 2 3 6
5 2 6 27
3 3 5 18

Output
YES
NO
NO
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ross is an archaeologist. He is leading a team that recently found an ancient place. They could collect few information about this place like maps and scripts. The map they found has only 1s and 0s. 

From the scripts they found, they got to know that this map resembles the place and there is a treasure buried under the area which is represented as a diagonal matrix of equal side lengths in the map. Some other script mentioned that it should be the largest possible matrix.

Ross and his team is finding it difficult to find that in the map and contacted you for help. Find the dimension of largest diagonal matrix.

Input format:

First line has T denoting number of test cases.
Each test case starts with two integers in first line M,N denoting rows and columns in the map/matrix.
M lines follows with N integers separated with a space.

Output format:

Print a single integer denoting side length of largest possible diagonal matrix in given matrix.

Constraints:

1 ≤ T ≤ 50
1 ≤ M,N ≤ 500
0 ≤ A[i][j] ≤ 1

Problem Setter: Vinay Kumar

SAMPLE INPUT
2
5 5
1 1 1 1 1
1 0 1 1 0
1 1 1 0 1
1 1 0 1 1
1 0 1 1 0
4 5
1 1 0 0 0
0 1 0 0 1
0 0 1 0 1
0 0 0 1 0

SAMPLE OUTPUT
2
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Kuriyama Mirai's Stones

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kuriyama Mirai has killed many monsters and got many (namely *n*) stones. She numbers the stones from 1 to *n*. The cost of the *i*-th stone is *v**i*. Kuriyama Mirai wants to know something about these stones so she will ask you two kinds of questions:
 1.  She will tell you two numbers, *l* and *r* (1<=≤<=*l*<=≤<=*r*<=≤<=*n*), and you should tell her . 1.  Let *u**i* be the cost of the *i*-th cheapest stone (the cost that will be on the *i*-th place if we arrange all the stone costs in non-decreasing order). This time she will tell you two numbers, *l* and *r* (1<=≤<=*l*<=≤<=*r*<=≤<=*n*), and you should tell her . 
For every question you should give the correct answer, or Kuriyama Mirai will say "fuyukai desu" and then become unhappy.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=105). The second line contains *n* integers: *v*1,<=*v*2,<=...,<=*v**n* (1<=≤<=*v**i*<=≤<=109) — costs of the stones. 

The third line contains an integer *m* (1<=≤<=*m*<=≤<=105) — the number of Kuriyama Mirai's questions. Then follow *m* lines, each line contains three integers *type*, *l* and *r* (1<=≤<=*l*<=≤<=*r*<=≤<=*n*; 1<=≤<=*type*<=≤<=2), describing a question. If *type* equal to 1, then you should output the answer for the first question, else you should output the answer for the second one.

Output Specification:
Print *m* lines. Each line must contain an integer — the answer to Kuriyama Mirai's question. Print the answers to the questions in the order of input.

Demo Input:
['6\n6 4 2 7 2 7\n3\n2 3 6\n1 3 4\n1 1 6\n', '4\n5 5 2 3\n10\n1 2 4\n2 1 4\n1 1 1\n2 1 4\n2 1 2\n1 1 1\n1 3 3\n1 1 3\n1 4 4\n1 2 2\n']

Demo Output:
['24\n9\n28\n', '10\n15\n5\n15\n5\n5\n2\n12\n3\n5\n']

Note:
Please note that the answers to the questions may overflow 32-bit integer type.

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

Walking through the streets of Marshmallow City, Slastyona have spotted some merchants selling a kind of useless toy which is very popular nowadays – caramel spinner! Wanting to join the craze, she has immediately bought the strange contraption.

Spinners in Sweetland have the form of V-shaped pieces of caramel. Each spinner can, well, spin around an invisible magic axis. At a specific point in time, a spinner can take 4 positions shown below (each one rotated 90 degrees relative to the previous, with the fourth one followed by the first one):

<image>

After the spinner was spun, it starts its rotation, which is described by a following algorithm: the spinner maintains its position for a second then majestically switches to the next position in clockwise or counter-clockwise order, depending on the direction the spinner was spun in.

Slastyona managed to have spinner rotating for exactly n seconds. Being fascinated by elegance of the process, she completely forgot the direction the spinner was spun in! Lucky for her, she managed to recall the starting position, and wants to deduct the direction given the information she knows. Help her do this.

Input

There are two characters in the first string – the starting and the ending position of a spinner. The position is encoded with one of the following characters: v (ASCII code 118, lowercase v), < (ASCII code 60), ^ (ASCII code 94) or > (ASCII code 62) (see the picture above for reference). Characters are separated by a single space.

In the second strings, a single number n is given (0 ≤ n ≤ 109) – the duration of the rotation.

It is guaranteed that the ending position of a spinner is a result of a n second spin in any of the directions, assuming the given starting position.

Output

Output cw, if the direction is clockwise, ccw – if counter-clockwise, and undefined otherwise.

Examples

Input

^ &gt;
1


Output

cw


Input

&lt; ^
3


Output

ccw


Input

^ v
6


Output

undefined

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