vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given a sequence of integers $a$, a triplet $(a[i],a[j],a[k])$ is beautiful if:

$i\lt j\lt k$
$a[j]-a[i]=a[k]-a[j]=d$

Given an increasing sequenc of integers and the value of $\boldsymbol{d}$, count the number of beautiful triplets in the sequence.

Example 

$arr=[2,2,3,4,5]$ 

$\boldsymbol{d}=1$    

There are three beautiful triplets, by index: $[i,j,k]=[0,2,3],[1,2,3],[2,3,4]$.  To test the first triplet, $ar r[j]-ar r[i]=3-2=1$ and $ar r[k]-ar r[j]=4-3=1$.  

Function Description  

Complete the beautifulTriplets function in the editor below.     

beautifulTriplets has the following parameters:  

int d: the value to match   
int arr[n]:  the sequence, sorted ascending   

Returns   

int: the number of beautiful triplets   

Input Format

The first line contains $2$ space-separated integers, $n$ and $\boldsymbol{d}$, the length of the sequence and the beautiful difference. 

The second line contains $n$ space-separated integers $arr\left[i\right]$.

Constraints

$1\leq n\leq10^4$
$1\leq d\leq20$
$0\leq\textit{arr}[i]\leq2\times10^4$
$ar r[i]>ar r[i-1]$

Sample Input
STDIN           Function
-----           --------
7 3             arr[] size n = 7, d = 3
1 2 4 5 7 8 10  arr = [1, 2, 4, 5, 7, 8, 10]

Sample Output
3

Explanation

There are many possible triplets $(arr[i],ar r[j],ar r[k])$, but our only beautiful triplets are $(1,4,7)$ , $(4,7,10)$ and $(2,5,8)$ by value, not index. Please see the equations below:    

$7-4=4-1=3=d$ 

$10-7=7-4=3=d$ 

$8-5=5-2=3=d$  

Recall that a beautiful triplet satisfies the following equivalence relation: $arr[j]-arr[i]=arr[k]-arr[j]=d$ where $i\lt j\lt k$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The enemy and their massive army is approaching your fortress, and all you have to defend it is a legion of guardian gnomes. There is no hope of winning the battle, so your focus will instead be on causing as much damage as possible to the enemy. 

You have $n$ gnomes at your disposal. Before the battle, they must be divided into at most $m$ non-empty groups. The battle will then proceed in turns. Each turn, your gnomes will attack the enemy, causing one unit of damage for each living gnome. Then the enemy will attack by throwing a lightning bolt at one of the $m$ groups. The lightning bolt kills $k$ of the gnomes in that group, or all of them if the number of living gnomes in the group is less than $k$. The battle ends when all gnomes are dead. The enemy will always throw the lightning bolts in an optimal way such that the total damage caused by the gnomes is minimized.

Now you wonder, what is the maximum amount of damage you can cause to the enemy if you divide the gnomes into groups in an optimal way?

For example, if as in Sample Input 1 you have $n=10$ gnomes that are to be divided into $m=4$ groups, and the lightning bolt does at most $k=3$ damage, then an optimal solution would be to create one large group of size $7$ and three small groups of size $1$. In the first round, you cause $10$ damage and the lightning bolt reduces the large group by $3$. In the next round, you cause $7$ damage and the large group is reduced down to size $1$. In the remaining four rounds you do $4$, $3$, $2$, and $1$ damage respectively and the lightning bolt removes one group each round. In total you do $10+7+4+3+2+1 = 27$ damage.

-----Input-----
The input consists of a single line containing the three integers $n$, $m$, and $k$ ($1 \le n \le 10^9$, $1 \le m, k \le 10^7$), with meanings as described above.

-----Output-----
Output the maximum amount of damage you can cause to the enemy.

