vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Pandey needs your help. As you know, he is on the quest to save the princess. After traveling for a number of days, he has finally reached the palace, but one last battle remains to be fought. However he has only one unit of energy left in him. To win the battle, he needs all the energy he can get. So he is searching for the Wizard of GJ.

GJ agrees to help him if he is willing to play his game. GJ will give him B balloons, one at a time. For each balloon, he will ask Pandey if he wants to take the balloon. If Pandey accepts, his energy level will be changed according to the value and type of the balloon. Otherwise, the balloon is lost forever. 

GJ is hoping to enjoy seeing Pandey regret his choices after every move because Pandey will only know the current balloon offered to him and will have no knowledge of the following ones. However, unknown to GJ, Pandey's brother Vajpayee had been working undercover as GJ's apprentice and knew in advance the values on each of the balloons and also the order in which he would show them to Pandey. So, Pandey knows all the details, and now he needs you to help him select the balloons so that he can maximize his energy. 

Each balloon may be of one of the following types: 
+ X : Taking this balloon will add X to the current energy of Pandey.
- X :  Taking this balloon will subtract X from the current energy of Pandey.
* X :  Taking this balloon will multiply X to the current energy of Pandey.
/ X :  Taking this balloon will divide (integer division) the current energy of Pandey by X.
To simulate this balloon, you can use a standard division operator in most of programming languages.
E.g. 7 / 4 = 1 and (-7) / 4 = -1.
N : Taking this balloon replaces Pandey's energy by its negated value.

Input:
The first line contains T which is the number of test cases.
The first line of every test case contains an integer B which represents the number of magic balloons offered to Pandey by GJ.
B lines follow, each containing one of the 5 possible balloon types in the order in which they are shown to Pandey.

Output:
For each test case, output a line containing the maximum energy Pandey can make with the given balloons offered by GJ. Pandey starts with energy equal to one.

Constraints:

1 ≤ T ≤ 10
1 ≤ B ≤ 50
1 ≤ X ≤ 30
You can assume that it's impossible to get the energy greater than 10^18 or lower than -10^18.

Scoring:

 1 ≤ B ≤ 16 (40 pts)
Original Constraints (60 pts)

SAMPLE INPUT
2
3
N
- 2
N
3
- 1
* 4
/ 2


SAMPLE OUTPUT
3
4

Explanation

Case 1: The maximum energy obtained by Pandey is if he selects all the 3 balloons. So, his energy changes in this manner : 1 -> -1 -> -3 -> 3

Case 2: The maximum energy obtained by Pandey is if he selects only the second balloon (the one with of type "* 4".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The knight is standing in front of a long and narrow hallway. A princess is waiting at the end of it.

In a hallway there are three doors: a red door, a green door and a blue door. The doors are placed one after another, however, possibly in a different order. To proceed to the next door, the knight must first open the door before.

Each door can be only opened with a key of the corresponding color. So three keys: a red key, a green key and a blue key — are also placed somewhere in the hallway. To open the door, the knight should first pick up the key of its color.

The knight has a map of the hallway. It can be transcribed as a string, consisting of six characters:

R, G, B — denoting red, green and blue doors, respectively;

r, g, b — denoting red, green and blue keys, respectively.

Each of these six characters appears in the string exactly once.

The knight is standing at the beginning of the hallway — on the left on the map.

Given a map of the hallway, determine if the knight can open all doors and meet the princess at the end of the hallway.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 720$) — the number of testcases.

Each testcase consists of a single string. Each character is one of R, G, B (for the doors), r, g, b (for the keys), and each of them appears exactly once.


-----Output-----

For each testcase, print YES if the knight can open all doors. Otherwise, print NO.


-----Examples-----

Input
4
rgbBRG
RgbrBG
bBrRgG
rgRGBb
Output
YES
NO
YES
NO


-----Note-----

In the first testcase, the knight first collects all keys, then opens all doors with them.

In the second testcase, there is a red door right in front of the knight, but he doesn't have a key for it.

In the third testcase, the key to each door is in front of each respective door, so the knight collects the key and uses it immediately three times.

In the fourth testcase, the knight can't open the blue door.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two non-negative integers L and R.
We will choose two integers i and j such that L \leq i < j \leq R.
Find the minimum possible value of (i \times j) \mbox{ mod } 2019.

-----Constraints-----
 - All values in input are integers.
 - 0 \leq L < R \leq 2 \times 10^9

-----Input-----
Input is given from Standard Input in the following format:
L R

-----Output-----
Print the minimum possible value of (i \times j) \mbox{ mod } 2019 when i and j are chosen under the given condition.

-----Sample Input-----
2020 2040

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

When (i, j) = (2020, 2021), (i \times j) \mbox{ mod } 2019  = 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice likes word "nineteen" very much. She has a string s and wants the string to contain as many such words as possible. For that reason she can rearrange the letters of the string.

