vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In programming contest circles, one of the most important roles is that of the Chief Equality Officer (CEO). This person is responsible for making sure that every team has an equal chance of winning the contest. Since last year’s NWERC the current CEO, Gregor, has thought at length about how to make the contest even more fair and equal.

His answer is to introduce a new programming language as the only one allowed for submissions. This way, no team will be disadvantaged by not having mastered any of the allowed languages. This language is called Balloon, short for Building A Long List Of Ordinary Numbers. Its only data type is the list of integers. To keep the language fast, it contains only four instructions:
 - [x$_1$,…,x$_ n$] is the constructor for lists. It returns the integers inside the brackets in their given order.
 - concat(<Expr$_1$>,<Expr$_2$>) returns a list of all the integers returned when evaluating the expression <Expr$_1$> followed by all of the integers returned when evaluating <Expr$_2$>.
 - shuffle(<Expr>) returns a list of all the integers returned by <Expr>, rearranged according to a uniformly random permutation, i.e., each permutation of the elements is used with equal probability.
 - sorted(<Expr>) returns a list of all the integers returned by <Expr>, rearranged into non-decreasing order.

As an example, consider the first expression of Sample Input 1. The two shuffle exressions both take the list [1,2] as input and return one of the lists [1,2] and [2,1], each with probability $0.5$ (independently of each other). The outer concat operator takes the two returned lists as its input and returns their concatenation. I.e., it returns one of the lists [1,2,1,2], [1,2,2,1], [2,1,1,2], and [2,1,2,1], each with probability $0.25$.

Naturally, we cannot use byte-by-byte output comparison any more when teams submit their solutions in Balloon, as its output is probabilistic. The judge server instead has to check whether a submitted program is equivalent to the sample solution created by the judges. Two programs are equivalent if for any list $L$ of integers, both programs have an equal probability of returning $L$.

It is your task to determine whether two given Balloon programs are equivalent.

-----Input-----
The input consists of:
 - One line containing a string A, the first program.
 - One line containing a string B, the second program.

Each program is a syntactically valid Balloon program with between $3$ and $10^6$ characters, and contains neither spacing nor empty lists (i.e., the strings “ ” or “[]” do not occur in the input).

Each integer in each program is greater than $0$ and less than $10^{9}$.

-----Output-----
If the two programs are equivalent, output “equal”, otherwise output “not equal”.

-----Examples-----
Sample Input 1:
concat(shuffle([1,2]),shuffle([1,2]))
shuffle([1,2,1,2])
Sample Output 1:
not equal

Sample Input 2:
sorted(concat([3,2,1],[4,5,6]))
[1,2,3,4,5,6]
Sample Output 2:
equal

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya started to attend programming lessons. On the first lesson his task was to write a simple program. The program was supposed to do the following: in the given string, consisting if uppercase and lowercase Latin letters, it: 
 -  deletes all the vowels, -  inserts a character "." before each consonant, -  replaces all uppercase consonants with corresponding lowercase ones. 
Vowels are letters "A", "O", "Y", "E", "U", "I", and the rest are consonants. The program's input is exactly one string, it should return the output as a single string, resulting after the program's processing the initial string.

Help Petya cope with this easy task.

Input Specification:
The first line represents input string of Petya's program. This string only consists of uppercase and lowercase Latin letters and its length is from 1 to 100, inclusive.

Output Specification:
Print the resulting string. It is guaranteed that this string is not empty.

Demo Input:
['tour\n', 'Codeforces\n', 'aBAcAba\n']

Demo Output:
['.t.r\n', '.c.d.f.r.c.s\n', '.b.c.b\n']

Note:
none

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

# Story

The Pied Piper has been enlisted to play his magical tune and coax all the rats out of town.

But some of the rats are deaf and are going the wrong way!

# Kata Task

How many deaf rats are there?

# Legend

* ```P``` = The Pied Piper
* ```O~``` = Rat going left
* ```~O``` = Rat going right

# Example

* ex1 ```~O~O~O~O P``` has 0 deaf rats


