vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Grigoriy, like the hero of one famous comedy film, found a job as a night security guard at the museum. At first night he received embosser and was to take stock of the whole exposition.

Embosser is a special devise that allows to "print" the text of a plastic tape. Text is printed sequentially, character by character. The device consists of a wheel with a lowercase English letters written in a circle, static pointer to the current letter and a button that print the chosen letter. At one move it's allowed to rotate the alphabetic wheel one step clockwise or counterclockwise. Initially, static pointer points to letter 'a'. Other letters are located as shown on the picture:

<image>

After Grigoriy add new item to the base he has to print its name on the plastic tape and attach it to the corresponding exhibit. It's not required to return the wheel to its initial position with pointer on the letter 'a'.

Our hero is afraid that some exhibits may become alive and start to attack him, so he wants to print the names as fast as possible. Help him, for the given string find the minimum number of rotations of the wheel required to print it.

Input

The only line of input contains the name of some exhibit — the non-empty string consisting of no more than 100 characters. It's guaranteed that the string consists of only lowercase English letters.

Output

Print one integer — the minimum number of rotations of the wheel, required to print the name given in the input.

Examples

Input

zeus


Output

18


Input

map


Output

35


Input

ares


Output

34

Note

<image>

To print the string from the first sample it would be optimal to perform the following sequence of rotations: 

  1. from 'a' to 'z' (1 rotation counterclockwise), 
  2. from 'z' to 'e' (5 clockwise rotations), 
  3. from 'e' to 'u' (10 rotations counterclockwise), 
  4. from 'u' to 's' (2 counterclockwise rotations). 

In total, 1 + 5 + 10 + 2 = 18 rotations are required.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Mirko is studying the hash function which associates numerical values to words. The function is defined recursively in the following way:
 - $f( \text {empty word} ) = 0$
 - $f( \text {word} + \text {letter} ) = ( ( f( \text {word} ) \cdot 33 ) \oplus \mathrm{ord}( \text {letter} ) ) \mathbin {\% } \mathrm{MOD}$

The function is defined for words that consist of only lowercase letters of the English alphabet. $\oplus $ stands for the bitwise exclusive or operator (i.e. $0110 \oplus 1010 = 1100$), $\mathrm{ord}(\text {letter})$ stands for the ordinal number of the letter in the alphabet ($\mathrm{ord}(\mathtt{a}) = 1$, $\mathrm{ord}(\mathtt{z}) = 26$) and $A \mathbin {\% } B$ stands for the remainder of the number $A$ when performing integer division with the number $B$. $\mathrm{MOD}$ will be an integer of the form $2^M$.

Some values of the hash function when $M$ = 10:
 - $f( \mathtt{a} ) = 1$
 - $f ( \mathtt{aa} ) = 32$
 - $f ( \mathtt{kit} ) = 438$

Mirko wants to find out how many words of the length $N$ there are with the hash value $K$. Write a programme to help him calculate this number.

-----Input-----
The first line of input contains three integers $N$, $K$ and $M$ ($1 \leq N \leq 10$, $0 \leq K < 2^M$, $6 \leq M \leq 25$).

-----Output-----
The first and only line of output must consist of the required number from the task.

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

Sample Input 2:
1 2 10
Sample Output 2:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Doubly linked list is one of the fundamental data structures. A doubly linked list is a sequence of elements, each containing information about the previous and the next elements of the list. In this problem all lists have linear structure. I.e. each element except the first has exactly one previous element, each element except the last has exactly one next element. The list is not closed in a cycle.

In this problem you are given n memory cells forming one or more doubly linked lists. Each cell contains information about element from some list. Memory cells are numbered from 1 to n.

For each cell i you are given two values:   l_{i} — cell containing previous element for the element in the cell i;  r_{i} — cell containing next element for the element in the cell i. 

If cell i contains information about the element which has no previous element then l_{i} = 0. Similarly, if cell i contains information about the element which has no next element then r_{i} = 0. [Image] Three lists are shown on the picture. 