For example, if she has string "xiineteenppnnnewtnee", she can get string "xnineteenppnineteenw", containing (the occurrences marked) two such words. More formally, word "nineteen" occurs in the string the number of times you can read it starting from some letter of the string. Of course, you shouldn't skip letters.

Help her to find the maximum number of "nineteen"s that she can get in her string.


-----Input-----

The first line contains a non-empty string s, consisting only of lowercase English letters. The length of string s doesn't exceed 100.


-----Output-----

Print a single integer — the maximum number of "nineteen"s that she can get in her string.


-----Examples-----
Input
nniinneetteeeenn

Output
2
Input
nneteenabcnneteenabcnneteenabcnneteenabcnneteenabcii

Output
2
Input
nineteenineteen

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
During its early years, Raushan's Candy Store offered only two flavors of candies - Coconut and Spearmint. The Candy Store is popular for its "2 Coconut 1 Spearmint" promo. You can buy a strip containing one Spearmint candy and two Coconuts for just the price of the Coconuts! Talk about a steal!

Raushan has a machine that packs candies into capsules. These were known as candy strips. He just enters what flavors goes into a strip and the machine does it. But one day, the machine just malfunctioned and packed the candies randomly into one big strip. But that day, a high demand for the promo was met. And Raushan went into a panic.

Now, Raushan's idea is this: instead of throwing away the big strip and start anew, he should just trim the strip so that for every Spearmint candy, there's two Coconut candies in the strip.

For example, if the strip was SSCCSCSCC, he could trim it from the left by removing the two Spearmint candies. Then, trim it from the right and remove one Coconut candy. Thus, he's left with a strip looking like CCSCSC. This strip has one Spearmint candy for every two Coconut candies.

As he recalls the fond memories of his newly-opened shop, he wondered how many ways he could trim each strip so that he could sell the remainder under the "2 Coconut 1 Spearmint" promo.

Input 
The first line contains a single integer, which is T.     

The second line contains a string of length T, consisting of S and C.

Output 
Output a single line containing how many ways he can trim the strips in order to make it sellable under the "2 Coconut 1 Spearmint" promo.

Constraints 
1 ≤ N ≤ 10^6

SAMPLE INPUT
4
SCCS

SAMPLE OUTPUT
2

Explanation