-----Examples-----
Sample Input:
10 4 3
Sample Output:
27

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mike has always been thinking about the harshness of social inequality. He's so obsessed with it that sometimes it even affects him while solving problems. At the moment, Mike has two sequences of positive integers *A*<==<=[*a*1,<=*a*2,<=...,<=*a**n*] and *B*<==<=[*b*1,<=*b*2,<=...,<=*b**n*] of length *n* each which he uses to ask people some quite peculiar questions.

To test you on how good are you at spotting inequality in life, he wants you to find an "unfair" subset of the original sequence. To be more precise, he wants you to select *k* numbers *P*<==<=[*p*1,<=*p*2,<=...,<=*p**k*] such that 1<=≤<=*p**i*<=≤<=*n* for 1<=≤<=*i*<=≤<=*k* and elements in *P* are distinct. Sequence *P* will represent indices of elements that you'll select from both sequences. He calls such a subset *P* "unfair" if and only if the following conditions are satisfied: 2·(*a**p*1<=+<=...<=+<=*a**p**k*) is greater than the sum of all elements from sequence *A*, and 2·(*b**p*1<=+<=...<=+<=*b**p**k*) is greater than the sum of all elements from the sequence *B*. Also, *k* should be smaller or equal to  because it will be to easy to find sequence *P* if he allowed you to select too many elements!

Mike guarantees you that a solution will always exist given the conditions described above, so please help him satisfy his curiosity!

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105) — the number of elements in the sequences. 

On the second line there are *n* space-separated integers *a*1,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109) — elements of sequence *A*.

On the third line there are also *n* space-separated integers *b*1,<=...,<=*b**n* (1<=≤<=*b**i*<=≤<=109) — elements of sequence *B*.

Output Specification:
On the first line output an integer *k* which represents the size of the found subset. *k* should be less or equal to .

On the next line print *k* integers *p*1,<=*p*2,<=...,<=*p**k* (1<=≤<=*p**i*<=≤<=*n*) — the elements of sequence *P*. You can print the numbers in any order you want. Elements in sequence *P* should be distinct.

Demo Input:
['5\n8 7 4 8 3\n4 2 5 3 7\n']