For example, for the picture above the values of l and r are the following: l_1 = 4, r_1 = 7; l_2 = 5, r_2 = 0; l_3 = 0, r_3 = 0; l_4 = 6, r_4 = 1; l_5 = 0, r_5 = 2; l_6 = 0, r_6 = 4; l_7 = 1, r_7 = 0.

Your task is to unite all given lists in a single list, joining them to each other in any order. In particular, if the input data already contains a single list, then there is no need to perform any actions. Print the resulting list in the form of values l_{i}, r_{i}.

Any other action, other than joining the beginning of one list to the end of another, can not be performed.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of memory cells where the doubly linked lists are located.

Each of the following n lines contains two integers l_{i}, r_{i} (0 ≤ l_{i}, r_{i} ≤ n) — the cells of the previous and the next element of list for cell i. Value l_{i} = 0 if element in cell i has no previous element in its list. Value r_{i} = 0 if element in cell i has no next element in its list.

It is guaranteed that the input contains the correct description of a single or more doubly linked lists. All lists have linear structure: each element of list except the first has exactly one previous element; each element of list except the last has exactly one next element. Each memory cell contains information about one element from some list, each element of each list written in one of n given cells.


-----Output-----

Print n lines, the i-th line must contain two integers l_{i} and r_{i} — the cells of the previous and the next element of list for cell i after all lists from the input are united in a single list. If there are many solutions print any of them.


-----Example-----
Input
7
4 7
5 0
0 0
6 1
0 2
0 4
1 0

Output
4 7
5 6
0 5
6 1
3 2
2 4
1 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Find the price of a product before tax such that, when the consumption tax rate is 8 percent and 10 percent, the amount of consumption tax levied on it is A yen and B yen, respectively. (Yen is the currency of Japan.)
Here, the price before tax must be a positive integer, and the amount of consumption tax is rounded down to the nearest integer.
If multiple prices satisfy the condition, print the lowest such price; if no price satisfies the condition, print -1.

-----Constraints-----
 - 1 \leq A \leq B \leq 100
 - A and B are integers.

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
If there is a price that satisfies the condition, print an integer representing the lowest such price; otherwise, print -1.

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

-----Sample Output-----
25

If the price of a product before tax is 25 yen, the amount of consumption tax levied on it is:
 - When the consumption tax rate is 8 percent: \lfloor 25 \times 0.08 \rfloor = \lfloor 2 \rfloor = 2 yen.
 - When the consumption tax rate is 10 percent: \lfloor 25 \times 0.1 \rfloor = \lfloor 2.5 \rfloor = 2 yen.
Thus, the price of 25 yen satisfies the condition. There are other possible prices, such as 26 yen, but print the minimum such price, 25.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Ilya and tic-tac-toe game

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Ilya is an experienced player in tic-tac-toe on the 4<=×<=4 field. He always starts and plays with Xs. He played a lot of games today with his friend Arseny. The friends became tired and didn't finish the last game. It was Ilya's turn in the game when they left it. Determine whether Ilya could have won the game by making single turn or not. 

The rules of tic-tac-toe on the 4<=×<=4 field are as follows. Before the first turn all the field cells are empty. The two players take turns placing their signs into empty cells (the first player places Xs, the second player places Os). The player who places Xs goes first, the another one goes second. The winner is the player who first gets three of his signs in a row next to each other (horizontal, vertical or diagonal).

Input Specification:
The tic-tac-toe position is given in four lines.

Each of these lines contains four characters. Each character is '.' (empty cell), 'x' (lowercase English letter x), or 'o' (lowercase English letter o). It is guaranteed that the position is reachable playing tic-tac-toe, and it is Ilya's turn now (in particular, it means that the game is not finished). It is possible that all the cells are empty, it means that the friends left without making single turn.

Output Specification:
Print single line: "YES" in case Ilya could have won by making single turn, and "NO" otherwise.

Demo Input:
['xx..\n.oo.\nx...\noox.\n', 'x.ox\nox..\nx.o.\noo.x\n', 'x..x\n..oo\no...\nx.xo\n', 'o.x.\no...\n.x..\nooxx\n']

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

