vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Unbearable Controversy of Being

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Tomash keeps wandering off and getting lost while he is walking along the streets of Berland. It's no surprise! In his home town, for any pair of intersections there is exactly one way to walk from one intersection to the other one. The capital of Berland is very different!

Tomash has noticed that even simple cases of ambiguity confuse him. So, when he sees a group of four distinct intersections *a*, *b*, *c* and *d*, such that there are two paths from *a* to *c* — one through *b* and the other one through *d*, he calls the group a "damn rhombus". Note that pairs (*a*,<=*b*), (*b*,<=*c*), (*a*,<=*d*), (*d*,<=*c*) should be directly connected by the roads. Schematically, a damn rhombus is shown on the figure below:

Other roads between any of the intersections don't make the rhombus any more appealing to Tomash, so the four intersections remain a "damn rhombus" for him.

Given that the capital of Berland has *n* intersections and *m* roads and all roads are unidirectional and are known in advance, find the number of "damn rhombi" in the city.

When rhombi are compared, the order of intersections *b* and *d* doesn't matter.

Input Specification:
The first line of the input contains a pair of integers *n*, *m* (1<=≤<=*n*<=≤<=3000,<=0<=≤<=*m*<=≤<=30000) — the number of intersections and roads, respectively. Next *m* lines list the roads, one per line. Each of the roads is given by a pair of integers *a**i*,<=*b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*;*a**i*<=≠<=*b**i*) — the number of the intersection it goes out from and the number of the intersection it leads to. Between a pair of intersections there is at most one road in each of the two directions.

It is not guaranteed that you can get from any intersection to any other one.

Output Specification:
Print the required number of "damn rhombi".

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

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Not simply beatiful strings

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let's call a string adorable if its letters can be realigned in such a way that they form two consequent groups of equal symbols (note that different groups must contain different symbols). For example, ababa is adorable (you can transform it to aaabb, where the first three letters form a group of *a*-s and others — a group of *b*-s), but cccc is not since in each possible consequent partition letters in these two groups coincide.

You're given a string *s*. Check whether it can be split into two non-empty subsequences such that the strings formed by these subsequences are adorable. Here a subsequence is an arbitrary set of indexes of the string.

Input Specification:
The only line contains *s* (1<=≤<=|*s*|<=≤<=105) consisting of lowercase latin letters.

Output Specification:
Print «Yes» if the string can be split according to the criteria above or «No» otherwise.

Each letter can be printed in arbitrary case.

Demo Input:
['ababa\n', 'zzcxx\n', 'yeee\n']

Demo Output:
['Yes\n', 'Yes\n', 'No\n']

Note:
In sample case two zzcxx can be split into subsequences zc and zxx each of which is adorable.

There's no suitable partition in sample case three.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are supposed to play the rock-paper-scissors game. There are $N$ players including you.

This game consists of multiple rounds. While the rounds go, the number of remaining players decreases. In each round, each remaining player will select an arbitrary shape independently. People who show rocks win if all of the other people show scissors. In this same manner, papers win rocks, scissors win papers. There is no draw situation due to the special rule of this game: if a round is tied based on the normal rock-paper-scissors game rule, the player who has the highest programming contest rating (this is nothing to do with the round!) will be the only winner of the round. Thus, some players win and the other players lose on each round. The losers drop out of the game and the winners proceed to a new round. They repeat it until only one player becomes the winner.

Each player is numbered from $1$ to $N$. Your number is $1$. You know which shape the other $N-1$ players tend to show, that is to say, you know the probabilities each player shows rock, paper and scissors. The $i$-th player shows rock with $r_i\%$ probability, paper with $p_i\%$ probability, and scissors with $s_i\%$ probability. The rating of programming contest of the player numbered $i$ is $a_i$. There are no two players whose ratings are the same. Your task is to calculate your probability to win the game when you take an optimal strategy based on each player's tendency and rating.



Input

The input consists of a single test case formatted as follows.


$N$
$a_1$
$a_2$ $r_2$ $p_2$ $s_2$
...
$a_N$ $r_N$ $p_N$ $s_N$