Demo Output:
['3\n1 4 5\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
rishi loves to solve string puzzles. His friend kartheek gave him a task on string. which comprises of a string that has to be manipulated accordingly to the query of kartheek.
for every query there will be the starting and ending index of the string and rishi has to generate all non repeating arrangements of the string in between the specified indices.

INPUT :
first line consists of a string S.
Next line consists of an integer representing no. of queries Q.
Next q lines consists of starting and ending indices S and E respectively.

OUTPUT :
Output should consists of all arrangements of string for all queries. After completion of every query leave one line and print output of next query.

SAMPLE INPUT
abcd
2
1 3
2 3

SAMPLE OUTPUT
abcd
abdc
acbd
acdb
adcb
adbc

abcd
abdc

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
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-----

The first line of the input contains a positive integer n (1 ≤ n ≤ 10^5) — the number of the available sticks.

The second line of the input contains n positive integers l_{i} (2 ≤ l_{i} ≤ 10^6) — the lengths of the sticks.


-----Output-----

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.


-----Examples-----
Input
4
2 4 4 2

Output
8

Input
4
2 2 3 5

Output
0

Input
4
100003 100004 100005 100006

Output
10000800015

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is Borya's eleventh birthday, and he has got a great present: n cards with numbers. The i-th card has the number a_{i} written on it. Borya wants to put his cards in a row to get one greater number. For example, if Borya has cards with numbers 1, 31, and 12, and he puts them in a row in this order, he would get a number 13112.

He is only 11, but he already knows that there are n! ways to put his cards in a row. But today is a special day, so he is only interested in such ways that the resulting big number is divisible by eleven. So, the way from the previous paragraph is good, because 13112 = 1192 × 11, but if he puts the cards in the following order: 31, 1, 12, he would get a number 31112, it is not divisible by 11, so this way is not good for Borya. Help Borya to find out how many good ways to put the cards are there.

Borya considers all cards different, even if some of them contain the same number. For example, if Borya has two cards with 1 on it, there are two good ways.

Help Borya, find the number of good ways to put the cards. This number can be large, so output it modulo 998244353.


-----Input-----

Input data contains multiple test cases. The first line of the input data contains an integer t — the number of test cases (1 ≤ t ≤ 100). The descriptions of test cases follow.

Each test is described by two lines.

The first line contains an integer n (1 ≤ n ≤ 2000) — the number of cards in Borya's present.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^9) — numbers written on the cards.

It is guaranteed that the total number of cards in all tests of one input data doesn't exceed 2000.


-----Output-----

For each test case output one line: the number of ways to put the cards to the table so that the resulting big number was divisible by 11, print the number modulo 998244353.


-----Example-----
Input
4
2
1 1
3
1 31 12
3
12345 67 84
9
1 2 3 4 5 6 7 8 9

Output
2
2
2
31680

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jack and Jill are playing a game. They have balls numbered from `0` to `n - 1`. Jack looks the other way and asks Jill to reverse the position of the balls, for instance, to change the order from say, `0,1,2,3` to `3,2,1,0`. He further asks Jill to reverse the position of the balls `n` times, each time starting from one position further to the right, till she reaches the last ball. So, Jill has to reverse the positions of the ball starting from position `0`, then from position `1`, then from position `2` and so on. At the end of the game, Jill will ask Jack to guess the final position of any ball numbered `k`. 

You will be given `2` integers, the first will be `n`(balls numbered from `0` to `n-1`) and the second will be `k`. You will return the position of the ball numbered `k` after the rearrangement.

```Perl
solve(4,1) = 3. The reversals are [0,1,2,3] -> [3,2,1,0] -> [3,0,1,2] -> [3,0,2,1]. => 1 is in position 3.
```

More examples in the test cases. Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive number n > 1 find the prime factor decomposition of n.
The result will be a string with the following form :
```
 "(p1**n1)(p2**n2)...(pk**nk)"
```
where ```a ** b``` means ```a``` to the power of ```b```

with the p(i) in increasing order and n(i) empty if
n(i) is 1.
```
Example: n = 86240 should return "(2**5)(5)(7**2)(11)"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A left rotation operation on an array of size $n$ shifts each of the array's elements $1$ unit to the left. Given an integer, $\boldsymbol{d}$, rotate the array that many steps left and return the result.  

Example 

$\boldsymbol{d}=2$ 

$arr=[1,2,3,4,5]$  

After $2$ rotations, $ar r'=[3,4,5,1,2]$.

Function Description  

Complete the rotateLeft function in the editor below.  

rotateLeft has the following parameters:  

int d:  the amount to rotate by  
int arr[n]: the array to rotate  

Returns  

int[n]: the rotated array

Input Format

The first line contains two space-separated integers that denote $n$, the number of integers, and $\boldsymbol{d}$, the number of left rotations to perform. 

The second line contains $n$ space-separated integers that describe $\mbox{arr}[]$.  

Constraints

$1\leq n\leq10^5$  
$1\leq d\leq n$  
$1\leq a[i]\leq10^6$

Sample Input
5 4
1 2 3 4 5

Sample Output
5 1 2 3 4

Explanation

To perform $\boldsymbol{d}=4$ left rotations, the array undergoes the following sequence of changes: 

$[1,2,3,4,5]\to[2,3,4,5,1]\to[3,4,5,1,2]\to[4,5,1,2,3]\to[5,1,2,3,4]$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mack gives Daisy two strings S1 and S2-consisting only of characters- 'M' and 'D' , and asks her to convert S1 to S2 in exactly N moves.

In a single move, Daisy has two choices:
Exchange any one 'M' with a 'D', or
Exchange any one 'D' with a 'M'.

You need to help Daisy if it's possible to transform S1 to S2 in exactly N moves. Output "Yes" if possible, else "No".

Input Format:
First line contains T, the number of test cases. T lines follow.
Each line consists of 2 space separated strings S1 and S2, and and the value N.

Output Format:
For each test case, print the answer, either "Yes" or "No"-(Without the quotes).

Constraints:
1 ≤ T ≤ 250
1 ≤ |S1|=|S2| ≤ 50
1 ≤ N ≤ 100

SAMPLE INPUT
3
MMDMDDM DDDDDDD 2
MMDD MMDD 1
MMMMMDMM DDDDDMDD 8

SAMPLE OUTPUT
No
No
Yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: You're a Professional

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A simple recommendation system would recommend a user things liked by a certain number of their friends. In this problem you will implement part of such a system.

You are given user's friends' opinions about a list of items. You are also given a threshold *T* — the minimal number of "likes" necessary for an item to be recommended to the user.

Output the number of items in the list liked by at least *T* of user's friends.

Input Specification:
The first line of the input will contain three space-separated integers: the number of friends *F* (1<=≤<=*F*<=≤<=10), the number of items *I* (1<=≤<=*I*<=≤<=10) and the threshold *T* (1<=≤<=*T*<=≤<=*F*).

The following *F* lines of input contain user's friends' opinions. *j*-th character of *i*-th line is 'Y' if *i*-th friend likes *j*-th item, and 'N' otherwise.

Output Specification:
Output an integer — the number of items liked by at least *T* of user's friends.

Demo Input:
['3 3 2\nYYY\nNNN\nYNY\n', '4 4 1\nNNNY\nNNYN\nNYNN\nYNNN\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A professor went to a party. Being an erudite person, he classified the party into two categories. He proposed that if all the persons in the party are wearing different colored robes, then that is a girl’s only party. If we even get one duplicate color, it must be a boy’s party. The colors of the robes are represented by positive integers.
 
Example 1:
Input
N = 5
A[] = {1, 2, 3, 4, 7}
Output
GIRLS
Explanation:
All the colors are unique so it's a GIRLS party.
 
Example 2:
Input
N = 6
A[] = {1, 3, 2, 4, 5, 1}
Output
BOYS
Explanation:
There are two colors 1. So it's a BOYS party.
 
Your task:
You don't need to print the answer, printing is done by the driver code itself. You have to complete the function PartyType() which takes the array A[] and its size N as inputs and returns  “BOYS” (without quotes) if it’s a boy’s party, else returns “GIRLS”.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints
1 ≤ N ≤ 10^{5}
1 ≤ A_{i }≤ 10^{9}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Polycarp's Practice

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp is practicing his problem solving skill. He has a list of $n$ problems with difficulties $a_1, a_2, \dots, a_n$, respectively. His plan is to practice for exactly $k$ days. Each day he has to solve at least one problem from his list. Polycarp solves the problems in the order they are given in his list, he cannot skip any problem from his list. He has to solve all $n$ problems in exactly $k$ days.

Thus, each day Polycarp solves a contiguous sequence of (consecutive) problems from the start of the list. He can't skip problems or solve them multiple times. As a result, in $k$ days he will solve all the $n$ problems.

The profit of the $j$-th day of Polycarp's practice is the maximum among all the difficulties of problems Polycarp solves during the $j$-th day (i.e. if he solves problems with indices from $l$ to $r$ during a day, then the profit of the day is $\max\limits_{l \le i \le r}a_i$). The total profit of his practice is the sum of the profits over all $k$ days of his practice.

You want to help Polycarp to get the maximum possible total profit over all valid ways to solve problems. Your task is to distribute all $n$ problems between $k$ days satisfying the conditions above in such a way, that the total profit is maximum.

For example, if $n = 8, k = 3$ and $a = [5, 4, 2, 6, 5, 1, 9, 2]$, one of the possible distributions with maximum total profit is: $[5, 4, 2], [6, 5], [1, 9, 2]$. Here the total profit equals $5 + 6 + 9 = 20$.

Input Specification:
The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2000$) — the number of problems and the number of days, respectively.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2000$) — difficulties of problems in Polycarp's list, in the order they are placed in the list (i.e. in the order Polycarp will solve them).

Output Specification:
In the first line of the output print the maximum possible total profit.

In the second line print exactly $k$ positive integers $t_1, t_2, \dots, t_k$ ($t_1 + t_2 + \dots + t_k$ must equal $n$), where $t_j$ means the number of problems Polycarp will solve during the $j$-th day in order to achieve the maximum possible total profit of his practice.

If there are many possible answers, you may print any of them.

Demo Input:
['8 3\n5 4 2 6 5 1 9 2\n', '5 1\n1 1 1 1 1\n', '4 2\n1 2000 2000 2\n']

Demo Output:
['20\n3 2 3', '1\n5\n', '4000\n2 2\n']

Note:
The first example is described in the problem statement.

In the second example there is only one possible distribution.

In the third example the best answer is to distribute problems in the following way: $[1, 2000], [2000, 2]$. The total profit of this distribution is $2000 + 2000 = 4000$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence of integers $a_1, a_2, \dots, a_n$. You need to paint elements in colors, so that:   If we consider any color, all elements of this color must be divisible by the minimal element of this color.  The number of used colors must be minimized. 

For example, it's fine to paint elements $[40, 10, 60]$ in a single color, because they are all divisible by $10$. You can use any color an arbitrary amount of times (in particular, it is allowed to use a color only once). The elements painted in one color do not need to be consecutive.

For example, if $a=[6, 2, 3, 4, 12]$ then two colors are required: let's paint $6$, $3$ and $12$ in the first color ($6$, $3$ and $12$ are divisible by $3$) and paint $2$ and $4$ in the second color ($2$ and $4$ are divisible by $2$). For example, if $a=[10, 7, 15]$ then $3$ colors are required (we can simply paint each element in an unique color).


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 100$), where $n$ is the length of the given sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$). These numbers can contain duplicates.


-----Output-----

Print the minimal number of colors to paint all the given numbers in a valid way.


-----Examples-----
Input
6
10 2 3 5 4 2

Output
3

Input
4
100 100 100 100

Output
1

Input
8
7 6 5 4 3 2 2 3

Output
4



-----Note-----

In the first example, one possible way to paint the elements in $3$ colors is:

  paint in the first color the elements: $a_1=10$ and $a_4=5$,  paint in the second color the element $a_3=3$,  paint in the third color the elements: $a_2=2$, $a_5=4$ and $a_6=2$. 

In the second example, you can use one color to paint all the elements.

In the third example, one possible way to paint the elements in $4$ colors is:

  paint in the first color the elements: $a_4=4$, $a_6=2$ and $a_7=2$,  paint in the second color the elements: $a_2=6$, $a_5=3$ and $a_8=3$,  paint in the third color the element $a_3=5$,  paint in the fourth color the element $a_1=7$.

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

* 1 ≤ |V| ≤ 1000
* 0 ≤ |E| ≤ 2000
* -10000 ≤ di ≤ 10000
* There are no parallel edges
* There are no self-loops

Input

An edge-weighted graph G (V, E) and the source r.


|V| |E| r
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1


|V| is the number of vertices and |E| is the number of edges in G. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the source of the graph.

si and ti represent source and target vertices of i-th edge (directed) and di represents the cost of the i-th edge.

Output

If the graph contains a negative cycle (a cycle whose sum of edge costs is a negative value) which is reachable from the source r, print


NEGATIVE CYCLE


in a line.

Otherwise, print


c0
c1
:
c|V|-1


The output consists of |V| lines. Print the cost of the shortest path from the source r to each vertex 0, 1, ... |V|-1 in order. If there is no path from the source to a vertex, print "INF".

Examples

Input

4 5 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2


Output

0
2
-3
-1


Input

4 6 0
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2
3 1 0


Output

NEGATIVE CYCLE


Input

4 5 1
0 1 2
0 2 3
1 2 -5
1 3 1
2 3 2


Output

INF
0
-5
-3

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