Note:
In the first example Ilya had two winning moves: to the empty cell in the left column and to the leftmost empty cell in the first row.

In the second example it wasn't possible to win by making single turn.

In the third example Ilya could have won by placing X in the last row between two existing Xs.

In the fourth example it wasn't possible to win by making single turn.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N pieces of sushi. Each piece has two parameters: "kind of topping" t_i and "deliciousness" d_i.
You are choosing K among these N pieces to eat.
Your "satisfaction" here will be calculated as follows:
 - The satisfaction is the sum of the "base total deliciousness" and the "variety bonus".
 - The base total deliciousness is the sum of the deliciousness of the pieces you eat.
 - The variety bonus is x*x, where x is the number of different kinds of toppings of the pieces you eat.
You want to have as much satisfaction as possible.
Find this maximum satisfaction.

-----Constraints-----
 - 1 \leq K \leq N  \leq 10^5
 - 1 \leq t_i \leq N
 - 1 \leq d_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
t_1 d_1
t_2 d_2
.
.
.
t_N d_N

-----Output-----
Print the maximum satisfaction that you can obtain.

-----Sample Input-----
5 3
1 9
1 7
2 6
2 5
3 1

-----Sample Output-----
26

If you eat Sushi 1,2 and 3:
 - The base total deliciousness is 9+7+6=22.
 - The variety bonus is 2*2=4.
Thus, your satisfaction will be 26, which is optimal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem you will be solving one of the most profound challenges of humans across the world since the beginning of time – how to make lots of money.

You are a middleman in the widget market. Your job is to buy widgets from widget producer companies and sell them to widget consumer companies. Each widget consumer company has an open request for one widget per day, until some end date, and a price at which it is willing to buy the widgets. On the other hand, each widget producer company has a start date at which it can start delivering widgets and a price at which it will deliver each widget.

Due to fair competition laws, you can sign a contract with only one producer company and only one consumer company. You will buy widgets from the producer company, one per day, starting on the day it can start delivering, and ending on the date specified by the consumer company. On each of those days you earn the difference between the producer’s selling price and the consumer’s buying price.

Your goal is to choose the consumer company and the producer company that will maximize your profits.

-----Input-----
The first line of input contains two integers $m$ and $n$ ($1 \leq m, n \leq 500000$) denoting the number of producer and consumer companies in the market, respectively. It is followed by $m$ lines, the $i^{\text {th}}$ of which contains two integers $p_ i$ and $d_ i$ ($1 \leq p_ i, d_ i \leq 10^9$), the price (in dollars) at which the $i^{\text {th}}$ producer sells one widget and the day on which the first widget will be available from this company. Then follow $n$ lines, the $j^{\text {th}}$ of which contains two integers $q_ j$ and $e_ j$ ($1 \leq q_ j, e_ j \leq 10^9$), the price (in dollars) at which the $j^{\text {th}}$ consumer is willing to buy widgets and the day immediately after the day on which the last widget has to be delivered to this company.

-----Output-----
Display the maximum total number of dollars you can earn. If there is no way to sign contracts that gives you any profit, display 0.

-----Examples-----
Sample Input:
2 2
1 3
2 1
3 5
7 2
Sample Output:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Turtle loves drawing on his whiteboard at home. One day when he was drawing, his marker dried out! Mr. Turtle then noticed that the marker behaved like an eraser for the remainder of his drawing.

Mr. Turtle has a picture in his head of how he wants his final drawing to appear. He plans out his entire drawing ahead of time, step by step. Mr. Turtle’s plan is a sequence of commands: up, down, left or right, with a distance. He starts drawing in the bottom left corner of his whiteboard. Consider the $6 \times 8$ whiteboard and sequence of commands in the first diagram. If the marker runs dry at timestep $17$, the board will look like the second diagram (the numbers indicate the timestep when the marker is at each cell). Note that it will make a mark at timestep $17$, but not at timestep $18$. 

