vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Vanya and Field

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vanya decided to walk in the field of size *n*<=×<=*n* cells. The field contains *m* apple trees, the *i*-th apple tree is at the cell with coordinates (*x**i*,<=*y**i*). Vanya moves towards vector (*dx*,<=*dy*). That means that if Vanya is now at the cell (*x*,<=*y*), then in a second he will be at cell . The following condition is satisfied for the vector: , where  is the largest integer that divides both *a* and *b*. Vanya ends his path when he reaches the square he has already visited. 

Vanya wonders, from what square of the field he should start his path to see as many apple trees as possible.

Input Specification:
The first line contains integers *n*,<=*m*,<=*dx*,<=*dy*(1<=≤<=*n*<=≤<=106, 1<=≤<=*m*<=≤<=105, 1<=≤<=*dx*,<=*dy*<=≤<=*n*) — the size of the field, the number of apple trees and the vector of Vanya's movement. Next *m* lines contain integers *x**i*,<=*y**i* (0<=≤<=*x**i*,<=*y**i*<=≤<=*n*<=-<=1) — the coordinates of apples. One cell may contain multiple apple trees.

Output Specification:
Print two space-separated numbers — the coordinates of the cell from which you should start your path. If there are several answers you are allowed to print any of them.

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

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

Note:
In the first sample Vanya's path will look like: (1, 3) - (3, 1) - (0, 4) - (2, 2) - (4, 0) - (1, 3)

In the second sample: (0, 0) - (1, 1) - (0, 0)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Modern text editors usually show some information regarding the document being edited. For example, the number of words, the number of pages, or the number of characters.

In this problem you should implement the similar functionality.

You are given a string which only consists of:  uppercase and lowercase English letters,  underscore symbols (they are used as separators),  parentheses (both opening and closing). 

It is guaranteed that each opening parenthesis has a succeeding closing parenthesis. Similarly, each closing parentheses has a preceding opening parentheses matching it. For each pair of matching parentheses there are no other parenthesis between them. In other words, each parenthesis in the string belongs to a matching "opening-closing" pair, and such pairs can't be nested.

For example, the following string is valid: "_Hello_Vasya(and_Petya)__bye_(and_OK)".

Word is a maximal sequence of consecutive letters, i.e. such sequence that the first character to the left and the first character to the right of it is an underscore, a parenthesis, or it just does not exist. For example, the string above consists of seven words: "Hello", "Vasya", "and", "Petya", "bye", "and" and "OK". Write a program that finds:  the length of the longest word outside the parentheses (print 0, if there is no word outside the parentheses),  the number of words inside the parentheses (print 0, if there is no word inside the parentheses). 


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 255) — the length of the given string. The second line contains the string consisting of only lowercase and uppercase English letters, parentheses and underscore symbols. 


-----Output-----

Print two space-separated integers:  the length of the longest word outside the parentheses (print 0, if there is no word outside the parentheses),  the number of words inside the parentheses (print 0, if there is no word inside the parentheses). 


-----Examples-----
Input
37
_Hello_Vasya(and_Petya)__bye_(and_OK)

Output
5 4


Input
37
_a_(_b___c)__de_f(g_)__h__i(j_k_l)m__

Output
2 6


Input
27
(LoooonG)__shOrt__(LoooonG)

Output
5 2


Input
5
(___)

Output
0 0





-----Note-----

In the first sample, the words "Hello", "Vasya" and "bye" are outside any of the parentheses, and the words "and", "Petya", "and" and "OK" are inside. Note, that the word "and" is given twice and you should count it twice in the answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a positive integer N, MoEngage wants you to determine if it is possible to rearrange the digits of N (in decimal representation) and obtain a [multiple] of 5. 

For example, when N = 108, we can rearrange its digits to construct 180 = 36 \cdot 5 which is a multiple of 5.

------ Input Format ------ 

- The first line contains an integer T, the number of test cases. The description of the T test cases follow.
- Each test case consists of two lines
- The first line contains a single integer D, the number of digits in N.
- The second line consists of a string of length D, the number N (in decimal representation). It is guaranteed that the string does not contain leading zeroes and consists only of the characters 0, 1, \dots 9.

