vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Vasiliy is fond of solving different tasks. Today he found one he wasn't able to solve himself, so he asks you to help.

Vasiliy is given n strings consisting of lowercase English letters. He wants them to be sorted in lexicographical order (as in the dictionary), but he is not allowed to swap any of them. The only operation he is allowed to do is to reverse any of them (first character becomes last, second becomes one before last and so on).

To reverse the i-th string Vasiliy has to spent c_{i} units of energy. He is interested in the minimum amount of energy he has to spent in order to have strings sorted in lexicographical order.

String A is lexicographically smaller than string B if it is shorter than B (|A| < |B|) and is its prefix, or if none of them is a prefix of the other and at the first position where they differ character in A is smaller than the character in B.

For the purpose of this problem, two equal strings nearby do not break the condition of sequence being sorted lexicographically.


-----Input-----

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of strings.

The second line contains n integers c_{i} (0 ≤ c_{i} ≤ 10^9), the i-th of them is equal to the amount of energy Vasiliy has to spent in order to reverse the i-th string. 

Then follow n lines, each containing a string consisting of lowercase English letters. The total length of these strings doesn't exceed 100 000.


-----Output-----

If it is impossible to reverse some of the strings such that they will be located in lexicographical order, print  - 1. Otherwise, print the minimum total amount of energy Vasiliy has to spent.


-----Examples-----
Input
2
1 2
ba
ac

Output
1

Input
3
1 3 1
aa
ba
ac

Output
1

Input
2
5 5
bbb
aaa

Output
-1

Input
2
3 3
aaa
aa

Output
-1



-----Note-----

In the second sample one has to reverse string 2 or string 3. To amount of energy required to reverse the string 3 is smaller.

In the third sample, both strings do not change after reverse and they go in the wrong order, so the answer is  - 1.

In the fourth sample, both strings consists of characters 'a' only, but in the sorted order string "aa" should go before string "aaa", thus the answer is  - 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are planning to build housing on a street. There are $n$ spots available on the street on which you can build a house. The spots are labeled from $1$ to $n$ from left to right. In each spot, you can build a house with an integer height between $0$ and $h$.

In each spot, if a house has height $a$, you will gain $a^2$ dollars from it.

The city has $m$ zoning restrictions. The $i$-th restriction says that the tallest house from spots $l_i$ to $r_i$ (inclusive) must be at most $x_i$.

You would like to build houses to maximize your profit. Determine the maximum profit possible.


-----Input-----

The first line contains three integers $n$, $h$, and $m$ ($1 \leq n,h,m \leq 50$) — the number of spots, the maximum height, and the number of restrictions.

Each of the next $m$ lines contains three integers $l_i$, $r_i$, and $x_i$ ($1 \leq l_i \leq r_i \leq n$, $0 \leq x_i \leq h$) — left and right limits (inclusive) of the $i$-th restriction and the maximum possible height in that range.


-----Output-----

Print a single integer, the maximum profit you can make.


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

Output
14

Input
4 10 2
2 3 8
3 4 7

Output
262



-----Note-----

In the first example, there are $3$ houses, the maximum height of a house is $3$, and there are $3$ restrictions. The first restriction says the tallest house between $1$ and $1$ must be at most $1$. The second restriction says the tallest house between $2$ and $2$ must be at most $3$. The third restriction says the tallest house between $3$ and $3$ must be at most $2$.

In this case, it is optimal to build houses with heights $[1, 3, 2]$. This fits within all the restrictions. The total profit in this case is $1^2 + 3^2 + 2^2 = 14$.

In the second example, there are $4$ houses, the maximum height of a house is $10$, and there are $2$ restrictions. The first restriction says the tallest house from $2$ to $3$ must be at most $8$. The second restriction says the tallest house from $3$ to $4$ must be at most $7$.

In this case, it's optimal to build houses with heights $[10, 8, 7, 7]$. We get a profit of $10^2+8^2+7^2+7^2 = 262$. Note that there are two restrictions on house $3$ and both of them must be satisfied. Also, note that even though there isn't any explicit restrictions on house $1$, we must still limit its height to be at most $10$ ($h=10$).

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got two numbers. As long as they are both larger than zero, they go through the same operation: subtract the lesser number from the larger one. If they equal substract one number from the another. For example, one operation transforms pair (4,17) to pair (4,13), it transforms (5,5) to (0,5).