The 2 possible trimmings are:
xCCS
SCCx

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
*This kata is based on [Project Euler Problem #349](https://projecteuler.net/problem=349). You may want to start with solving [this kata](https://www.codewars.com/kata/langtons-ant) first.*

---

[Langton's ant](https://en.wikipedia.org/wiki/Langton%27s_ant) moves on a regular grid of squares that are coloured either black or white.
The ant is always oriented in one of the cardinal directions (left, right, up or down) and moves  according to the following rules:
- if it is on a black square, it flips the colour of the square to white, rotates 90 degrees counterclockwise and moves forward one square.
- if it is on a white square, it flips the colour of the square to black, rotates 90 degrees clockwise and moves forward one square.

Starting with a grid that is **entirely white**, how many squares are black after `n` moves of the ant?

**Note:** `n` will go as high as 10^(20)

---

## My other katas

If you enjoyed this kata then please try [my other katas](https://www.codewars.com/collections/katas-created-by-anter69)! :-)

#### *Translations are welcome!*

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

President K decided to make a flag for IOI 2016 in Russia. Chairman K first took out the old flag from the warehouse. This flag is divided into squares of N rows and M columns, and each square is painted in one of white, blue, and red.

Chairman K is trying to repaint some of the squares on this flag to make it the Russian flag. However, the Russian flag in this problem is as follows.

* Several lines (one or more lines) from the top are all painted in white.
* The next few lines (one or more lines) are all painted in blue.
* All the cells in the other lines (one or more lines) are painted in red.



Find the minimum number of squares that President K needs to repaint to turn the old flag into a Russian flag.

input

The input consists of 1 + N lines.

On the first line, two integers N and M (3 ≤ N ≤ 50, 3 ≤ M ≤ 50) are written separated by a blank. This means that the flags are separated by N rows and M columns.

The following N lines each contain a string of M characters, which represents the color information painted in the squares of the old flag. The jth character (1 ≤ i ≤ N, 1 ≤ j ≤ M) on the i-th line of the N-line represents the color of the cell on the i-th line and j-th column of the old flag. It is either B'or'R'. 'W' stands for white,'B' stands for blue, and'R' stands for red.

output

Output in one line the minimum number of squares that President K needs to repaint to turn the old flag into a Russian flag.

Input / output example

Input example 1


4 5
WRWRW
BWRWB
WRWRW
RWBWR


Output example 1


11


Input example 2


6 14
WWWWWWWWWWWWWW
WBBBWWRRWWBBBW
WWBWWRRRRWWBWW
BWBWWRRRRWWBWW
WBBWWWRRWWBBBW
WWWWWWWWWWWWWW


Output example 2


44


In I / O example 1, the old flag is colored as shown in the figure below.

fig01

In the figure below, repaint the 11 squares with an'X'.

fig02

This makes it possible to make the Russian flag as shown in the figure below.

fig03

Since it is not possible to make a Russian flag by repainting less than 11 squares, 11 is output.

In I / O example 2, the old flag is colored as shown in the figure below.

fig04

Creative Commons License

Information Olympics Japan Committee work "15th Japan Information Olympics JOI 2015/2016 Qualifying Competition Tasks"





Example

Input

4 5
WRWRW
BWRWB
WRWRW
RWBWR


Output

11

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Andrewid the Android is a galaxy-famous detective. He is now investigating the case of vandalism at the exhibition of contemporary art.

The main exhibit is a construction of *n* matryoshka dolls that can be nested one into another. The matryoshka dolls are numbered from 1 to *n*. A matryoshka with a smaller number can be nested in a matryoshka with a higher number, two matryoshkas can not be directly nested in the same doll, but there may be chain nestings, for example, 1<=→<=2<=→<=4<=→<=5. 

In one second, you can perform one of the two following operations:
 -  Having a matryoshka *a* that isn't nested in any other matryoshka and a matryoshka *b*, such that *b* doesn't contain any other matryoshka and is not nested in any other matryoshka, you may put *a* in *b*; -  Having a matryoshka *a* directly contained in matryoshka *b*, such that *b* is not nested in any other matryoshka, you may get *a* out of *b*. 
According to the modern aesthetic norms the matryoshka dolls on display were assembled in a specific configuration, i.e. as several separate chains of nested matryoshkas, but the criminal, following the mysterious plan, took out all the dolls and assembled them into a single large chain (1<=→<=2<=→<=...<=→<=*n*). In order to continue the investigation Andrewid needs to know in what minimum time it is possible to perform this action.

Input Specification:
The first line contains integers *n* (1<=≤<=*n*<=≤<=105) and *k* (1<=≤<=*k*<=≤<=105) — the number of matryoshkas and matryoshka chains in the initial configuration.

The next *k* lines contain the descriptions of the chains: the *i*-th line first contains number *m**i* (1<=≤<=*m**i*<=≤<=*n*), and then *m**i* numbers *a**i*1,<=*a**i*2,<=...,<=*a**im**i* — the numbers of matryoshkas in the chain (matryoshka *a**i*1 is nested into matryoshka *a**i*2, that is nested into matryoshka *a**i*3, and so on till the matryoshka *a**im**i* that isn't nested into any other matryoshka).

It is guaranteed that *m*1<=+<=*m*2<=+<=...<=+<=*m**k*<==<=*n*, the numbers of matryoshkas in all the chains are distinct, in each chain the numbers of matryoshkas follow in the ascending order.

Output Specification:
In the single line print the minimum number of seconds needed to assemble one large chain from the initial configuration.

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

Demo Output:
['1\n', '10\n']

Note:
In the first sample test there are two chains: 1 → 2 and 3. In one second you can nest the first chain into the second one and get 1 → 2 → 3.

In the second sample test you need to disassemble all the three chains into individual matryoshkas in 2 + 1 + 1 = 4 seconds and then assemble one big chain in 6 seconds.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Paul is at the orchestra. The string section is arranged in an r × c rectangular grid and is filled with violinists with the exception of n violists. Paul really likes violas, so he would like to take a picture including at least k of them. Paul can take a picture of any axis-parallel rectangle in the orchestra. Count the number of possible pictures that Paul can take.

Two pictures are considered to be different if the coordinates of corresponding rectangles are different.


-----Input-----

The first line of input contains four space-separated integers r, c, n, k (1 ≤ r, c, n ≤ 10, 1 ≤ k ≤ n) — the number of rows and columns of the string section, the total number of violas, and the minimum number of violas Paul would like in his photograph, respectively.

The next n lines each contain two integers x_{i} and y_{i} (1 ≤ x_{i} ≤ r, 1 ≤ y_{i} ≤ c): the position of the i-th viola. It is guaranteed that no location appears more than once in the input.


-----Output-----

Print a single integer — the number of photographs Paul can take which include at least k violas. 


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

Output
4

Input
3 2 3 3
1 1
3 1
2 2

Output
1

Input
3 2 3 2
1 1
3 1
2 2

Output
4



-----Note-----

We will use '*' to denote violinists and '#' to denote violists.

In the first sample, the orchestra looks as follows 

*#

**

 Paul can take a photograph of just the viola, the 1 × 2 column containing the viola, the 2 × 1 row containing the viola, or the entire string section, for 4 pictures total.

In the second sample, the orchestra looks as follows 

#*

*#

#*

 Paul must take a photograph of the entire section.

In the third sample, the orchestra looks the same as in the second sample.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].
Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.
If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.
 
Example 1:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

Example 2:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000

Example 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.

 
Constraints:

2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
There is at most one edge between every two nodes.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a positive integer $n$, written without leading zeroes (for example, the number 04 is incorrect). 

In one operation you can delete any digit of the given integer so that the result remains a positive integer without leading zeros.

Determine the minimum number of operations that you need to consistently apply to the given integer $n$ to make from it the square of some positive integer or report that it is impossible.

An integer $x$ is the square of some positive integer if and only if $x=y^2$ for some positive integer $y$.

Input Specification:
The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{9}$). The number is given without leading zeroes.

Output Specification:
If it is impossible to make the square of some positive integer from $n$, print -1. In the other case, print the minimal number of operations required to do it.

Demo Input:
['8314\n', '625\n', '333\n']

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

Note:
In the first example we should delete from $8314$ the digits $3$ and $4$. After that $8314$ become equals to $81$, which is the square of the integer $9$.

In the second example the given $625$ is the square of the integer $25$, so you should not delete anything. 

In the third example it is impossible to make the square from $333$, so the answer is -1.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In the evening, after the contest Ilya was bored, and he really felt like maximizing. He remembered that he had a set of *n* sticks and an instrument. Each stick is characterized by its length *l**i*.

Ilya decided to make a rectangle from the sticks. And due to his whim, he decided to make rectangles in such a way that maximizes their total area. Each stick is used in making at most one rectangle, it is possible that some of sticks remain unused. Bending sticks is not allowed.

Sticks with lengths *a*1, *a*2, *a*3 and *a*4 can make a rectangle if the following properties are observed:
 -  *a*1<=≤<=*a*2<=≤<=*a*3<=≤<=*a*4 -  *a*1<==<=*a*2 -  *a*3<==<=*a*4 
A rectangle can be made of sticks with lengths of, for example, 3 3 3 3 or 2 2 4 4. A rectangle cannot be made of, for example, sticks 5 5 5 7.

Ilya also has an instrument which can reduce the length of the sticks. The sticks are made of a special material, so the length of each stick can be reduced by at most one. For example, a stick with length 5 can either stay at this length or be transformed into a stick of length 4.

You have to answer the question — what maximum total area of the rectangles can Ilya get with a file if makes rectangles from the available sticks?

Input Specification:
The first line of the input contains a positive integer *n* (1<=≤<=*n*<=≤<=105) — the number of the available sticks.

The second line of the input contains *n* positive integers *l**i* (2<=≤<=*l**i*<=≤<=106) — the lengths of the sticks.

Output Specification:
The first line of the output must contain a single non-negative integer — the maximum total area of the rectangles that Ilya can make from the available sticks.

Demo Input:
['4\n2 4 4 2\n', '4\n2 2 3 5\n', '4\n100003 100004 100005 100006\n']

Demo Output:
['8\n', '0\n', '10000800015\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a rooted tree with $n$ nodes. The nodes are numbered $1..n$. The root is node $1$, and $m$ of the nodes are colored red, the rest are black.

You would like to choose a subset of nodes such that there is no node in your subset which is an ancestor of any other node in your subset. For example, if A is the parent of B and B is the parent of C, then you could have at most one of A, B or C in your subset. In addition, you would like exactly $k$ of your chosen nodes to be red.

If exactly $m$ of the nodes are red, then for all $k=0..m$, figure out how many ways you can choose subsets with $k$ red nodes, and no node is an ancestor of any other node.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line with two integers $n$ ($1 \le n \le 2 \times 10^5$) and $m$ ($0 \le m \le min(10^3,\ n)$), where $n$ is the number of nodes in the tree, and $m$ is the number of nodes which are red. The nodes are numbered $1..n$.

Each of the next $n-1$ lines will contain a single integer $p$ ($1 \le p \le n$), which is the number of the parent of this node. The nodes are listed in order, starting with node $2$, then node $3$, and so on. Node $1$ is skipped, since it is the root. It is guaranteed that the nodes form a single tree, with a single root at node $1$ and no cycles.

Each of the next $m$ lines will contain single integer $r$ ($1 \le r \le n$). These are the numbers of the red nodes. No value of $r$ will be repeated.

-----Output-----
Output $m+1$ lines, corresponding to the number of subsets satisfying the given criteria with a number of red nodes equal to $k=0..m$, in that order. Output this number modulo $10^9+7$.

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

Sample Input 2:
4 4
1
1
1
1
2
3
4
Sample Output 2:
1
4
3
1
0

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