------ Output Format ------ 

- For each test case, print \texttt{Yes} if it is possible to rearrange the digits of N so that it becomes a multiple 5. Otherwise, print \texttt{No}.

You may print each character of the string in uppercase or lowercase (for example, the strings \texttt{YeS}, \texttt{yEs}, \texttt{yes} and \texttt{YES} will all be treated as identical).

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ D ≤ 1000$
$1 ≤ N < 10^{1000}$
- Sum of $D$ over all test cases $≤ 1000$.

----- Sample Input 1 ------ 
3
3
115
3
103
3
119
----- Sample Output 1 ------ 
Yes
Yes
No
----- explanation 1 ------ 
Test Case $1$: The given number is already divisible by $5$, therefore the answer is $\texttt{Yes}$.

Test Case 2: We can obtain $310 = 62 \cdot 5$ by rearranging the digits of $103$, so the answer is $\texttt{Yes}$.

Test Case 3: The only numbers that can be obtained by rearranging the digits of $119$ are $\{119, 191, 911\}$. None of these numbers are multiples of $5$, so the answer is $\texttt{No}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Permutation p is an ordered set of integers p_1,  p_2,  ...,  p_{n}, consisting of n distinct positive integers, each of them doesn't exceed n. We'll denote the i-th element of permutation p as p_{i}. We'll call number n the size or the length of permutation p_1,  p_2,  ...,  p_{n}.

Petya decided to introduce the sum operation on the set of permutations of length n. Let's assume that we are given two permutations of length n: a_1, a_2, ..., a_{n} and b_1, b_2, ..., b_{n}. Petya calls the sum of permutations a and b such permutation c of length n, where c_{i} = ((a_{i} - 1 + b_{i} - 1) mod n) + 1 (1 ≤ i ≤ n).

Operation $x \text{mod} y$ means taking the remainder after dividing number x by number y.

Obviously, not for all permutations a and b exists permutation c that is sum of a and b. That's why Petya got sad and asked you to do the following: given n, count the number of such pairs of permutations a and b of length n, that exists permutation c that is sum of a and b. The pair of permutations x, y (x ≠ y) and the pair of permutations y, x are considered distinct pairs.

As the answer can be rather large, print the remainder after dividing it by 1000000007 (10^9 + 7).


-----Input-----

The single line contains integer n (1 ≤ n ≤ 16).


-----Output-----

In the single line print a single non-negative integer — the number of such pairs of permutations a and b, that exists permutation c that is sum of a and b, modulo 1000000007 (10^9 + 7).


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

Output
18

Input
5

Output
1800

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers $n$ and $k$. Your task is to find if $n$ can be represented as a sum of $k$ distinct positive odd (not divisible by $2$) integers or not.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^5$) — the number of test cases.

The next $t$ lines describe test cases. The only line of the test case contains two integers $n$ and $k$ ($1 \le n, k \le 10^7$).


-----Output-----

For each test case, print the answer — "YES" (without quotes) if $n$ can be represented as a sum of $k$ distinct positive odd (not divisible by $2$) integers and "NO" otherwise.


-----Example-----
Input
6
3 1
4 2
10 3
10 2
16 4
16 5

Output
YES
YES
NO
YES
YES
NO



-----Note-----

In the first test case, you can represent $3$ as $3$.

In the second test case, the only way to represent $4$ is $1+3$.

In the third test case, you cannot represent $10$ as the sum of three distinct positive odd integers.

In the fourth test case, you can represent $10$ as $3+7$, for example.

In the fifth test case, you can represent $16$ as $1+3+5+7$.

In the sixth test case, you cannot represent $16$ as the sum of five distinct positive odd integers.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Spongebob is already tired trying to reason his weird actions and calculations, so he simply asked you to find all pairs of n and m, such that there are exactly *x* distinct squares in the table consisting of *n* rows and *m* columns. For example, in a 3<=×<=5 table there are 15 squares with side one, 8 squares with side two and 3 squares with side three. The total number of distinct squares in a 3<=×<=5 table is 15<=+<=8<=+<=3<==<=26.