* ex2 ```P O~ O~ ~O O~``` has 1 deaf rat


* ex3 ```~O~O~O~OP~O~OO~``` has 2 deaf rats

---

# Series

* [The deaf rats of Hamelin (2D)](https://www.codewars.com/kata/the-deaf-rats-of-hamelin-2d)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has a string $S$ with length $N$. He also has $M$ other strings $P_{1}, P_{2}, \ldots, P_{M}$, which are called *patterns*. The characters in the strings are indexed from $1$.

Chef was wondering if he could find the $M$ patterns in the string $S$ in the given order. That is, he wanted to know whether it is possible to choose $M$ ranges, denoted by $[l_{i}, r_{i}]$ for each $i$ ($1 ≤ i ≤ M$), such that $1 ≤ l_{1} ≤ r_{1} < l_{2} ≤ r_{2} < \ldots < l_{M} ≤ r_{M} ≤ N$ and for each valid $i$, the substring $S_{l_{i}}, S_{l_{i} + 1}, \ldots, S_{r_{i}}$ equals $P_{i}$.

As this problem was too easy for Chef, he decided to make a harder one. A permutation $p = (p_{1}, p_{2}, \ldots, p_{M})$ of integers $1$ through $M$ is called a *matchable permutation* if Chef can reorder the $M$ patterns into $P_{p_{1}}, P_{p_{2}}, \ldots, P_{p_{M}}$ and then find them in $S$, in this order (in the same way as described above).

Can you help Chef find the number of matchable permutations?

------  Input ------
The first line of the input contains two space-separated integers $N$ and $M$.
The second line contains a single string $S$.
$M$ lines follow. For each $i$ ($1 ≤ i ≤ M)$, the $i$-th of these lines contains a single string $P_{i}$. 

------  Output ------
Print a single line containing one integer - the number of matchable permutations.

------  Constraints  ------
$1 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 14$
$1 ≤ |P_{i}| ≤ 10^{5}$ for each valid $i$
$S, P_{1}, P_{2}, \ldots, P_{M}$ contain only lowercase English letters

------  Subtasks ------
Subtask #1 (10 points): $1 ≤ M ≤ 3$

Subtask #2 (30 points): $1 ≤ N ≤ 1,000$

Subtask #3 (60 points): original constraints

------  Example Input 1 ------

10 3
abbabacbac
ab
ac
b

------  Example Output 1 ------

3

------  Explanation 1 ------
Among the $3! = 6$ possible permutations of $(1, 2, 3)$, the matchable permutations are $(1, 2, 3)$, $(3, 1, 2)$ and $(1, 3, 2)$. These correspond to permutations of patterns ("ab", "ac", "b"), ("b", "ab", "ac") and ("ab", "b", "ac") respectively. Each of them can be found in $S$ in the given order.

------  Example Input 2 ------

3 2
aaa
aa
aa

------  Example Output 2 ------

0
	
------  Explanation 2 ------
We cannot match the two patterns in such a way that their ranges do not intersect.

------  Example Input 3 ------

4 2
aaaa
aa
aa

------  Example Output 3 ------

2
	
------  Explanation 3 ------
The matchable permutations are $(1, 2)$ and $(2, 1)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer N. The task is to check whether a number has exactly three distinct factors or not. 
 
Example 1:
Input:
N = 10
Output:
0
Explanation:
10 has 4 factors- 1,2,5 and 10.
So, the Ouput is 0.
Example 2:
Input:
N = 9
Output:
1
Explanation:
9 has 3 factors- 1,3 and 9.
So, the Ouput is 1.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function hasThreePrimeFac() which takes an Integer N as input and returns 1 if it has exactly 3 factors else returns 0.
 
Expected Time Complexity: O(sqrt(N))
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{12}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On the Internet shopping site, on the same page as the product that the user is currently viewing, some other products that other users have bought in the past along with the product that they are currently viewing are displayed. It is believed that sales can be increased by presenting products that are considered to be highly relevant.

Similar things can be seen in local supermarkets (such as bread and jam) as a way to place items that are often bought together nearby. Your job is to write a program that will help you devise product placement. This time, I would like to set a certain standard number of times and find a combination of two products for which the number of times bought together is equal to or greater than the standard number of times.

When given the information of the products bought together and the standard number of times, create a program that outputs the combination of the two products bought together more than the standard number of times.



Input

The input is given in the following format.


N F
info1
info2
::
infoN


The first line gives the number of pieces of information N (1 ≤ N ≤ 100) and the reference number F (1 ≤ F ≤ 100) of the items bought together. The following N lines are given information on the products bought together. Information about the products bought together infoi is given in the following format.


M item1 item2 ... itemM


M (1 ≤ M ≤ 10) indicates how many products this information contains. itemj is the name of the item bought in this purchase and is a string of 1 to 30 length consisting of only lowercase letters. The same product is never given in infoi.

Output

The number of combinations of two products bought together more than the reference number of times is output on the first line, and all combinations are output on the second and subsequent lines. However, if there is no combination, nothing is output after the second line.

The output order is as follows after arranging the product names in the combination in the lexicographic order (the order in which the words are arranged in the English-Japanese dictionary).

* Compare the first product names, and the one with the earliest in lexicographic order comes first.
* If they are the same, compare the second product names and the lexicographic order comes first.



Separate product names with a single space, and separate product combinations with a single line break.

Examples

Input

5 2
3 bread milk banana
2 milk cornflakes
3 potato bread milk
4 cornflakes bread milk butter
2 potato bread


Output

3
bread milk
bread potato
cornflakes milk


Input

5 5
3 bread milk banana
2 milk cornflakes
3 potato bread milk
4 cornflakes bread milk butter
2 potato bread


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that any two consecutive stones' numbers differ by one of two values.  Legend has it that there is a treasure trove at the end of the trail.  If Manasa can guess the value of the last stone, the treasure will be hers.

Example 

$n=2$ 

$a=2$ 

$b=3$  

She finds $2$ stones and their differences are $a=2$ or $b=3$.  We know she starts with a $0$ stone not included in her count.  The permutations of differences for the two stones are $[2,2],[2,3],[3,2].$ or $[3,3]$.  Looking at each scenario, stones might have $[2,4],[2,5],[3,5]$ or $[3,6]$ on them.  The last stone might have any of  $4,5$, or $6$ on its face. 

Compute all possible numbers that might occur on the last stone given a starting stone with a $0$ on it, a number of additional stones found, and the possible differences between consecutive stones.  Order the list ascending.

Function Description

Complete the stones function in the editor below.   

stones has the following parameter(s):  

int n: the number of non-zero stones  
int a: one possible integer difference  
int b: another possible integer difference  

Returns  

int[]: all possible values of the last stone, sorted ascending  

Input Format

The first line contains an integer $T$, the number of test cases.  

Each test case contains $3$ lines: 

- The first line contains $n$, the number of non-zero stones found. 

- The second line contains $a$, one possible difference 

- The third line contains $b$, the other possible difference.  

Constraints

$1\leq T\leq10 $  
$1\leq n,a,b\leq10^{3}$  

Sample Input
STDIN   Function
-----   --------
2       T = 2 (test cases)
3       n = 3 (test case 1)
1       a = 1
2       b = 2
4       n = 4 (test case 2)
10      a = 10
100     b = 100

Sample Output
2 3 4 
30 120 210 300 

Explanation

With differences 1 and 2, all possible series for the first test case are given below:

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

Hence the answer 2 3 4. 

With differences 10 and 100, all possible series for the second test case are the following: 

0, 10, 20, 30
0, 10, 20, 120
0, 10, 110, 120
0, 10, 110, 210
0, 100, 110, 120
0, 100, 110, 210
0, 100, 200, 210
0, 100, 200, 300

Hence the answer 30 120 210 300.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Somewhere in a mountainous region of the world is a collection of $n$ villages. Connecting these villages to one another is a series of roads, always running directly between two villages and allowing travel in both directions. Due to the treacherous landscape, building these roads is expensive, so the minimum number of roads have been constructed such that each village can reach every other village via a sequence of roads. 

Trade between these villages is very important, since not every village has access to the same supply of natural resources. Many villages produce the same resource, however, so it is useful for villages to know their relative distance to other villages so that they can choose trading partners to minimize overall trading costs. Note that the distance between two villages $a$ and $b$ is the sum of the lengths of the individual roads on the shortest path that connects $a$ and $b$.

A project has been underway to compute the distance between every pair of villages. This information has been incorporated in a table, along with a map that shows the layout of villages and roads that run between them. You have been assigned the task of distributing the table and map to all the villages for the betterment of the regional economy.

Unfortunately, not long after you were given this task, a gust of wind blew the map right out of your hand and into the countryside. Despite your best efforts of searching for it, you have been unable to locate it. You know that you could visit all the villages to reconstruct the map and THEN start distributing the map and table, but this will take twice as long as the original task and the villages will be very displeased with you. You wonder, maybe it’s possible to reconstruct the map given only the table?

-----Input-----
The first line of input will contain the integer $n$ ($2 \leq n \leq 2500$), the number of villages in this region. The next $n$ lines will contain $n$ integers each. The $j^{\rm th}$ integer of the $i^{\rm th}$ line is the distance from village $i$ to village $j$. All distances are greater than zero unless $i = j$, less than $10^7$, and it is guaranteed that the distance from village $i$ to village $j$ is the same as the distance from village $j$ to village $i$.

-----Output-----
For each test case, output $n-1$ lines with two integers $u$ and $v$ on each line, indicating that there is a road connecting villages $u$ and $v$ in this region. Assume the villages are numbered from $1$ to $n$. Any solution that outputs the original set of roads will be accepted.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Innokentiy decides to change the password in the social net "Contact!", but he is too lazy to invent a new password by himself. That is why he needs your help. 

Innokentiy decides that new password should satisfy the following conditions:  the length of the password must be equal to n,  the password should consist only of lowercase Latin letters,  the number of distinct symbols in the password must be equal to k,  any two consecutive symbols in the password must be distinct. 

Your task is to help Innokentiy and to invent a new password which will satisfy all given conditions. 


-----Input-----

The first line contains two positive integers n and k (2 ≤ n ≤ 100, 2 ≤ k ≤ min(n, 26)) — the length of the password and the number of distinct symbols in it. 

Pay attention that a desired new password always exists.


-----Output-----

Print any password which satisfies all conditions given by Innokentiy.


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

Output
java

Input
6 6

Output
python

Input
5 2

Output
phphp



-----Note-----

In the first test there is one of the appropriate new passwords — java, because its length is equal to 4 and 3 distinct lowercase letters a, j and v are used in it.

In the second test there is one of the appropriate new passwords — python, because its length is equal to 6 and it consists of 6 distinct lowercase letters.

In the third test there is one of the appropriate new passwords — phphp, because its length is equal to 5 and 2 distinct lowercase letters p and h are used in it.

Pay attention the condition that no two identical symbols are consecutive is correct for all appropriate passwords in tests.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Xenny was a teacher and his class consisted of N boys and N girls. He took all his students to the playground and asked them to stand in a straight line. The boys and the girls formed a perfect line, but Xenny seemed unhappy. He wanted them to form an alternating sequence of boys and girls, i.e., he wanted that after a boy, there should be a girl in the line, and vice-versa.

In order to form an alternating sequence, a boy and a girl could swap their positions.

Given the original sequence in which the boys and girls were standing, find the minimum number of swaps required to form an alternating sequence.

Note: An alternating sequence can start either with a boy or a girl.

Input
First line of input consists of a natural number T - the number of testcases.
T testcases follow. For each testcase:

First line consists of a single integer N - the number of boys, and the number of girls.
Second line consists of a string of length 2N, representing the original sequence.
In this string, a boy is represented by uppercase character B and a girl by G.

Output
For each testcase, print the minimum number of swaps required to get an alternating sequence on a new line.

Constraints
1 ≤ T ≤ 5

1 ≤ N ≤ 10^6

SAMPLE INPUT
1
2
BBGG

SAMPLE OUTPUT
1

Explanation

The first boy from left  can swap his position with the first girl from right to get the sequence:

GBGB

This is an alternating sequence and it was obtained using 1 swap.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Two positive integers *a* and *b* have a sum of *s* and a bitwise XOR of *x*. How many possible values are there for the ordered pair (*a*,<=*b*)?

Input Specification:
The first line of the input contains two integers *s* and *x* (2<=≤<=*s*<=≤<=1012, 0<=≤<=*x*<=≤<=1012), the sum and bitwise xor of the pair of positive integers, respectively.

Output Specification:
Print a single integer, the number of solutions to the given conditions. If no solutions exist, print 0.

Demo Input:
['9 5\n', '3 3\n', '5 2\n']

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

Note:
In the first sample, we have the following solutions: (2, 7), (3, 6), (6, 3), (7, 2).

In the second sample, the only solutions are (1, 2) and (2, 1).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a polyline going through points (0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – ... - (2kx, 0) – (2kx + x, x) – .... 

We know that the polyline passes through the point (a, b). Find minimum positive value x such that it is true or determine that there is no such x.


-----Input-----

Only one line containing two positive integers a and b (1 ≤ a, b ≤ 10^9).


-----Output-----

Output the only line containing the answer. Your answer will be considered correct if its relative or absolute error doesn't exceed 10^{ - 9}. If there is no such x then output  - 1 as the answer.


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

Output
1.000000000000

Input
1 3

Output
-1

Input
4 1

Output
1.250000000000



-----Note-----

You can see following graphs for sample 1 and sample 3.  [Image]  [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bob and Alice like to play the game tower of Hanoi. One day Alice challenges Bob to build the tallest tower from a
set of disks of different height and radius. The tower of Hanoi can be built by stacking disks on top of each other. In order to put disk A on top of disk B, the radius and height of A must be strictly smaller than those of B.  Help Bob to win the challenge.

Input:
First line of input contains number of test cases T.
First line of each test case contains value of  N, the number of disks. The next N lines contains two positive integer number Ri and Hi corresponding to the radius and height of i^th Disk respectively.

Output:
For each test case print the maximum height of the tower possible.  

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 200
1 ≤ Ri, Hi ≤ 10^9

SAMPLE INPUT
2
3
4 3
1 4
3 2
5
5 6
4 3
1 2
7 5
3 4SAMPLE OUTPUT
5
12

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given two strings *s* and *t* consisting of small Latin letters, string *s* can also contain '?' characters. 

Suitability of string *s* is calculated by following metric:

Any two letters can be swapped positions, these operations can be performed arbitrary number of times over any pair of positions. Among all resulting strings *s*, you choose the one with the largest number of non-intersecting occurrences of string *t*. Suitability is this number of occurrences.

You should replace all '?' characters with small Latin letters in such a way that the suitability of string *s* is maximal.

Input Specification:
The first line contains string *s* (1<=≤<=|*s*|<=≤<=106).

The second line contains string *t* (1<=≤<=|*t*|<=≤<=106).

Output Specification:
Print string *s* with '?' replaced with small Latin letters in such a way that suitability of that string is maximal.

If there are multiple strings with maximal suitability then print any of them.

Demo Input:
['?aa?\nab\n', '??b?\nza\n', 'abcd\nabacaba\n']

Demo Output:
['baab\n', 'azbz\n', 'abcd\n']

Note:
In the first example string "baab" can be transformed to "abab" with swaps, this one has suitability of 2. That means that string "baab" also has suitability of 2.

In the second example maximal suitability you can achieve is 1 and there are several dozens of such strings, "azbz" is just one of them.

In the third example there are no '?' characters and the suitability of the string is 0.

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