Mr. Turtle wants to know the earliest and latest time his marker can dry out, and he’ll still obtain the drawing in his head. Can you help him? Note that timestep $0$ is the moment before the marker touches the board. It is valid for a marker to dry out at timestep $0$.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The input will start with a line with $3$ space-separated integers $h$, $w$ and $n$ ($1 \le h,w,n \le 1000000, w \cdot h \le 1000000$) where $h$ and $w$ are the height and width of the whiteboard respectively, and $n$ is the number of commands in Mr. Turtle’s plan.

The next $h$ lines will each consist of exactly $w$ characters, with each character being either ‘#’ or ‘.’ . This is the pattern in Mr. Turtle’s head, where ’#’ is a marked cell, and ‘.’ is a blank cell.

The next $n$ lines will each consist of a command, of the form “direction distance”, with a single space between the direction and the distance and no other spaces on the line. The direction will be exactly one of the set $\{ \texttt{up}, \texttt{down}, \texttt{left}, \texttt{right} \} $, guaranteed to be all lower case. The distance will be between $1$ and $1000000$ inclusive. The commands must be executed in order. It is guaranteed that no command will take the marker off of the whiteboard.

-----Output-----
Output two integers, first the minimum, then the maximum time that can pass before the marker dries out, and Mr. Turtle can still end up with the target drawing. Neither number should be larger than the last timestep that the marker is on the board, so if the marker can run to the end and still draw the target drawing, use the last timestep that the marker is on the board. If it’s not possible to end up with the target drawing, output -1 -1.

-----Examples-----
Sample Input 1:
6 8 5
........
...#....
########
#..#...#
#..#####
#.......
up 3
right 7
down 2
left 4
up 3
Sample Output 1:
20 20

Sample Input 2:
6 8 5
........
........
###.####
#......#
#..#####
#.......
up 3
right 7
down 2
left 4
up 3
Sample Output 2:
17 17

Sample Input 3:
3 3 2
...
.#.
...
up 2
right 2
Sample Output 3:
-1 -1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Nearly each project of the F company has a whole team of developers working on it. They often are in different rooms of the office in different cities and even countries. To keep in touch and track the results of the project, the F company conducts shared online meetings in a Spyke chat.

One day the director of the F company got hold of the records of a part of an online meeting of one successful team. The director watched the record and wanted to talk to the team leader. But how can he tell who the leader is? The director logically supposed that the leader is the person who is present at any conversation during a chat meeting. In other words, if at some moment of time at least one person is present on the meeting, then the leader is present on the meeting.

You are the assistant director. Given the 'user logged on'/'user logged off' messages of the meeting in the chronological order, help the director determine who can be the leader. Note that the director has the record of only a continuous part of the meeting (probably, it's not the whole meeting).

Input Specification:
The first line contains integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=105) — the number of team participants and the number of messages. Each of the next *m* lines contains a message in the format:
 -  '+ *id*': the record means that the person with number *id* (1<=≤<=*id*<=≤<=*n*) has logged on to the meeting. -  '- *id*': the record means that the person with number *id* (1<=≤<=*id*<=≤<=*n*) has logged off from the meeting. 
Assume that all the people of the team are numbered from 1 to *n* and the messages are given in the chronological order. It is guaranteed that the given sequence is the correct record of a continuous part of the meeting. It is guaranteed that no two log on/log off events occurred simultaneously.

Output Specification:
In the first line print integer *k* (0<=≤<=*k*<=≤<=*n*) — how many people can be leaders. In the next line, print *k* integers in the increasing order — the numbers of the people who can be leaders.

If the data is such that no member of the team can be a leader, print a single number 0.

Demo Input:
['5 4\n+ 1\n+ 2\n- 2\n- 1\n', '3 2\n+ 1\n- 2\n', '2 4\n+ 1\n- 1\n+ 2\n- 2\n', '5 6\n+ 1\n- 1\n- 3\n+ 3\n+ 4\n- 4\n', '2 4\n+ 1\n- 2\n+ 2\n- 1\n']