You've got some number of pairs (*a**i*,<=*b**i*). How many operations will be performed for each of them?

Input Specification:
The first line contains the number of pairs *n* (1<=<=≤<=<=*n*<=<=≤<=<=1000). Then follow *n* lines, each line contains a pair of positive integers *a**i*,<=*b**i* (1<=<=≤<=<=*a**i*,<=<=*b**i*<=<=≤<=<=109).

Output Specification:
Print the sought number of operations for each pair on a single line.

Demo Input:
['2\n4 17\n7 987654321\n']

Demo Output:
['8\n141093479\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
How many days are we represented in a foreign country?

My colleagues make business trips to a foreign country. We must find the number of days our company is represented in a country. Every day that one or more colleagues are present in the country is a day that the company is represented. A single day cannot count for more than one day.

Write a function that recieves a list of pairs and returns the number of days that the company is represented in the foreign country. The first number of the pair is the number of the day of arrival and the second number of the pair is the day of departure of someone who travels, i.e. 1 january is number 1 and 31 of december is 365.

Example:
```python
days_represented([[10,17],[200,207]])
```

Returns 16 because there are two trips of 8 days, which add up to 16.

Happy coding and rank this kata if you wish ;-)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A soldier wants to buy w bananas in the shop. He has to pay k dollars for the first banana, 2k dollars for the second one and so on (in other words, he has to pay i·k dollars for the i-th banana). 

He has n dollars. How many dollars does he have to borrow from his friend soldier to buy w bananas?


-----Input-----

The first line contains three positive integers k, n, w (1  ≤  k, w  ≤  1000, 0 ≤ n ≤ 10^9), the cost of the first banana, initial number of dollars the soldier has and number of bananas he wants. 


-----Output-----

Output one integer — the amount of dollars that the soldier must borrow from his friend. If he doesn't have to borrow money, output 0.


-----Examples-----
Input
3 17 4

Output
13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a very simple problem. You are given $N$ points. Some points may be repeated. The weight (distance) between two points is given by the Manhattan distance between the two points. Find the weight of a Minimum Spanning Tree that spans these $N$ points.

-----Input-----
The input consists of:
 - One line with one integer $N$ ($1 \leq N \leq 100000$), the number of points,
 - $N$ lines each with two integers $x$ and $y$ ($0 \leq x,y < 1000$), the coordinates of each point.

-----Output-----
Output one line with a single integer: The weight of a Minimum Spanning Tree that spans these $N$ points.

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

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Professor GukiZ was playing with arrays again and accidentally discovered new function, which he called *GukiZiana*. For given array *a*, indexed with integers from 1 to *n*, and number *y*, *GukiZiana*(*a*,<=*y*) represents maximum value of *j*<=-<=*i*, such that *a**j*<==<=*a**i*<==<=*y*. If there is no *y* as an element in *a*, then *GukiZiana*(*a*,<=*y*) is equal to <=-<=1. GukiZ also prepared a problem for you. This time, you have two types of queries: 
 1.  First type has form 1 *l* *r* *x* and asks you to increase values of all *a**i* such that *l*<=≤<=*i*<=≤<=*r* by the non-negative integer *x*. 1.  Second type has form 2 *y* and asks you to find value of *GukiZiana*(*a*,<=*y*). 
For each query of type 2, print the answer and make GukiZ happy!

Input Specification:
The first line contains two integers *n*, *q* (1<=≤<=*n*<=≤<=5<=*<=105,<=1<=≤<=*q*<=≤<=5<=*<=104), size of array *a*, and the number of queries. 

The second line contains *n* integers *a*1,<=*a*2,<=... *a**n* (1<=≤<=*a**i*<=≤<=109), forming an array *a*. 

Each of next *q* lines contain either four or two numbers, as described in statement:

If line starts with 1, then the query looks like 1 *l* *r* *x* (1<=≤<=*l*<=≤<=*r*<=≤<=*n*, 0<=≤<=*x*<=≤<=109), first type query.

If line starts with 2, then th query looks like 2 *y* (1<=≤<=*y*<=≤<=109), second type query.

Output Specification:
For each query of type 2, print the value of *GukiZiana*(*a*,<=*y*), for *y* value for that query.

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arpa is taking a geometry exam. Here is the last problem of the exam.

You are given three points a, b, c.

Find a point and an angle such that if we rotate the page around the point by the angle, the new position of a is the same as the old position of b, and the new position of b is the same as the old position of c.

Arpa is doubting if the problem has a solution or not (i.e. if there exists a point and an angle satisfying the condition). Help Arpa determine if the question has a solution or not.


-----Input-----

The only line contains six integers a_{x}, a_{y}, b_{x}, b_{y}, c_{x}, c_{y} (|a_{x}|, |a_{y}|, |b_{x}|, |b_{y}|, |c_{x}|, |c_{y}| ≤ 10^9). It's guaranteed that the points are distinct.


-----Output-----

Print "Yes" if the problem has a solution, "No" otherwise.

You can print each letter in any case (upper or lower).


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

Output
Yes

Input
1 1 0 0 1000 1000

Output
No



-----Note-----

In the first sample test, rotate the page around (0.5, 0.5) by $90^{\circ}$.

In the second sample test, you can't find any solution.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an encoded string, return it's decoded string.


The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.


You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].


Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string `S` and a character `C`, return an array of integers representing the shortest distance from the current character in `S` to `C`.

### Notes

* All letters will be lowercase.
* If the string is empty, return an empty array.
* If the character is not present, return an empty array.

## Examples

```python
shortest_to_char("lovecodewars", "e") == [3, 2, 1, 0, 1, 2, 1, 0, 1, 2, 3, 4]
shortest_to_char("aaaabbbb", "b") == [4, 3, 2, 1, 0, 0, 0, 0]
shortest_to_char("", "b") == []
shortest_to_char("abcde", "") == []
```

___

If you liked it, please rate  :D

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Measuring Lengths in Baden

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Lengths are measures in Baden in inches and feet. To a length from centimeters it is enough to know that an inch equals three centimeters in Baden and one foot contains 12 inches.

You are given a length equal to *n* centimeters. Your task is to convert it to feet and inches so that the number of feet was maximum. The result should be an integer rounded to the closest value containing an integral number of inches.

Note that when you round up, 1 cm rounds up to 0 inches and 2 cm round up to 1 inch.

Input Specification:
The only line contains an integer *n* (1<=≤<=*n*<=≤<=10000).

Output Specification:
Print two non-negative space-separated integers *a* and *b*, where *a* is the numbers of feet and *b* is the number of inches.