The first line consists of a single integer $N$ ($2 \leq N \leq 14$). The second line consists of a single integer $a_i$ ($1 \leq a_i \leq N$). The ($i+1$)-th line consists of four integers $a_i, r_i, p_i$ and $s_i$ ($1 \leq a_i \leq N, 0 \leq r_i, p_i, s_i \leq 100,$ $r_i + p_i + s_i = 100$) for $i=2, ..., N$. It is guaranteed that $a_1, ..., a_N$ are pairwise distinct.

Output

Print the probability to win the game in one line. Your answer will be accepted if its absolute or relative error does not exceed $10^{-6}$.

Examples

Input

2
2
1 40 40 20


Output

0.8


Input

2
1
2 50 50 0


Output

0.5


Input

3
2
1 50 0 50
3 0 0 100


Output

1


Input

3
2
3 40 40 20
1 30 10 60


Output

0.27


Input

4
4
1 34 33 33
2 33 34 33
3 33 33 34


Output

0.6591870816

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
We had a string *s* consisting of *n* lowercase Latin letters. We made *k* copies of this string, thus obtaining *k* identical strings *s*1,<=*s*2,<=...,<=*s**k*. After that, in each of these strings we swapped exactly two characters (the characters we swapped could be identical, but they had different indices in the string).

You are given *k* strings *s*1,<=*s*2,<=...,<=*s**k*, and you have to restore any string *s* so that it is possible to obtain these strings by performing aforementioned operations. Note that the total length of the strings you are given doesn't exceed 5000 (that is, *k*·*n*<=≤<=5000).

Input Specification:
The first line contains two integers *k* and *n* (1<=≤<=*k*<=≤<=2500,<=2<=≤<=*n*<=≤<=5000,<=*k* · *n*<=≤<=5000) — the number of strings we obtained, and the length of each of these strings.

Next *k* lines contain the strings *s*1,<=*s*2,<=...,<=*s**k*, each consisting of exactly *n* lowercase Latin letters.

Output Specification:
Print any suitable string *s*, or -1 if such string doesn't exist.

Demo Input:
['3 4\nabac\ncaab\nacba\n', '3 4\nkbbu\nkbub\nubkb\n', '5 4\nabcd\ndcba\nacbd\ndbca\nzzzz\n']

Demo Output:
['acab\n', 'kbub\n', '-1\n']

Note:
In the first example *s*<sub class="lower-index">1</sub> is obtained by swapping the second and the fourth character in acab, *s*<sub class="lower-index">2</sub> is obtained by swapping the first and the second character, and to get *s*<sub class="lower-index">3</sub>, we swap the third and the fourth character.

In the second example *s*<sub class="lower-index">1</sub> is obtained by swapping the third and the fourth character in kbub, *s*<sub class="lower-index">2</sub> — by swapping the second and the fourth, and *s*<sub class="lower-index">3</sub> — by swapping the first and the third.

In the third example it's impossible to obtain given strings by aforementioned operations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a grid with $R$ rows (numbered $1$ through $R$) and $C$ columns (numbered $1$ through $C$). A cell in row $r$ and column $c$ is denoted by $(r, c)$. Two cells in the grid are adjacent if they have a common side. For each valid $i$ and $j$, there is a value $a_{i, j}$ written in cell $a_{i, j}$.
A cell in the grid is stable if the number of cells in the grid which are adjacent to this cell is strictly greater than the value written in this cell. The whole grid is stable if all cells in the grid are stable.
Can you determine whether the grid is stable?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $R$ and $C$.
- $R$ lines follow. For each $i$ ($1 \le i \le R$), the $i$-th of these lines contains $C$ space-separated integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, C}$.

-----Output-----
For each test case, print a single line containing the string "Stable" if the grid is stable or "Unstable" if it is unstable (without quotes).

-----Constraints-----
- $1 \le T \le 3,000$
- $3 \le R, C \le 10$
- $0 \le a_{i, j} \le 4$ for each valid $i, j$