Demo Output:
['4\n1 3 4 5 ', '1\n3 ', '0\n', '3\n2 3 5 ', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You wrote all your unit test names in camelCase.
But some of your colleagues have troubles reading these long test names.
So you make a compromise to switch to underscore separation.

To make these changes fast you wrote a class to translate a camelCase name
into an underscore separated name.

Implement the ToUnderscore() method.

Example:

`"ThisIsAUnitTest" => "This_Is_A_Unit_Test"`


**But of course there are always special cases...**

You also have some calculation tests. Make sure the results don't get split by underscores.
So only add an underscore in front of the first number.

Also Some people already used underscore names in their tests. You don't want to change them.
But if they are not split correct you should adjust them.

Some of your colleagues mark their tests with a leading and trailing underscore.
Don't remove this.

And of course you should handle empty strings to avoid unnecessary errors. Just return an empty string then.

Example:

`"Calculate15Plus5Equals20" => "Calculate_15_Plus_5_Equals_20"`

`"This_Is_Already_Split_Correct" => "This_Is_Already_Split_Correct"`

`"ThisIs_Not_SplitCorrect" => "This_Is_Not_Split_Correct"`

`"_UnderscoreMarked_Test_Name_" => _Underscore_Marked_Test_Name_"`

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The new "Die Hard" movie has just been released! There are *n* people at the cinema box office standing in a huge line. Each of them has a single 100, 50 or 25 ruble bill. A "Die Hard" ticket costs 25 rubles. Can the booking clerk sell a ticket to each person and give the change if he initially has no money and sells the tickets strictly in the order people follow in the line?

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) — the number of people in the line. The next line contains *n* integers, each of them equals 25, 50 or 100 — the values of the bills the people have. The numbers are given in the order from the beginning of the line (at the box office) to the end of the line.

Output Specification:
Print "YES" (without the quotes) if the booking clerk can sell a ticket to each person and give the change. Otherwise print "NO".

Demo Input:
['4\n25 25 50 50\n', '2\n25 100\n', '4\n50 50 25 25\n']

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

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The clique problem is one of the most well-known NP-complete problems. Under some simplification it can be formulated as follows. Consider an undirected graph *G*. It is required to find a subset of vertices *C* of the maximum size such that any two of them are connected by an edge in graph *G*. Sounds simple, doesn't it? Nobody yet knows an algorithm that finds a solution to this problem in polynomial time of the size of the graph. However, as with many other NP-complete problems, the clique problem is easier if you consider a specific type of a graph.

Consider *n* distinct points on a line. Let the *i*-th point have the coordinate *x**i* and weight *w**i*. Let's form graph *G*, whose vertices are these points and edges connect exactly the pairs of points (*i*,<=*j*), such that the distance between them is not less than the sum of their weights, or more formally: |*x**i*<=-<=*x**j*|<=≥<=*w**i*<=+<=*w**j*.

Find the size of the maximum clique in such graph.

Input Specification:
The first line contains the integer *n* (1<=≤<=*n*<=≤<=200<=000) — the number of points.

Each of the next *n* lines contains two numbers *x**i*, *w**i* (0<=≤<=*x**i*<=≤<=109,<=1<=≤<=*w**i*<=≤<=109) — the coordinate and the weight of a point. All *x**i* are different.

Output Specification:
Print a single number — the number of vertexes in the maximum clique of the given graph.

Demo Input:
['4\n2 3\n3 1\n6 1\n0 2\n']

Demo Output:
['3\n']

Note:
If you happen to know how to solve this problem without using the specific properties of the graph formulated in the problem statement, then you are able to get a prize of one million dollars!

The picture for the sample test.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is trying to solve some pattern problems, Chef wants your help to code it. Chef has one number K to form a new pattern. Help the chef to code this pattern problem.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, one integer $K$. 

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 100$

-----Sample Input:-----
4
1
2
3
4

-----Sample Output:-----
1
21
*1
321
*21
**1
4321
*321
**21
***1

-----EXPLANATION:-----
No need, else pattern can be decode easily.

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