Demo Input:
['42\n', '5\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have N bamboos. The lengths (in centimeters) of these are l_1, l_2, ..., l_N, respectively.
Your objective is to use some of these bamboos (possibly all) to obtain three bamboos of length A, B, C. For that, you can use the following three kinds of magics any number:
 - Extension Magic: Consumes 1 MP (magic point). Choose one bamboo and increase its length by 1.
 - Shortening Magic: Consumes 1 MP. Choose one bamboo of length at least 2 and decrease its length by 1.
 - Composition Magic: Consumes 10 MP. Choose two bamboos and combine them into one bamboo. The length of this new bamboo is equal to the sum of the lengths of the two bamboos combined. (Afterwards, further magics can be used on this bamboo.)
At least how much MP is needed to achieve the objective?

-----Constraints-----
 - 3 \leq N \leq 8
 - 1 \leq C < B < A \leq 1000
 - 1 \leq l_i \leq 1000
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N A B C
l_1
l_2
:
l_N

-----Output-----
Print the minimum amount of MP needed to achieve the objective.

-----Sample Input-----
5 100 90 80
98
40
30
21
80

-----Sample Output-----
23

We are obtaining three bamboos of lengths 100, 90, 80 from five bamboos 98, 40, 30, 21, 80. We already have a bamboo of length 80, and we can obtain bamboos of lengths 100, 90 by using the magics as follows at the total cost of 23 MP, which is optimal.
 - Use Extension Magic twice on the bamboo of length 98 to obtain a bamboo of length 100. (MP consumed: 2)
 - Use Composition Magic on the bamboos of lengths 40, 30 to obtain a bamboo of length 70. (MP consumed: 10)
 - Use Shortening Magic once on the bamboo of length 21 to obtain a bamboo of length 20. (MP consumed: 1)
 - Use Composition Magic on the bamboo of length 70 obtained in step 2 and the bamboo of length 20 obtained in step 3 to obtain a bamboo of length 90. (MP consumed: 10)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Pr and Ms. Ad are at $a$ and $b$ respectively on an infinite number line. Mr. Pr wants to meet Ms. Ad.
Mr. Pr can choose to move  $c$ or $d$ units in 1 second. If Mr. Pr moves $c$ units then Ms. Ad will move $d$ units and vice versa. (Both of them always moved in positive x-direction)
You have to determine if Mr. Pr can meet with Ms. Ad after some integral amount of time, given that Mr. Pr chooses optimally. Note that meeting after a fractional amount of time does not count.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains four space separated integers, $a$, $b$, $c$, and $d$.

-----Output:-----
- For each test case, output a single line containing "YES" if Mr. Pr meets with Ms. Ad, otherwise "NO".

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq a,b,c,d \leq 10^9$

-----Sample Input:-----
2
3 4 1 2
10 20 3 7

-----Sample Output:-----
YES
NO

-----Explanation:-----
In the first test case, Mr. Pr will move 2 units in the first second and Ms. Ad moves 1 unit simultaneously and they meet. 
In the second test case, it is impossible to meet (fractional time is not allowed).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hamed has recently found a string t and suddenly became quite fond of it. He spent several days trying to find all occurrences of t in other strings he had. Finally he became tired and started thinking about the following problem. Given a string s how many ways are there to extract k ≥ 1 non-overlapping substrings from it such that each of them contains string t as a substring? More formally, you need to calculate the number of ways to choose two sequences a_1, a_2, ..., a_{k} and b_1, b_2, ..., b_{k} satisfying the following requirements:

  k ≥ 1  $\forall i(1 \leq i \leq k) 1 \leq a_{i}, b_{i} \leq|s|$  $\forall i(1 \leq i \leq k) b_{i} \geq a_{i}$  $\forall i(2 \leq i \leq k) a_{i} > b_{i - 1}$  $\forall i(1 \leq i \leq k)$  t is a substring of string s_{a}_{i}s_{a}_{i} + 1... s_{b}_{i} (string s is considered as 1-indexed). 

As the number of ways can be rather large print it modulo 10^9 + 7.


-----Input-----

Input consists of two lines containing strings s and t (1 ≤ |s|, |t| ≤ 10^5). Each string consists of lowercase Latin letters.


-----Output-----

Print the answer in a single line.


-----Examples-----
Input
ababa
aba

Output
5

Input
welcometoroundtwohundredandeightytwo
d

Output
274201

Input
ddd
d

Output
12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Many people are aware of DMCA – Digital Millennium Copyright Act. But another recently proposed DMCA – Digital Millennium Calculation Act – is much less known.

In this problem you need to find a root of a number according to this new DMCA law.

Input

The input contains a single integer a (1 ≤ a ≤ 1000000).

Output

Output the result – an integer number.

Examples

Input


1


Output


1


Input


81


Output


9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dinesh has been appointed as a Civil engineer of Jamshedpur city. He has selected some locations in the city for the road construction.
For simplicity he numbered those locations as 0,1,2,3,....500. He constructed roads between various pairs of location(say A and B ) and with the permission from the government,fixed the cost for travelling between those pair of locations from either end as W unit.

After completion of his project he  wants to find the minimum cost for travelling from location U (source) to Q number of other locations (destination).

Input

First line contains N ,the number of roads that Dinesh constructed.

Next N line contains three integers A ,B, and W.

A and B represent the locations between which the road was constructed and W is the fixed cost for travelling from A to B or from B to A.

Next line contains a number U from where Dinesh wants to travel to other locations.

Next line contains Q , the number of queries (finding cost) that he wants to perform.

Next Q lines contain an integer V (destination) for which minimum cost is to be found from U.

Output

Print the required answer in each line.

Note :If he can't travel from location U to V by any means then, print "NO PATH" without quotes.

Constraints:

1 ≤ N ≤ 500

0 ≤ A,B ≤ 500

1 ≤ W ≤ 100

0 ≤ U,V ≤ 500

1 ≤ Q ≤ 500

SAMPLE INPUT
7
0 1 4
0 3 8
1 4 1
1 2 2
4 2 3
2 5 3
3 4 2
0
4
1
4
5
7

SAMPLE OUTPUT
4
5
9
NO PATH

Explanation

Query #1

0->1: cost =4

Query #2

0->4= 0->1->4 cost=4+1=5

Query #3

0->5= 0->1->2->5 cost=4+2+3=9

Query #4

0->7= no path exist between 0 and 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every evening, little Ivica sends secret messages to little Marica through e-mail. Knowing Ivica’s e-letter travels unguarded through the network on its way to Marica’s e-mailbox, they have decided to encrypt every message using the following algorithm:
 - Suppose Ivica’s message consists of $N$ characters.
 - Ivica must first find a matrix consisting of $R$ rows and $C$ columns such that $R \le C$ and $R \cdot C = N$. If there is more than one such matrix, Ivica chooses the one with the most rows.
 - Ivica writes his message into the matrix in row-major order. In other words, he writes the first segment of the message into the first row, the second segment into the second row and so on.
 - The message he sends to Marica is the matrix read in column-major order.

For instance, suppose Ivica wants to send the message “bombonisuuladici” containing 16 letters. He can use a $1 \times 16$, $2 \times 8$, or $4 \times 4$ matrix. Of these, the $4 \times 4$ has the most rows. When the message is written into it, the matrix looks like this, and the encrypted message becomes “boudonuimilcbsai”.

b

o

m

b

o

n

i

s

u

u

l

a

d

i

c

i

Marica has grown tired of spending her precious time deciphering Ivica’s messages, so you must write a program to do it for her.

-----Input-----
The input contains the received message, a string of lowercase letters of the English alphabet (with no spaces). The number of letters will be between 1 and 100.

-----Output-----
Output the original (decrypted) message.

-----Examples-----
Sample Input 1:
bok
Sample Output 1:
bok

Sample Input 2:
koaski
Sample Output 2:
kakosi

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Small, but very brave, mouse Brain was not accepted to summer school of young villains. He was upset and decided to postpone his plans of taking over the world, but to become a photographer instead.

As you may know, the coolest photos are on the film (because you can specify the hashtag #film for such).

Brain took a lot of colourful pictures on colored and black-and-white film. Then he developed and translated it into a digital form. But now, color and black-and-white photos are in one folder, and to sort them, one needs to spend more than one hour!

As soon as Brain is a photographer not programmer now, he asks you to help him determine for a single photo whether it is colored or black-and-white.

Photo can be represented as a matrix sized n × m, and each element of the matrix stores a symbol indicating corresponding pixel color. There are only 6 colors:   'C' (cyan) 'M' (magenta) 'Y' (yellow) 'W' (white) 'G' (grey) 'B' (black) 

The photo is considered black-and-white if it has only white, black and grey pixels in it. If there are any of cyan, magenta or yellow pixels in the photo then it is considered colored.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100) — the number of photo pixel matrix rows and columns respectively.

Then n lines describing matrix rows follow. Each of them contains m space-separated characters describing colors of pixels in a row. Each character in the line is one of the 'C', 'M', 'Y', 'W', 'G' or 'B'.


-----Output-----

Print the "#Black&White" (without quotes), if the photo is black-and-white and "#Color" (without quotes), if it is colored, in the only line.


-----Examples-----
Input
2 2
C M
Y Y

Output
#Color
Input
3 2
W W
W W
B B

Output
#Black&White
Input
1 1
W

Output
#Black&White

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