-----Example Input-----
2
3 3
1 2 1
2 3 2
1 2 1
3 4
0 0 0 0
0 0 0 0
0 0 4 0

-----Example Output-----
Stable
Unstable

-----Explanation-----
Example case 1: Each cell of the grid is stable, so the grid is stable.
Example case 2: The cell in row $3$ and column $3$ is unstable since the number of cells adjacent to this cell is $3$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sorted array arr[] of distinct integers. Sort the array into a wave-like array(In Place).
In other words, arrange the elements into a sequence such that arr[1] >= arr[2] <= arr[3] >= arr[4] <= arr[5].....
If there are multiple solutions, find the lexicographically smallest one.
Note:The given array is sorted in ascending order, and you don't need to return anything to make changes in the original array itself.
Example 1:
Input:
n = 5
arr[] = {1,2,3,4,5}
Output: 2 1 4 3 5
Explanation: Array elements after 
sorting it in wave form are 
2 1 4 3 5.
Example 2:
Input:
n = 6
arr[] = {2,4,7,8,9,10}
Output: 4 2 8 7 10 9
Explanation: Array elements after 
sorting it in wave form are 
4 2 8 7 10 9.
Your Task:
The task is to complete the function convertToWave(), which converts the given array to a wave array.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ n ≤ 10^{6}
0 ≤ arr[i] ≤10^{7}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr of n positive integers. The task is to swap every i^{th} element of the array with (i+2)^{th} element.
Note: When passing array to function, we basically pass the reference to the array. More details here. We'll learn more about pointers and references in upcoming module.
Example:
Input:
n = 5
arr[] = 1 2 3 4 5
Output:
3 4 5 2 1
Explanation:
Swapping 1 and 3, makes the array 3 2 1 4 5.
Now, swapping 2 and 4, makes the array 
3 4 1 2 5. Again,swapping 1 and 5, makes the 
array 3 4 5 2 1.
Your Task:
Your task is to complete the function swapElements(), which should swap each ith element with (i+2)^{th} element. No need to print or return the array.
 
Expected Time Complexity: O(n)
Expected Auxilary Space: O(1)
Constraints:
1 <= N <= 10^{6}
1 <= A_{i} <= 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given nonnegative integers a and b (a ≤ b), and a positive integer x.
Among the integers between a and b, inclusive, how many are divisible by x?

-----Constraints-----
 - 0 ≤ a ≤ b ≤ 10^{18}
 - 1 ≤ x ≤ 10^{18}

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

-----Output-----
Print the number of the integers between a and b, inclusive, that are divisible by x.

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

-----Sample Output-----
3

There are three integers between 4 and 8, inclusive, that are divisible by 2: 4, 6 and 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a tree that has n nodes and n-1 edges. There are military bases on t out of the n nodes. We want to disconnect the bases as much as possible by destroying k edges. The tree will be split into k+1 regions when we destroy k edges. Given the purpose to disconnect the bases, we only consider to split in a way that each of these k+1 regions has at least one base. When we destroy an edge, we must pay destroying cost. Find the minimum destroying cost to split the tree.



Input

The input consists of multiple data sets. Each data set has the following format. The first line consists of three integers n, t, and k (1 \leq n \leq 10,000, 1 \leq t \leq n, 0 \leq k \leq t-1). Each of the next n-1 lines consists of three integers representing an edge. The first two integers represent node numbers connected by the edge. A node number is a positive integer less than or equal to n. The last one integer represents destroying cost. Destroying cost is a non-negative integer less than or equal to 10,000. The next t lines contain a distinct list of integers one in each line, and represent the list of nodes with bases. The input ends with a line containing three zeros, which should not be processed.

Output

For each test case, print its case number and the minimum destroying cost to split the tree with the case number.

Example

Input

2 2 1
1 2 1
1
2
4 3 2
1 2 1
1 3 2
1 4 3
2
3
4
0 0 0


Output

Case 1: 1
Case 2: 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob has a string $s$ consisting of lowercase English letters. He defines $s'$ to be the string after removing all "a" characters from $s$ (keeping all other characters in the same order). He then generates a new string $t$ by concatenating $s$ and $s'$. In other words, $t=s+s'$ (look at notes for an example).