Input Specification:
The first line of the input contains a single integer *x* (1<=≤<=*x*<=≤<=1018) — the number of squares inside the tables Spongebob is interested in.

Output Specification:
First print a single integer *k* — the number of tables with exactly *x* distinct squares inside.

Then print *k* pairs of integers describing the tables. Print the pairs in the order of increasing *n*, and in case of equality — in the order of increasing *m*.

Demo Input:
['26\n', '2\n', '8\n']

Demo Output:
['6\n1 26\n2 9\n3 5\n5 3\n9 2\n26 1\n', '2\n1 2\n2 1\n', '4\n1 8\n2 3\n3 2\n8 1\n']

Note:
In a 1 × 2 table there are 2 1 × 1 squares. So, 2 distinct squares in total.

In a 2 × 3 table there are 6 1 × 1 squares and 2 2 × 2 squares. That is equal to 8 squares in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array a_1, a_2, ..., a_{n} of n integers, find the largest number in the array that is not a perfect square.

A number x is said to be a perfect square if there exists an integer y such that x = y^2.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of elements in the array.

The second line contains n integers a_1, a_2, ..., a_{n} ( - 10^6 ≤ a_{i} ≤ 10^6) — the elements of the array.

It is guaranteed that at least one element of the array is not a perfect square.


-----Output-----

Print the largest number in the array which is not a perfect square. It is guaranteed that an answer always exists.


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

Output
2

Input
8
1 2 4 8 16 32 64 576

Output
32



-----Note-----

In the first sample case, 4 is a perfect square, so the largest number in the array that is not a perfect square is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Absent-minded Masha got set of n cubes for her birthday.

At each of 6 faces of each cube, there is exactly one digit from 0 to 9. Masha became interested what is the largest natural x such she can make using her new cubes all integers from 1 to x.

To make a number Masha can rotate her cubes and put them in a row. After that, she looks at upper faces of cubes from left to right and reads the number.

The number can't contain leading zeros. It's not required to use all cubes to build a number.

Pay attention: Masha can't make digit 6 from digit 9 and vice-versa using cube rotations.


-----Input-----

In first line integer n is given (1 ≤ n ≤ 3) — the number of cubes, Masha got for her birthday.

Each of next n lines contains 6 integers a_{i}_{j} (0 ≤ a_{i}_{j} ≤ 9) — number on j-th face of i-th cube.


-----Output-----

Print single integer — maximum number x such Masha can make any integers from 1 to x using her cubes or 0 if Masha can't make even 1.


-----Examples-----
Input
3
0 1 2 3 4 5
6 7 8 9 0 1
2 3 4 5 6 7

Output
87
Input
3
0 1 3 5 6 8
1 2 4 5 7 8
2 3 4 6 7 9

Output
98


-----Note-----

In the first test case, Masha can build all numbers from 1 to 87, but she can't make 88 because there are no two cubes with digit 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Farmer Bob have a big farm, where he growths chickens, rabbits and cows. It is very difficult to count the number of animals for each type manually, so he diceded to buy a system to do it. But he bought a cheap system that can count only total number of heads, total number of legs and total number of horns of animals on the farm.
Help Bob to figure out how many chickens, rabbits and cows does he have?

All chickens have 2 legs, 1 head and no horns; all rabbits have 4 legs, 1 head and no horns; all cows have 4 legs, 1 head and 2 horns.

Your task is to write a function 
```Python
get_animals_count(legs_number, heads_number, horns_number)
```
```Csharp
Dictionary get_animals_count(int legs_number, int heads_number, int horns_number)
```
, which returns a dictionary 
```python
{"rabbits" : rabbits_count, "chickens" : chickens_count, "cows" : cows_count}
``` 
```Csharp
new Dictionary(){{"rabbits", rabbits_count},{"chickens", chickens_count},{"cows", cows_count}}
```

Parameters `legs_number, heads_number, horns_number` are integer, all tests have valid input.

Example:

```python
get_animals_count(34, 11, 6); # Should return {"rabbits" : 3, "chickens" : 5, "cows" : 3}
get_animals_count(154, 42, 10); # Should return {"rabbits" : 30, "chickens" : 7, "cows" : 5}
```

```Csharp
get_animals_count(34, 11, 6); //Should return  Dictionary(){{"rabbits", 3},{"chickens", 5},{"cows", 3}}
get_animals_count(154, 42, 10); //Should return Dictionary(){{"rabbits", 30},{"chickens", 7},{"cows", 5}}
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $t$ and $n$ strings $s_1, s_2, \dots, s_n$. All strings consist of lowercase Latin letters.

Let $f(t, s)$ be the number of occurences of string $s$ in string $t$. For example, $f('\text{aaabacaa}', '\text{aa}') = 3$, and $f('\text{ababa}', '\text{aba}') = 2$.

Calculate the value of $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j)$, where $s + t$ is the concatenation of strings $s$ and $t$. Note that if there are two pairs $i_1$, $j_1$ and $i_2$, $j_2$ such that $s_{i_1} + s_{j_1} = s_{i_2} + s_{j_2}$, you should include both $f(t, s_{i_1} + s_{j_1})$ and $f(t, s_{i_2} + s_{j_2})$ in answer.


-----Input-----

The first line contains string $t$ ($1 \le |t| \le 2 \cdot 10^5$).

The second line contains integer $n$ ($1 \le n \le 2 \cdot 10^5$).

Each of next $n$ lines contains string $s_i$ ($1 \le |s_i| \le 2 \cdot 10^5$).

It is guaranteed that $\sum\limits_{i=1}^{n} |s_i| \le 2 \cdot 10^5$. All strings consist of lowercase English letters.


-----Output-----

Print one integer — the value of $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j)$.


-----Examples-----
Input
aaabacaa
2
a
aa

Output
5

Input
aaabacaa
4
a
a
a
b

Output
33

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Hooray! Berl II, the king of Berland is making a knight tournament. The king has already sent the message to all knights in the kingdom and they in turn agreed to participate in this grand event.

As for you, you're just a simple peasant. There's no surprise that you slept in this morning and were late for the tournament (it was a weekend, after all). Now you are really curious about the results of the tournament. This time the tournament in Berland went as follows:  There are n knights participating in the tournament. Each knight was assigned his unique number — an integer from 1 to n.  The tournament consisted of m fights, in the i-th fight the knights that were still in the game with numbers at least l_{i} and at most r_{i} have fought for the right to continue taking part in the tournament.  After the i-th fight among all participants of the fight only one knight won — the knight number x_{i}, he continued participating in the tournament. Other knights left the tournament.  The winner of the last (the m-th) fight (the knight number x_{m}) became the winner of the tournament. 

You fished out all the information about the fights from your friends. Now for each knight you want to know the name of the knight he was conquered by. We think that the knight number b was conquered by the knight number a, if there was a fight with both of these knights present and the winner was the knight number a.

Write the code that calculates for each knight, the name of the knight that beat him.


-----Input-----

The first line contains two integers n, m (2 ≤ n ≤ 3·10^5; 1 ≤ m ≤ 3·10^5) — the number of knights and the number of fights. Each of the following m lines contains three integers l_{i}, r_{i}, x_{i} (1 ≤ l_{i} < r_{i} ≤ n; l_{i} ≤ x_{i} ≤ r_{i}) — the description of the i-th fight.

It is guaranteed that the input is correct and matches the problem statement. It is guaranteed that at least two knights took part in each battle.


-----Output-----

Print n integers. If the i-th knight lost, then the i-th number should equal the number of the knight that beat the knight number i. If the i-th knight is the winner, then the i-th number must equal 0.


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

Output
3 1 4 0 
Input
8 4
3 5 4
3 7 6
2 8 8
1 8 1

Output
0 8 4 6 4 8 6 1 


-----Note-----

Consider the first test case. Knights 1 and 2 fought the first fight and knight 1 won. Knights 1 and 3 fought the second fight and knight 3 won. The last fight was between knights 3 and 4, knight 4 won.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is that you should complete all the projects in easy version but this is not necessary in hard version.

Polycarp is a very famous freelancer. His current rating is $r$ units.

Some very rich customers asked him to complete some projects for their companies. To complete the $i$-th project, Polycarp needs to have at least $a_i$ units of rating; after he completes this project, his rating will change by $b_i$ (his rating will increase or decrease by $b_i$) ($b_i$ can be positive or negative). Polycarp's rating should not fall below zero because then people won't trust such a low rated freelancer.

Is it possible to complete all the projects? Formally, write a program to check if such an order of the projects exists, that Polycarp has enough rating before starting each project, and he has non-negative rating after completing each project.

In other words, you have to check that there exists such an order of projects in which Polycarp will complete them, so he has enough rating before starting each project, and has non-negative rating after completing each project.


-----Input-----

The first line of the input contains two integers $n$ and $r$ ($1 \le n \le 100, 1 \le r \le 30000$) — the number of projects and the initial rating of Polycarp, respectively.

The next $n$ lines contain projects, one per line. The $i$-th project is represented as a pair of integers $a_i$ and $b_i$ ($1 \le a_i \le 30000$, $-300 \le b_i \le 300$) — the rating required to complete the $i$-th project and the rating change after the project completion.


-----Output-----

Print "YES" or "NO".


-----Examples-----
Input
3 4
4 6
10 -2
8 -1

Output
YES

Input
3 5
4 -5
4 -2
1 3

Output
YES

Input
4 4
5 2
5 -3
2 1
4 -2

Output
YES

Input
3 10
10 0
10 -10
30 0

Output
NO



-----Note-----

In the first example, the possible order is: $1, 2, 3$.

In the second example, the possible order is: $2, 3, 1$.

In the third example, the possible order is: $3, 1, 4, 2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gunnar and his friends like games which involve rolling dice. Gunnar has a huge collection of 6-sided, 12-sided and 20-sided dice. All the games with dice started to bore him, so he came up with a new game. He rolls an $s$-sided die $n$ times and wins if at least $k$ different numbers appear in the $n$ throws. An $s$-sided die contains $s$ distinct numbers $1, \dots , s$ on its sides.

Since this is a game only for one person, Gunnar and his friends decided to make it more fun by letting other people bet on a particular game. Before you bet on a particular game, you would like to know how probable it is to throw at least $k$ different numbers in $n$ throws with an $s$-sided die. We assume that all numbers have the same probability of being thrown in each throw.

-----Input-----
The input consists of a single line with three integers $n$, $s$, and $k$ ($1\le n\le 10000, 1 \le k \le s \le 500$). $n$ is the number of throws, $k$ the number of different numbers that are needed to win and $s$ is the number of sides the die has.

-----Output-----
Output one line with the probability that a player throws at least $k$ different numbers within $n$ throws with an $s$-sided die. Your answer should be within absolute or relative error at most $10^{-7}$.

-----Examples-----
Sample Input:
3 3 2
Sample Output:
0.888888889

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

Watson gives an array A of N integers A_{1}, A_{2}, ..., A_{N} to Sherlock. He wants Sherlock to reorganize the array in a way such that no two adjacent numbers differ by more than 1.
Formally, if reorganized array is B_{1}, B_{2}, ..., B_{N}, then the condition that | B_{i} - B_{i + 1} | ≤ 1, for all 1 ≤ i < N(where |x| denotes the absolute value of x) should be met.
Sherlock is not sure that a solution exists, so he asks you.

------ Input ------ 

First line contains T, number of test cases. Each test case consists of N in one line followed by N integers in next line denoting A_{1}, A_{2}, ..., A_{N}.

------ Output ------ 

For each test case, output in one line YES or NO denoting if array A can be reorganized in required way or not.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤  10^{9}$
$Sum of N over all test cases  ≤ 2*10^{5}$

----- Sample Input 1 ------ 
2
4
3 2 2 3 
2
1 5
----- Sample Output 1 ------ 
YES
NO
----- explanation 1 ------ 

Test case 1:
No need to reorganise.

Test case 2:
No possible way.

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