You are given a string $t$. Your task is to find some $s$ that Bob could have used to generate $t$. It can be shown that if an answer exists, it will be unique.


-----Input-----

The first line of input contains a string $t$ ($1 \leq |t| \leq 10^5$) consisting of lowercase English letters.


-----Output-----

Print a string $s$ that could have generated $t$. It can be shown if an answer exists, it is unique. If no string exists, print ":(" (without double quotes, there is no space between the characters).


-----Examples-----
Input
aaaaa

Output
aaaaa

Input
aacaababc

Output
:(

Input
ababacacbbcc

Output
ababacac

Input
baba

Output
:(



-----Note-----

In the first example, we have $s = $ "aaaaa", and $s' = $ "".

In the second example, no such $s$ can work that will generate the given $t$.

In the third example, we have $s = $ "ababacac", and $s' = $ "bbcc", and $t = s + s' = $ "ababacacbbcc".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Having written another programming contest, three Rabbits decided to grab some lunch. The coach gave the team exactly k time units for the lunch break.

The Rabbits have a list of n restaurants to lunch in: the i-th restaurant is characterized by two integers f_{i} and t_{i}. Value t_{i} shows the time the Rabbits need to lunch in the i-th restaurant. If time t_{i} exceeds the time k that the coach has given for the lunch break, then the Rabbits' joy from lunching in this restaurant will equal f_{i} - (t_{i} - k). Otherwise, the Rabbits get exactly f_{i} units of joy.

Your task is to find the value of the maximum joy the Rabbits can get from the lunch, depending on the restaurant. The Rabbits must choose exactly one restaurant to lunch in. Note that the joy value isn't necessarily a positive value. 


-----Input-----

The first line contains two space-separated integers — n (1 ≤ n ≤ 10^4) and k (1 ≤ k ≤ 10^9) — the number of restaurants in the Rabbits' list and the time the coach has given them to lunch, correspondingly. Each of the next n lines contains two space-separated integers — f_{i} (1 ≤ f_{i} ≤ 10^9) and t_{i} (1 ≤ t_{i} ≤ 10^9) — the characteristics of the i-th restaurant.


-----Output-----

In a single line print a single integer — the maximum joy value that the Rabbits will get from the lunch. 


-----Examples-----
Input
2 5
3 3
4 5

Output
4

Input
4 6
5 8
3 6
2 3
2 2

Output
3

Input
1 5
1 7

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $\mbox{S}$. 

Your task is to find out whether $\mbox{S}$ is a valid regex or not.

Input Format

The first line contains integer $\mathbf{T}$, the number of test cases. 

The next $\mathbf{T}$ lines contains the string $\mbox{S}$.

Constraints

$\textbf{0}<T<100$

Output Format

Print "True" or "False" for each test case without quotes.

Sample Input
2
.*\+
.*+

Sample Output
True
False

Explanation

.*\+ : Valid regex. 

.*+: Has the error multiple repeat. Hence, it is invalid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the hit video game “Johnny5 and the Exploding Oil Cans”, you control the robot “Johnny5”. The robot can be moved one cell at a time in one of the directions up, down, left, or right on an $N \times N$ grid. One move takes one second and costs one unit of energy. It is allowed to stand still, you don’t have to move every second. If you have no energy, you can’t move. You start the game with $E$ units of energy.

The objective of the game is to collect as many oil cans as you can. Every second there may appear one or more oil cans somewhere on the grid. If Johnny5 is at a location when a can appears there he collects that can, otherwise it explodes. You score $1$ point for each oil can Johnny5 collects. If an oil can explodes in one of the four adjacent cells to where Johnny5 is located he collects the spilled oil, and you gain one unit of energy for each of them. If he does not pick up the can, and is not in one of the adjacent cells to pick up the oil, the oil disappears immediately. Note that he only gets oil from adjacent cells, and not from any cans in the same cell that he is in.

You’ve had trouble beating this game for years, but your friend just called and told you there is a way to get a list of where and when the cans will appear. Write a program that uses this information to find the maximum number of points you can get.

-----Input-----
The first line of the input consists of $5$ space-separated integers $N$, $E$, $S_ X$, $S_ Y$, $C$. These numbers give the size of the grid, the starting energy, the $x$ and $y$ coordinates where Johnny5 starts, and the number of cans.

The next $C$ lines each consist of $3$ space-separated integers $X$, $Y$, $CT$. These numbers represent the $x$ and $y$ coordinates of a can, and the time it appears there, in seconds after the start of the game.

-----Output-----
Output the maximum number of points you can score.

-----Limits-----
 - $1 \leq N \leq 500$.
 - $0 \leq E \leq 100$.
 - $0 \leq C \leq 100$.
 - $0 \leq X_ S, Y_ S, X, Y < N$.
 - $1 \leq CT \leq 100$.

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

Sample Input 2:
3 1 1 1 8
0 1 1
1 0 1
2 1 1
1 2 1
1 2 2
2 2 3
0 2 5
1 2 6
Sample Output 2:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Games on a CD

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Several years ago Tolya had *n* computer games and at some point of time he decided to burn them to CD. After that he wrote down the names of the games one after another in a circle on the CD in clockwise order. The names were distinct, the length of each name was equal to *k*. The names didn't overlap.

Thus, there is a cyclic string of length *n*·*k* written on the CD.

Several years have passed and now Tolya can't remember which games he burned to his CD. He knows that there were *g* popular games that days. All of the games he burned were among these *g* games, and no game was burned more than once.

You have to restore any valid list of games Tolya could burn to the CD several years ago.

Input Specification:
The first line of the input contains two positive integers *n* and *k* (1<=≤<=*n*<=≤<=105, 1<=≤<=*k*<=≤<=105) — the amount of games Tolya burned to the CD, and the length of each of the names.

The second line of the input contains one string consisting of lowercase English letters — the string Tolya wrote on the CD, split in arbitrary place. The length of the string is *n*·*k*. It is guaranteed that the length is not greater than 106.

The third line of the input contains one positive integer *g* (*n*<=≤<=*g*<=≤<=105) — the amount of popular games that could be written on the CD. It is guaranteed that the total length of names of all popular games is not greater than 2·106.

Each of the next *g* lines contains a single string — the name of some popular game. Each name consists of lowercase English letters and has length *k*. It is guaranteed that the names are distinct.

Output Specification:
If there is no answer, print "NO" (without quotes).

Otherwise, print two lines. In the first line print "YES" (without quotes). In the second line, print *n* integers — the games which names were written on the CD. You should print games in the order they could have been written on the CD, it means, in clockwise order. You can print games starting from any position. Remember, that no game was burned to the CD more than once. If there are several possible answers, print any of them.

Demo Input:
['3 1\nabc\n4\nb\na\nc\nd\n', '4 2\naabbccdd\n4\ndd\nab\nbc\ncd\n']

Demo Output:
['YES\n2 1 3 \n', 'NO\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of N+2 integer elements. All elements of the array are in the range 1 to N. Also, all elements occur once except two numbers which occur twice. Find the two repeating numbers.
Note: Return the numbers in their order of appearing twice. So, if X and Y are the repeating numbers, and X repeats twice before Y repeating twice, then the order should be (X, Y).
Example 1:
Input:
N = 4
array[] = {1,2,1,3,4,3}
Output: 1 3
Explanation: In the given array, 
1 and 3 are repeated two times.
Example 2:
Input:
N = 2
array[] = {1,2,2,1}
Output: 2 1
Explanation: In the given array,
1 and 2 are repeated two times 
and second occurence of 2 comes 
before 1. So the output is 2 1.
Your Task:
The task is to complete the function repeatedElements() which takes array arr[] and an integer N as inputs (the size of the array is N + 2 and elements are in the range[1, N]) and finds the two repeated element in the array and return them in a list.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1). 
Constraints: 
2 ≤ N ≤ 10^{5}
1 ≤ array[i] ≤ N

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